快速排序复杂度
快排的平均时间为：T(n) = k*n*lnn
时间复杂度为：O(n*logn)
快速排序法的时间复杂度是nlogn（n×log以2为底n的对数）
拓展：
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
附各种排序法的时间复杂度如下：
快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。
最好情况
如图9‐9‐7所示，它是{50,10,90,30, 70,40,80,60,20}在快速排序过程中的递归过程。由于我们的第一个关键字是50，正好是待排序的序列的中间值，因此递归树是平衡的，此时性能也比较好。
在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度就为.log2n.+1（.x.表示不大于x的最大整数），即仅需递归log2n次，需要时间为T（n）。第一次Partiation需要对整个数组扫描一遍，做n次比较。然后，获得的枢轴将数组一分为二，那么各自还需要T（n/2）的时间（注意是最好情况，所以平分两半）。于是不断地划分下去，我们就有了下面的不等式推断。
T（n）≤2T（n/2） +n，T（1）=0 T（n）≤2（2T（n/4）+n/2） +n=4T（n/4）+2n
T（n）≤4（2T（n/8）+n/4） +2n=8T（n/8）+3n
……
T（n）≤nT（1）+（log2n）×n= O(nlogn) 12345
也就是说，在最优的情况下，快速排序算法的时间复杂度为O(nlogn)。
最坏情况
在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它就是一棵斜树。此时需要执行n‐1次递归调用，且第i次划分需要经过n‐i次关键字的比较才能找到第i个记录，也就是枢轴的位置，因此比较次数为
最终其时间复杂度为O(n2)。
平均情况
平均的情况，设枢轴的关键字应该在第k的位置（1≤k≤n），那么：
由数学归纳法可证明，其数量级为O(nlogn)。
什么排序的速度(时间复杂度)最快?
其时间复杂度为O(nlog2n)。这是就平均情况而言的，如果从最好的情况考虑，则插入排序和起泡排序的时间复杂度最好，为O(n)，而其他算法的最好情况同平均情况大致相同。如果从最坏的情况考虑，快速排序的时间复杂度为O(n2)，插入排序和起泡排序虽然同平均情况相同，但系数大约增加一倍，运行速度降低一...
...pascal)详解,不要源程序,时间复杂度n(logn);谢了\/\/
快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：var a:array[0..10] of integer；n:integer;procedure qsort(l,r:longint);{r，l表示集合的左右边界，即把第r到第l个数进行排序} var i,j,m:longint;begin m:=a[l];{标准数} i:=l; {I，J为指针} j:=r;repeat...
排序算法时间复杂度、空间复杂度、稳定性比较
1.插入类排序 直接插入排序,折半插入排序,希尔排序 2.交换类排序 冒泡排序,快速排序 3.选择类排序 简单选择排序,堆排序 4.归并类排序 二路归并排序 5.基数类排序 基数排序 (1)时间复杂度 快些以nlogn的速度归队 (2)空间复杂度 快排O(log2n),归并排序O(n...
计算机二级ms office高级应用基础知识
(1)交换类排序法。 冒泡排序:通过对待排序序列从后向前或从前向后,依次比较相邻元素的排序码,若发现逆序则交换,使较大的元素逐渐从前部移向后部或较小的元素逐渐从后部移向前部,直到所有元素有序为止。在最坏情况下,对长度为n的线性表排序,冒泡排序需要比较的次数为n(n-1)\/2。 快速排序:是迄今为止所有内排...
如何计算时间复杂度
以 上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。O(n^2)2.1. ...
归并排序平均时间复杂度
2、在归并排序中，每次递归都会将数组切分为两个子数组，因此在最坏情况下（即初始数组已经有序），归并排序的时间复杂度为O（nlogn）。在最坏情况下，归并排序需要递归logn次，每次递归需要遍历整个子数组，因此总的时间复杂度为O（nlogn）。3、在平均情况下，归并排序的时间复杂度也是O（nlogn）。在...
...74 11 65 58 94 36 99 87 按从小到大顺序进行排序,排序速度最快的算...
插入排序，时间复杂度： O(n的平方)。冒泡排序的算法时间复杂度上O(n^2 )选择排序的平均时间复杂度也是O(n^2)的。快速排序是不稳定的.最理想情况算法时间复杂度O(nlog2n).最坏O(n ＾2). 答案D
直接选择排序的时间复杂度是多少?
关键字比较次数永远是n(n-1)\/2，记录移动次数最多为3(n-1)，最少0次，前者起主导作用，因此实际上时间复杂度还是O(n^2)。在直接选择排序中，共需要进行n-1次选择和交换，每次选择需要进行 n-i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数C=(n*n - n)\/2,...
归并排序的平均时间复杂度
1、效率高：归并排序的时间复杂度为O（nlogn），在所有排序算法中，其效率仅次于快速排序。因此，对于处理大量数据的情况，归并排序具有很好的性能。2、稳定：归并排序是稳定的，即相同值的元素在排序后保持原来的相对顺序。这对于某些应用场景非常重要，例如在处理学生成绩单时，如果两个学生的成绩相同，...
描述n个数据的冒泡排序算法,时间复杂度是多少
重复2号步骤，直至再也不能交换。冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。选择排序 选择排序是这样实现的：设数组内存放了n个待排数字，数组下标从1开始，到n结束。i=1 从数组的第i个元素开始到第n个元素，寻找最小的元素。将上一步找到的最小元素和第i...
鄣策增抗： 快速排序的平均时间复杂度和最坏时间复杂度分别是O(nlgn)、O(n^2). 当排序已经成为基本有序状态时,快速排序退化为O(n^2),一般情况下,排序为指数复杂度. 快速排序最差情况递归调用栈高度O(n),平均情况递归调用栈高度O(logn),而...
博尔塔拉蒙古自治州15599176070： 8、快速排序平均情况和最坏情况下的算法时间复杂度分别为:A)平均情况O(nlog(2,n)),最坏情况O(n^2) B)8、快速排序平均情况和最坏情况下的算法时间... - ？
鄣策增抗：[答案] 是A 最坏的情况是当这个列本来就有序的情况,这样的情况是很坏的,达到了N平方的复杂度.
博尔塔拉蒙古自治州15599176070： 电脑编程中快速排序的时间复杂度n log n 是n*log(n)还是什么？
鄣策增抗： 快速排序的平均复杂度是在n*log2(n)也就是nlog(n),在信息学中nlog(n)的底数默认为2.至于说快速排序10个数的时间复杂度,是没办法计算的,这个还是和这10个数的初始顺序有关.只能说排序10个数的平均复杂度在10*log2(10),如果这个10个序列差劲,复杂度也有可能是O(10^2).(快速排序的最坏情况下的时间复杂度是O(n^2))
博尔塔拉蒙古自治州15599176070： 什么排序的速度(时间复杂度)最快? - ？
鄣策增抗： 从时间复杂度看,所有内部排序方法可以分为两类.1.插入排序 选择排序 起泡排序 其时间复杂度为O(n2);2.堆排序 快速排序 归并排序 其时间复杂度为O(nlog2n).这是就平均情况而言的,如果从最好的情况考虑, 则插入排序和起泡排序的时间复杂度最好,为O(n), 而其他算法的最好情况同平均情况大致相同.如果从最坏的情况考虑,快速排序的时间复杂度为O(n2),插入排序和起泡排序虽然同平均情况相同,但系数大约增加一倍,运行速度降低一半,而选择排序、堆排序和归并排序则影响不大.总之, 在平均情况下,快速排序最快; 在最好情况下,插入排序和起泡排序最快; 在最坏情况下,堆排序和归并排序最快.
博尔塔拉蒙古自治州15599176070： 快速排序时间复杂度怎样推算的 - ？
鄣策增抗： 快速排序是基于二分的,所以在理想情况下它的时间复杂度为O(NLOG2N),极端情况下(数据恰好逆序)则相当于选择排序,复杂度退化为O(N^2);
博尔塔拉蒙古自治州15599176070： 快速排序等时间复杂度问题？
鄣策增抗： 时间复杂度实际上就是程序的关键语句运行的次数. 算法复杂度的评价一般是算法对于一个大小固定的样本的执行时间,一般这个时间可以通过一个根据算法评估出来的多项式来表达的.例如,选择排序的复杂度就是O(n^2)[注:选择排序对于长度为n的序列每选出第k个数都要和后面k+1~n数进行比较,所以实际的复杂程度应该是n+n-1+n-2+...+2+1=(n^2+n)/2而在复杂度表示时,n被看作极大的值,所以忽略他的系数和后面的低次项,所以表示成o(n^2)] 对于快速排序,同样可以求出它的平均复杂度是O(NlogN)具体的计算方法可以自己尝试(提示,划分次数是log N 比较次数是N)最坏情况是O(n^2)
博尔塔拉蒙古自治州15599176070： 5. 快速排序在平均情况下的时间复杂度为 - --------------,在最坏情况下的时 间复杂度为----------------. - ？
鄣策增抗： 快速排序时间复杂度下界为O(nlogn),最坏情况为O(n^2) 快速排序的平均时间复杂度为O(nlogn).
博尔塔拉蒙古自治州15599176070： C语言 各常见排序法的时间复杂度 急 请简单说明 - ？
鄣策增抗： 选择排序抄算法复杂度是O(n^2). 插入排序是O(n^2) 快速排序快速排序是不稳2113定的.5261最理想情况算法时间复杂度O(nlog2n),最坏4102O(n^2). 堆排序算法时间复杂度O(nlogn). 归并1653排序的时间复杂度是O(nlog2n).
博尔塔拉蒙古自治州15599176070： 对于输入为N个数进行快速排序算法的平均时间复杂度是多少? - ？
鄣策增抗： 根据T(n) = T(ðn) + O(n) (0 < ð <1) 则有 T(n) = O(n) 因此关键问题是怎样解决划分标准的问题, 因此产生下列线性时间找中位数的算法: 将数组a有n个元素, 划分成5个一组, 则共有[n/5]个元素, 对于每组用一般的排序找中位数,需要25次, ...
