我把快排写错了? • CC's

众所周知，快速排序的时间复杂度是 $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);//继续处理右边的 ，这里是一个递归的过程
    }

cpp

还有这个，

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);
    }
}

cpp

它们都会跳过相同的数字，每次排序后哨兵总会在边界上，导致算法劣化到 $O(n^2)$ 。

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