快速排序的代码实现和复杂度分析

1. 原理简介

快速排序是冒泡排序的一种改进算法，由C. A. R. Hoare在1960年提出。其基本思想是通过一趟排序将数据切割成两部分，两部分数据以某个值为划分点。一部分全部大于此划分点，一部分全部小于此划分点。这样的划分点又称为Pivot。

基本流程如下：

1. 设定一划分值将数组分为两部分
2. 将大于此划分值的数据全部放到右边，小于此划分值的全部放到左侧
3. 对两侧的数据分别独立排序，此排序使用上述相同的方法
4. 递归排序完所有的子数据

2. C语言简单实现

介绍一种简单的C语言实现方法。

void QuickSort(int *a, int n)
{
    //第一步确定递归边界，当子数组仅有一个元素时退出此层递归
    if ( n<2 )
        return;
    int i,j;
    //第二步确定Pivot(还有其他划分方法，这里直接取中点位置)
    int p = a[n/2];
    //第三步遍历数组，将左侧和右侧数据归类
    //这里for循环是必要的，由于两侧数据中不止存在一个大于或小于p的数据
    for (i=0, j=n-1; ; i++, j--)
    {
        //一直遍历直到寻得大于p的元素
        while(a[i]<p)
            i++;
        //一直遍历直到寻得小于p的元素
        while(a[j]>p)
            j--;
        //当i与j相遇时，说明遍历结束退出循环
        if ( i>=j )
            break;
        swap(&a[i],&a[j]);
    }
    //递归排序左侧数据
    QuickSort(a,i);
    //递归排序右侧数据
    //由于循环退出条件是i和j相遇，那么i的位置一定是左侧数组最右端
    QuickSort(a+i,n-i);
}

下面是利用随机模拟数据的试验结果：

3. 时间复杂度分析

本文介绍两种方法来分析快速排序的时间复杂度。

第一种方法利用了主定理(Master Theorem)，其表述如下：T(n)可以称之为时间期望。

在快速排序中，f(n)即为两侧数据归类的过程，不难知f(n)=O(n)。假设子问题规模一样，那么理想情况下a=2, b=2为最佳分割，有如下公式：

T[n] = 2T[n/2] + O(n)

通过计算得知：T[n] = O(nlogn)

快速排序的时间复杂度只能无限趋近于此值。

极端情况下，即某次划分导致左侧为一个数据，右侧为n-1个。那么这种划分下的快速排序实质上为冒泡排序，即：

T[n] = T[n-1] + T[1] + O(n)

那么很容易得到T[n] = O(n*n)

除主定理外还有其他的数学方法，如：

该解法来自于知乎用户：芾棠

Reference List:

1.C语言实现快速排序 - Landpack - 博客园 (cnblogs.com)

2.快速排序算法的时间复杂度分析[详解Master method] - 简书 (jianshu.com)