以下是快排的java算法：
public class QuickSort {
public static void quickSort(int a[], int start, int end) {
if (start >= 0 && end <= a.length - 1 && start < end) {
int low = start;
int high = end;
int splitKey = a[start];
while (start < end) {
while (start < end && a[end] >= splitKey) end--;
a[start] = a[end];
while (start < end && a[start] <= splitKey) start++;
a[end] = a[start];
}
a[end] = splitKey;
quickSort(a, low, start - 1);
quickSort(a, start + 1, high);
}
}
public static void quickSort(int a[]) {
quickSort(a, 0, a.length - 1);
}
}
大家都知道快排的时间复杂度是O(n*ln[n])，那么这个复杂度是如何计算出来的呢？
最好的情况下，每次划分对一个记录定位后，要记录的左侧子序列与右侧子序列的长度相同。在具有n个记录的序列中，一次划分需要对整个待划分序列扫描一遍，所需的时间为O(n)。
设$T_n$是对n个记录的序列进行排序的时间，每次划分后，正好把划分区域分为长度相等的连个子序列，显然T(0)=T(1) =1,则有：
image.png
最坏的情况下，待排序的记录序列正序或逆序，每次划分只能得到一个比上一次划分少一个记录的子序列，（另一个子序列为空）。此时，必须经过n-1次递归调用才能把所有记录定位，而且第i趟划分需要经过n-i次比较才能找个才能找到第i个记录的位置，因此时间复杂度为
image.png
平均情况下，设轴值记录的关键码第k小（1≤k≤n）,则有：
image.png
由上式可推出如下两式：
image.png
两式相减,然后两边同除以n(n+1)得
image.png
又因为f(n)单调递减，单调有界数列极限定理，所以f(n)有界
image.png
此数称为欧拉常数，
约为 0.57721566490153286060651209
所以
image.png
所以
image.png
**如果有何处不当，请不吝赐教，一定多加完善。谢谢 **
参考资料：
【1】《算法设计与分析》第二版 王红梅
网友评论