众所周知，快速排序的时间复杂度是$O(n\lg n)$的。然而因为我太菜，写出来的快速排序一不小心就成了$O(n^2)$…
这个辣鸡问题
这个应该都知道，当待排序数组已经有序时，固定选择某一个位置的数字当哨兵的快排会变成$O(n^2)$。一个解决方法就是随机选择哨兵，或者干脆将输入的数组打乱后再排序。
然而，如果输入的数组数字全部相同呢？
当然这在实际中很少见，但是在实现的时候就要小心。在这种情况下，所实现的快排必须对于相同数字也交换位置，否则就会退化为$O(n^2)$。
比如说，这个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
void quicksort(int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
//顺序很重要，要先从右边开始找
while(a[j]>=temp && i<j)
j--;
//再找右边的
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归位
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
}
|
还有这个，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void quick_sort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
}
|
它们都会跳过相同的数字，每次排序后哨兵总会在边界上，导致算法劣化到$O(n^2)$。
大概就是这回事，没别的了。这种情况当然有改进的快速排序可以直接避免这种罕见的情况，在不大幅度改动算法的前提下，就要对相同的元素也进行换位才可以，即使会增加交换次数。