关于快速排序及其最坏情况下的时间复杂度的问题假设您为每个分区级别选择中间轴心点
快速排序是一种常用的排序算法，它的核心思想是通过分治的方式将一个大问题分解为多个小问题进行解决。在快速排序中，我们选择一个轴心点（也称为中间轴心点）作为基准，将待排序的序列分成两部分，一部分小于轴心点，一部分大于轴心点，然后对这两部分分别进行递归排序，最终得到有序序列。
快速排序的最坏情况下的时间复杂度是O(n^2)，即当序列已经有序或基本有序时，每次选择的轴心点都是最大或最小元素，导致每次划分只能减少一个元素，需要进行n次划分，因此时间复杂度达到O(n^2)。但是在平均情况下，快速排序的时间复杂度为O(nlogn)，具有较高的效率。
快速排序的优势在于它的原地排序特性和较高的平均时间复杂度。它不需要额外的存储空间，只需要对原始序列进行交换和比较操作，因此空间复杂度为O(1)。同时，快速排序在大多数情况下都能够快速地将序列分割成两部分，递归地进行排序，因此在实际应用中具有较好的性能。
快速排序适用于各种规模的数据集，特别是对于大规模数据的排序，快速排序通常是首选的排序算法之一。它广泛应用于各个领域的排序需求，例如数据库查询、搜索引擎排序、数据分析等。
腾讯云提供了多种云计算相关产品，其中与快速排序相关的产品可能是腾讯云的云服务器（CVM）和弹性MapReduce（EMR）。云服务器提供了高性能、可扩展的计算资源，可以用于执行快速排序算法。弹性MapReduce是一种大数据处理服务，可以方便地进行分布式计算和数据处理，也可以用于快速排序的实现。
腾讯云云服务器（CVM）产品介绍链接：https://cloud.tencent.com/product/cvm 腾讯云弹性MapReduce（EMR）产品介绍链接：https://cloud.tencent.com/product/emr
相关·内容
3回答
快速排序和优化的快速排序之间的根本区别是什么？快速排序的改进是什么？Java是如何决定使用这种排序而不是合并排序的？
浏览 2提问于2010-05-06得票数 5
回答已采纳
2回答
我检查了K&R书中的快速排序代码，2小时后我仍然不能理解第一个交换(swap(a, left, (left+right)/2);)实现了什么。我试着删除它，但排序仍然有效。有人能解释一下吗？这是一个性能问题吗？如果是这样，为什么呢？这个动作在我看来似乎是随机的(也就是说，在一些数字组上，它将提高性能，而在一些数字上则不会)。
谢谢。
void qsort(int a[], int left, int right)
{
int i, last;
if (left >= right)
return;
swap(a, left, (left+
浏览 2提问于2015-05-09得票数 2
有没有人能用“简单的英语”直观而正式地解释一下QuickSort n log是怎么回事？根据我的理解，它必须遍历n个项目，并且它做了这个log n times...Im，不知道如何用语言来表达为什么它做了这个log n次。
浏览 0提问于2012-05-03得票数 61
回答已采纳
1回答
这是我的实现。当我放入100个大小为1000000的数组时，排序时间为300秒。我的另一个算法，合并排序，做了40秒。我想知道，是否有一些东西可能会减慢我的算法。
template <typename TYP> void quick_sort(TYP *tab, int poczatek, int koniec) {
int i = poczatek;
int j = poczatek;
int srodek = (poczatek + koniec) / 2;
int piwot = tab[srodek];
swap(tab[srodek], tab[ko
浏览 0提问于2021-03-23得票数 1
以下排序算法在哪种类型的数据输入上有效/无效？快速排序，合并排序，堆排序，插入排序等。 我知道至少有两个因素影响排序算法的性能: 1)输入的大小，2)数据是否已经大部分排序。但我不知道这些因素是如何影响算法效率的。 我想详细研究这一点，所以如果你能给我任何来源/链接，那就太好了。
浏览 18提问于2019-05-03得票数 1
1回答
降低快速排序法的复杂度
、、、、
嘿，伙计们，我有一个问题，我正在试着降低这段代码的复杂性(在底部)。我的想法是删除while循环中的If子句，但我有点做不到。我在这里尝试做的是比较SortArray的两个元素，并使用快速排序算法对它们进行排序。目标是使算法尽可能简单。较小和较大的索引遍历数组，并在元素大于轴心时切换。更大的是在中间的末端，以便与枢轴进行切换。
if (records.getElementAt(smaller).compareTo(Pivot) > 0 ) {
swap(records, smaller, bigger);
bigger--;
}
浏览 5提问于2018-05-06得票数 0
1回答
这是我的快速排序代码，它选择最正确的值作为轴心：
def qsort_right(self, array):
less = []
equal = []
greater = []
last_value = len(array) - 1
if len(array) > 1:
pivot = array[last_value]
for i in array:
if i < pivot:
less.append(i)
if i == piv
浏览 2提问于2014-07-27得票数 0
我试着在网上翻看我可爱的课本(没有用)。根据科尔门的书I'm book off，我们将使用数组中的第一个元素作为轴心。我只是不知道该怎么做，因为第一个元素恰好是1。
该数组如下所示：
1、16、2、3、14、5、12、7、10、8、9、17、19、21、23、26、27
同样，书中算法的问题是它选择第一个元素作为轴心。一旦我们将1与所有其他元素进行比较，并发现没有其他元素小于或等于，那么我们将交换枢轴和子数组的中间元素，其中左侧的子数组小于枢轴，右侧的子数组大于枢轴。但是如果我们的轴心是1，那么我们就没有办法交换。真的很困惑，任何帮助都是很好的。这本书的标题是算法导论，第三版，如果有人
浏览 5提问于2013-06-04得票数 3
回答已采纳
好吧，我想对给定的3值使用快速排序，不管是什么值，我如何才能得到最坏的情况，也就是9操作？
有没有人可以画一棵树，并展示它是如何显示nlogn和n^2操作的？我试着在网上找过了，但我还是没能画出一幅合适的画来说明这一点。
浏览 7提问于2016-09-07得票数 0
2回答
因此，我正在学习QuickSort，并且对运行时间有一点困惑。输入有三种类型:升序、降序和随机序。如果我们从子数组的第一个位置( input )选择pivot，我知道按升序或降序对输入进行排序需要O(n^2)。对随机顺序输入进行排序需要O(nlogn)还是仍然需要O(n^2)时间？
浏览 10提问于2020-11-30得票数 0
1回答
我一直在看不同的视频和阅读不同的文章关于快速排序算法。
我理解它是如何工作的，如果我没有，有大量的在线材料供我查看。我在这里遇到的问题是，我发现的一些文章声明如下()：
重新排序数组，这样所有值小于枢轴的元素都会出现在枢轴之前，而值大于枢轴的所有元素都会出现在它之后(等量值都可以)。在此分区之后，枢轴处于其最后位置。这称为分区操作。
其他一些来源，()：
我们在周围交换元素，使得所有小于枢轴的元素都在大于枢轴的元素之前。
这两种算法有很大的不同。第一种方法使用枢轴将数组拆分，并将较小的东西放在一边，而将较大的东西放在另一边。
第二种方法与枢轴本身无关，但它将确保所有小于枢轴的元
浏览 0提问于2018-08-16得票数 0
回答已采纳
1回答
中位快速排序中值的最坏情况时间复杂度是多少(枢轴是由需要O(n)时间查找的中间值的中位数决定的)？
浏览 1提问于2014-11-22得票数 0
回答已采纳
我想说它最糟糕的时间复杂度仍然是n log n，因为我使用中间元素作为轴心，所以即使数组已经排序，当它从分区方法返回时，它仍然是数组的一半。我可能错了，我的DS不是最好的
public static void quicksort(int [] arr, int low, int high){
if(low < high){
int pivot = partition(arr, low, high);
quicksort(arr, low, pivot);
quicksort(arr, pivot+1, high);
浏览 0提问于2020-09-15得票数 0
7回答
什么是确定性快速排序？
、、、
我一直在读有关快速排序的文章，发现有时它被称为“确定性快速排序”。
这是普通快速排序的替代版本吗？普通的快速排序和确定性的快速排序有什么区别？
浏览 0提问于2010-02-23得票数 11
回答已采纳
6回答
快速排序最坏情况
、、
为了更好地理解它，我正在编写下面所需的程序。
快速排序的最坏情况运行时间是多少，什么可能导致这种更糟糕的情况性能？我们如何修改快速排序程序来缓解这个问题？
我知道它有最坏的情况，我知道它发生在O(n^2)唯一的最小或最大元素时。我的问题是，我如何修改程序来缓解这个问题。
一个好的算法就好了。
浏览 2提问于2010-10-26得票数 34
我做了一个排序算法，但我想也许我只是重新发明了快速排序。
然而，我听说快速排序是O(N^2)个最坏情况；我想我的算法应该只有O(NLogN)个最坏情况。
这和快速排序是一样的吗？
该算法的工作原理是交换值，以便将所有小于中值的值移动到数组的左侧。然后它在每一端递归地工作。
该算法从i=0开始，j= n-1
I和j相互移动，如果需要，listi和listj将被交换。
下面是递归之前第一次迭代的一些代码：
_list = [1,-4,2,-5,3,-6]
def in_place(_list,i,j,median):
while i<j:
a,b = _list[i
浏览 1提问于2012-03-20得票数 3
回答已采纳
2回答
这是快速排序算法的一部分代码，但我真的不知道它为什么使用rand() %n，请帮助我谢谢
Swap(V,0,rand() %n) // move pivot elem to V[0]
浏览 0提问于2010-06-08得票数 3
回答已采纳
4回答
尝试理解快速排序的复杂性
、、、、
我知道当轴心是最小或最大的元素时，最坏的情况会发生。然后，其中一个分区是空的，我们对N-1个元素重复递归
而是如何计算到O(N^2)
我已经读了几篇文章，但仍然不能完全理解它。
同样，最好的情况是轴是数组的中值，并且左右部分的大小相同。但是，值O(NlogN)是如何计算的呢？
浏览 1提问于2016-10-28得票数 1
我有一个由N个相同的数字组成的数组，我正在对它应用快速排序。在这种情况下，排序的时间复杂度是多少。
我环顾了一下这个问题，但没有得到确切的解释。
浏览 0提问于2012-09-19得票数 0
1回答
目前，我正在学习C，并选择实现快速排序作为练习。
我的代码是正确的排序，但之后，我看了一些教程关于快速排序在线。他们用不同的方式实现它。
我不知道，是我误解了快速排序，还是简单地以不同的方式实现了它。
我是如何理解快速排序的：
选择枢轴
根据其大小(比枢轴大/小)
重复直到数组被排序
我使用中间元素作为枢轴，以避免标准的最坏情况。
我的代码：
#include <stdio.h>
#include <math.h>
void quicksort(unsigned int* array, unsigned int length)
{
if (length &l
浏览 0提问于2020-04-20得票数 1
回答已采纳
2回答
快速排序和中值使用相同的方法(除法和同意法)，为什么它们有不同的渐近行为？
难道快速排序可能没有使用正确的枢轴吗？
浏览 4提问于2014-02-12得票数 0
回答已采纳
3回答
也就是说，当给定一个已经排序的列表时，快速排序的性能会更好吗？我不明白为什么会出现这种情况，但可能我并不完全理解算法。
此外，当我们在排序时向列表中添加新数据时，快速排序是否可以继续进行？在我看来，算法在一开始就需要所有数据的全集才能“工作”。
浏览 2提问于2013-10-09得票数 0
3回答
我如何生成并打印快速排序的最坏情况集，考虑到中间元素？这是我的快速排序算法的实现：
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
in
浏览 0提问于2013-10-16得票数 0
我读到可以让快速排序在O(nlogn)上运行
该算法表示，在每一步中选择中位数作为枢轴
但是，假设我们有这样的数组：
10 8 39 2 9 20
哪个值将是中位数？
在数学中，如果我没记错的话，中位数是(39+2)/2 = 41/2 = 20.5
但是我的数组中没有20.5
提前感谢
浏览 0提问于2012-01-03得票数 3
回答已采纳
2回答
了解合并排序和快速排序的运行时间
、、、、
对于合并排序和快速排序，我都在尝试想出它们成为最坏情况的场景。如果我是正确的，合并排序的最坏情况是O(nlogn)，当所有东西都排序好的时候。快速排序的最坏情况是，当pivot位于最不理想的位置时，数组被排序，因此它变成O(n^2)。首先，我想知道这是否正确，如果不正确，请纠正我。我真正的问题是，如果快速排序的轴心在数组的中间，那么该数组必须是什么样子才能达到O(n^2)？
浏览 33提问于2017-03-09得票数 2
import random, timeit
#Qucik sort
def quick_sort(A,first,last):
global Qs,Qc
if first>=last: return
left, right= first+1, last
pivot = A[first]
while left <= right:
while left <=last and A[left]<pivot:
Qc= Qc+1
left= left + 1
浏览 19提问于2020-04-27得票数 1
回答已采纳
我知道算法的最坏情况-当元素已经排序或所有元素都相同时，但想知道算法从nlgn的复杂性移动到n2的点。
浏览 34提问于2014-09-07得票数 -3
2回答
我实现了以下代码，但它似乎不适用于我的数组具有重复值的情况。
private int partition(Integer[] arr,int left, int right)
{
int i = left;
int j = right;
int pivot = arr[left];
while(true)
{
while(arr[i] <pivot) i++;
while(arr[j] > pivot) j--;
if(i < j)
{
p
浏览 0提问于2016-02-14得票数 1
3回答
因为最坏情况下的快速排序复杂度为O(n^2)
在升序情况下，当pivot选择第一个或最后一个元素时，它会给出O(n^2)的正确最坏情况复杂度，因为树的一个子元素总是空的
但是当pivot选择了中间时，我会感到困惑吗？它将树一分为二，使其复杂度为O(n.logn)
假设10 20 30 40 50 60 70 pivot=40
(10 20 30 ) 40 (50 60 70)
左侧枢轴20，右侧枢轴60
(10) 20 (30)
(50) 60 (70)
正确吗？
浏览 10提问于2014-07-08得票数 3
1回答
我已经得到了这个算法，它可以计算数组的中位数，并对它周围的其他项进行分区。 它将所有小于中位数的元素放在一个集合A1中，所有等于它的元素放在A2中，所有大于中值的元素放在A3中。如果A1大于1，它就会递归地进入其中，A3也会发生同样的情况。它在A中复制A1、A2和A3的串联后终止。 我知道它与Quickselect非常相似，但我不知道如何处理才能在最坏的情况下计算出时间复杂性。 我所知道的是，在快速排序中，时间复杂度是T(n) =n -1 + T(a) + t(n -a-1)，其中n-1表示分区，T(a)是对第一部分的递归调用，T(n -a-1)是对最后一部分的递归调用。在这种情况下，当pi
浏览 15提问于2019-04-01得票数 0
教授告诉我，排序数组上的快速排序将继续给出n2 =n- 1，n-2等等。我不太明白它如何等于n-1，整个概念真的把我搞糊涂了。有人能帮上忙吗？
这就是我的意思：
浏览 33提问于2021-10-19得票数 0
6回答
在这两个算法中，你所做的就是把你的结构递归地一分为二，然后以正确的顺序构建你的结构，这样说对吗？
那么，有什么不同呢？
编辑:我找到了在快速排序中实现分区的以下算法，但我并不真正理解它是如何工作的，特别是使用(hi + low) >>> 1作为参数的swop行！有人能理解这一点吗？
private static int partition( int[] items, int lo, int hi )
{
int destination = lo;
swop( items, (hi + lo) >>> 1, hi );
// The
浏览 0提问于2011-04-19得票数 5
11回答
快速排序:选择轴心
、、、
在实现快速排序时，您必须做的一件事就是选择一个轴心。但当我看到下面这样的伪代码时，我不清楚我应该如何选择pivot。列表的第一个元素？还有别的吗？
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to l
浏览 29提问于2008-10-02得票数 125
回答已采纳
2回答
快速排序中的分区元素的理想选择是
(A)清单的第一要素
(B)清单的最后一项内容
(C)名单中随机选择的元素
(D)名单的中位数
答案是(A)，但我认为应该是(D)。我哪里错了？
浏览 1提问于2017-05-17得票数 0
回答已采纳
2回答
深度快速排序复杂性
、、、、
所以我要考试，这次考试的很大一部分将是快速排序算法。大家都知道，最好的情况场景，也是这个算法的平均情况是：O(nlogn)。最坏的情况是O(n^2)。
至于最坏的情况，我知道如何解释它:当选定的支点是数组中最小或最大的值时，我们就会有可能占用n时间的n快速排序调用(我指分区操作)。我说的对吗？
现在是最好的/一般的情况。我读过Cormens的书，通过这本书我理解了很多东西，但是关于快速排序算法，他关注的是如何解释O(nlogn)复杂性的数学公式。我只是想知道为什么它是O(nlogn)，而不是进入一些数学证明。目前，我只看到一些维基百科的解释，如果我们选择一个支点，每次将数组划分为n/2, n/
浏览 1提问于2017-06-17得票数 3
回答已采纳
如果我使用修改后的quicksort版本来查找数组中最小的kth项，为什么预期的运行时间O(n) (如Programming Pearls book所述)？
我使用的算法如下：
1) Runs quick sort on the array
2) If k is > the correct location of pivot, then run quicksort on the 2nd half.
Otherwise run it on the first half.
我的印象是，这将需要O(n * logn)的工作。
浏览 0提问于2013-07-29得票数 2
回答已采纳
5回答
我有一个由N个相同的数字组成的数组，我正在对它应用快速排序。在这种情况下，排序的时间复杂度是多少。
我环顾了一下这个问题，但没有得到确切的解释。
任何帮助都将不胜感激。
浏览 3提问于2011-02-26得票数 21
回答已采纳
3回答
我已经实现了一个有效的quickSort算法，使用数组中的第一个元素作为枢轴，如下所示：
public int[] quickSort( int[] a, int start, int end){
int l = start;
int r = end;
int pivotIndex = start; //<---- first element in the array as pivot!
// must be at least two elements
if ( end - start >= 1){
// set p
浏览 0提问于2012-03-03得票数 0
回答已采纳
6回答
快速排序优于堆排序
、、、、
堆排序的复杂度在最坏的情况下是O(nlogn)，而快速排序的复杂度是O(n^2)。但经验证据表明，快速排序更优越。为什么会这样呢？
浏览 0提问于2009-12-06得票数 48
回答已采纳
我注意到，在使用自定义IComparer<T>对.NET中的数组进行排序时，会请求将项与其自身进行比较。
为什么会这样呢？当然，如果要对相同的索引进行比较，并假设结果必须为零，那么这无疑是一个微不足道的优化。
示例代码：
class Comparer : IComparer<string>
{
public int Compare(string x, string y)
{
Console.WriteLine("{0} vs {1}", x, y);
return string.Compare(x, y);
}
}
sta
浏览 1提问于2012-11-12得票数 4
回答已采纳
1回答
我正在尝试对数组进行分区，以便数组前半部分中的每个元素都小于数组后半部分中的每个元素。这与快速排序中使用的分区算法相同。由于某些原因，我可以让数组A = [2, 8, 7, 1, 3, 5, 6, 4]工作，但A = [7, 3, 6, 1, 9, 5, 4, 8]不能工作。
def partition(A):
x = A[len(A)-1]
i = -1
for j in range (0, len(A)-2):
if A[j]<=x:
i = i + 1
# exchange A[j] and A[i]
浏览 10提问于2017-03-12得票数 0
1回答
问题是如何在数组中找到"Kth“最小元素。
现在我确实看到了给定的技术，但不能正确地理解它们。看到问题后，我的第一个直觉是从给定的数组创建BST，并使用BST的InOrder遍历来查找数组的"Kth“最小元素。这是我的方法代码。
/*
#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* left;
node* right;
};
vector<int> v;//sorted vector
node* insert(node* root
浏览 2提问于2020-09-20得票数 0
回答已采纳
我发现在3-Way QuickSort中，最好的情况是O(n)，当每个元素相等时，最坏的情况是O(n²)，我不知道什么是O(n²)。
它是使用单轴，而不是双轴的。
我读到这篇文章的网站是：。
浏览 0提问于2019-09-30得票数 0
只是编写了一个quickSort算法，我似乎无法摆脱索引越界错误或无限循环。谁能给我指个方向？提前感谢！
-快速排序
def quickSort(lst):
if len(lst) <= 1:
return lst
while len(lst) > 1:
pivot = part(lst)
quickSort(lst[ :pivot])
quickSort(lst[pivot+1: ])
return lst
def part(a):
x = a[0]
i = 1
浏览 1提问于2015-02-10得票数 0
2回答
我已经给出了一个在C++中实现快速排序的任务，并且我已经成功地编写了看起来可以工作的代码。当我测试我的算法是否失败时，当我让它在一个包含一百万个元素的二进制文件中对数字进行排序时，它崩溃了。请注意，我有两个文件，每个文件都有一百万个元素。其中一个是未排序的，另一个是“几乎排序的”，我的算法似乎只在排序“几乎排序”的文件时失败。下面是我的代码：
int partition(int arr[], int low, int high)
{
int pivotI = low; //pivot index
int pivot = arr[pivotI];
int tem
浏览 27提问于2016-09-28得票数 1
回答已采纳
5回答
嘿，谁能告诉我每一个的基本算法和每一个的跟踪序列。我很困惑，网上有很多方法，我真的不知道哪一个是最简单/最聪明的。谢谢。
浏览 15提问于2010-12-06得票数 2
回答已采纳
当pivot始终是子列表中第二小元素时，快速排序的时间复杂度。
还是O(NlogN)吗？
如果我解递归方程
F(N) = F(N-2) + N
= F(N-2(2)) + 2N -2
= F(N-3(2)) + 3N - (2+1)(2)
= F(N-4(2)) + 4N - (3+2+1)(2)
这是O(N^2)，但不知何故我怀疑我的答案，有人能帮我澄清一下吗？
浏览 5提问于2018-07-23得票数 0
回答已采纳
考虑到排序算法的平均案例复杂度Omega(n*lg(n))的硬下界，什么时候/为什么您决定用快速排序来实现这个选择算法，而不是仅仅使用随机枢轴或数组中简单(n/2)的位置？
浏览 2提问于2015-04-29得票数 3
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
