深入理解快速排序算法的稳定性

在初次接触排序算法稳定性这个概念时，我一直认为复杂度为O(n²)的算法是稳定的，复杂度为O(nlogn)的算法是不稳定的。当时是这样理解的，复杂度为O(n²)的算法不可能再坏，而复杂度为O(nlogn)的算法在极端情况下可能会退化为O(n²)，例如快速排序。但其实这是错误的，稳定性的概念远没有这么复杂，它只表示两个值相同的元素在排序前后是否有位置变化。如果前后位置变化，则排序算法是稳定的，否则是不稳定的。稳定性的定义符合常理，两个值相同的元素无需再次交换位置，交换位置是做了一次无用功。

       之前对稳定性这个概念认识很浅，只停留在知道这个名词的层次上，直到最近写代码遇到一个诡异的现象才让我对稳定性有了更深刻的认识。我现在需要对大量数据进行排序，数据范围有限。针对数据量的大小，可以选择快速排序和基数排序（可参考：基数排序的性能优化）。在此基础上，每一个数据都还伴随有一个属性，在排序过程中也要随之移动这个属性数据。一种可行方案是将数据和属性构成一个结构体，然后对结构体进行排序。在排序的过程中只有指针的移动，没有实际结构体的移动。这种方案涉及间接寻址，对现有代码改动较大，没有采用。

       我采用的方案是在原始快速排序和基数排序基础上做修改，每当出现元素交换时，就将对应的属性也进行交换。按这种思路实现的快速排序代码如下：

void q_sort_with_time(int* a,int *b,int left,int right)
{
    if(left>=right) return;

    int i=left,j=right+1;
    int pivot=a[left];
    int b_pivot=b[left];

    while(true)
    {
        do
        {
            i++;
        }while(i<=right&&a[i]<pivot);

        do
        {
            j--;
        }while(j>left&&a[j]>pivot);

        if(i>=j) break;

        swap(&a[i],&a[j]);
        swap(&b[i],&b[j]);
    }

    a[left]=a[j];
    a[j]=pivot;

    b[left]=b[j];
    b[j]=b_pivot;

    q_sort_with_time(a,b,left,j-1);
    q_sort_with_time(a,b,j+1,right);
}

void quick_sort_with_time(int* a,int* b,int n)
{
    q_sort_with_time(a,b,0,n-1);
}

const static int radix=1024;
static int p[]={0,10,20,30};

inline int get_part(int n,int i)
{
    return n>>p[i]&(radix-1);
}

void radix_sort_with_time(int* a,int* b,int n)
{
    int* bucket=(int*)malloc(sizeof(int)*n);
    int* b_bucket=(int*)malloc(sizeof(int)*n);
    int count[radix];

    for(int i=0;i<2;++i)
    {
        memset(count,0,sizeof(int)*radix);

        for(int j=0;j<n;++j)
        {
            count[get_part(a[j],i)]++;
        }

        for(int j=1;j<radix;++j)
        {
            count[j]+=count[j-1];
        }

        for(int j=n-1;j>=0;--j)
        {
            int k=get_part(a[j],i);
            bucket[count[k]-1]=a[j];
            b_bucket[count[k]-1]=b[j];
            count[k]--;
        }

        memcpy(a,bucket,sizeof(int)*n);
        memcpy(b,b_bucket,sizeof(int)*n);
    }

    free(bucket);
    free(b_bucket);
}

int equals(int* a,int* b,int* c,int* d,int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]!=b[i]) 
        {
            printf("1---%d: %d is not equal with %d\n",i,a[i],b[i]);
            return 0;
        }
        if(c[i]!=d[i]) 
        {
            printf("2---%d: %d is not equal with %d,%d:%d\n",i,c[i],d[i],a[i],b[i]);
            return 0;
        }
    }

    return 1;
}

void bubble_sort_with_time(int* a,int* b,int n)
{
    for(int i=n-1;i>0;i--)
    {
        for(int j=0;j<i;j++)
        {
            if(a[j]>a[j+1])
            {
                swap(&a[j],&a[j+1]);
                swap(&b[j],&b[j+1]);
            }
        }
    }
}

对于快排和基数排序，我开始认为是基数排序的算法实现错了，毕竟这个算法是首次使用。但是结果令我吃惊：冒泡排序的结果和基数排序的结果完全一致，反倒是快速排序和冒泡排序的结果不一致！太出乎意料了，问题找了半天没想到是出在自己擅长的快排上面。快排怎么可能会出错呢，毕竟用了这么久。很长时间内我也没有找到问题所在。后来我将equals方法修改了下，去掉return，把所有不匹配的数据都打印出来，一打印终于发现问题所在！

打印结果显示，错误总是出在两个值相同的元素间，一瞬间就明白怎么回事了：快速排序是不稳定排序，它可能会交换两个值相同的元素，所以这根本就不是一个bug。没想到debug两天原来是做的无用功。

为了能汲取教训，我又仔细分析了一下为什么快排是不稳定排序。出现不稳定的关键是两个do-while循环：

do
{
    i++;
}while(i<=right&&a[i]<pivot);

do
{
    j--;
}while(j>left&&a[j]>pivot);

两个循环在进行元素比较时，分别用了小于和大于操作（也可以改用小于等于和大于等于，但是对性能没有影响）。这就意味着如果出现和pivot值相同的元素，它都会被作为交换对象而移动到pivot的前面或者后面，这就出现了值相同的元素会交换顺序的问题，因而是不稳定的。

深入理解快速排序算法的稳定性,布布扣,bubuko.com

深入理解快速排序算法的稳定性

原文：http://blog.csdn.net/yutianzuijin/article/details/24778623