我把快排写错了?

众所周知，快速排序的时间复杂度是$O(n\lg n)$的。然而因为我太菜，写出来的快速排序一不小心就成了$O(n^2)$…

这个辣鸡问题

这个应该都知道，当待排序数组已经有序时，固定选择某一个位置的数字当哨兵的快排会变成$O(n^2)$。一个解决方法就是随机选择哨兵，或者干脆将输入的数组打乱后再排序。

然而，如果输入的数组数字全部相同呢？

当然这在实际中很少见，但是在实现的时候就要小心。在这种情况下，所实现的快排必须对于相同数字也交换位置，否则就会退化为$O(n^2)$。

比如说，这个

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);//继续处理右边的 ，这里是一个递归的过程
}

还有这个，

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)$。

大概就是这回事，没别的了。这种情况当然有改进的快速排序可以直接避免这种罕见的情况，在不大幅度改动算法的前提下，就要对相同的元素也进行换位才可以，即使会增加交换次数。