C语言排序方法——快速排序

本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

算法步骤：

• 1 从数列中挑出一个元素，称为 “基准”（pivot）。

• 2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

• 3 递归（recursive）的把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

C代码的实现如下：

void quickSort( int num[], int count, int left, int right )
{
    if( left >= right )
    {
        return ;
    }
    int key = num[left];
    int lp = left;                                //左下标
    int rp = right;                               //右下标
    while( lp < rp )
    {
        if( num[rp] < key )
        {
            int temp = num[rp];
            for( int i = rp - 1; i >= lp; i-- )
            {
                num[i + 1] = num[i];
            }
            num[lp] = temp;
            lp ++;
            rp ++;
        }
        rp --;
    }
    quickSort( num, count, left, lp - 1 );        //对左半部分排序
    quickSort( num, count, rp + 1, right );       //对右半部分排序
}

复制代码

下面开始单步分析，这里用一个数组的数据来分析

首先将0作为比较的基准，由于右边所有的数据都比0大，所以数据不做
移动。
接下来将8作为比较基准，从最右边开始和8比较。
此时6比8小，将6移动到8前面，其他数据依次后移。

接着在将2和8比较，2比8小，继续将2移动到8前面，其他的数据依次后移。

这样将8小的数据移动到8的前面，比8大的数据在8后面保持不变。移动完成后如下：

接下来比较的基准变为数字6，将比6小的数据移动到6前面。
从最右边开始查找，找到1比6小，将1移动到6前面。

然后继续依次寻找比6小的数字，移动到6的前面，移动完成后如下：

然后比较的基准变为数字5，从最右边开始寻找比5小的数移动到5前面。查找到的数据为2。

依次查找其他比5小的数据，移动完成后如下：

到这里可以看到数据排序已经完成了。
整体运行流程如下：

下面测试一下最坏情况下的排序情况

可以看到最坏情况下排序的次数并没有增多，反而感觉还减少了。
在看一下最好情况下的排序情况：

最好情况下数据也要进行比较9次。

下来随机生成一个包含10000个数字的数组，测试下执行时间。

可以看到对10000个数字排序需要的时间为120ms。

下面用一张动图来演示一下快速排序的过程