快速排序

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

快排的思路

快速排序采用了分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：

1. 选取一个基准元素（pivot）
2. 分区过程，比pivot小的放到pivot左边，比pivot大的放到pivot右边
3. 对pivot左边的序列和右边的序列分别递归的执行步骤1和步骤2

虽然是采用分治法，但是分治法不能完全概括这个算法，因为我每次看完算法会很清楚，但是过段时间就忘了。然后看到了非常新颖的名字：“挖坑排序”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

//快速排序
void quickSort(int s[], int l, int r)
{
    if (l < r)
    {
        int i = l, j = r;
        //将数组中的最低位值取出，相当于挖了第一个坑
        int x = s[l];
        while (i < j)
        {
            while(i < j && s[j] >= x) {
            //从右向左找第一个小于x的数
				j--;  
			}
            if(i < j) {
            //将s[j]的数挖坑填之前的坑
				s[i++] = s[j];
			}
			
            while(i < j && s[i] < x) {
            // 从左向右找第一个大于等于x的数
				i++;  
			}
            if(i < j) {
            //挖坑，填之前的坑
				s[j--] = s[i];
			}
        }
        //填最后一个坑
        s[i] = x;
        quickSort(s, l, i - 1); // 递归调用 
        quickSort(s, i + 1, r);
    }
}

对挖坑填数进行总结

1. i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2. j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3. i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4. 再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

算法分析

平均情况下快速排序的时间复杂度是O(n\lgn)O(n\lgn)，最坏情况是O(n2)O(n2)。

最坏时间复杂度

当划分产生的两个子问题分别包含 n-1 和 0个元素时，最坏情况发生。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：
Cmax = n(n-1)/2=O(n^2)

最好时间复杂度

当划分产生的两个子问题分别包含⌊n/2⌋⌊n/2⌋和⌈n/2⌉−1⌈n/2⌉−1个元素时，最好情况发生。用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为O(lgn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数C(n)=O(nlgn)。

因为快速排序的记录移动次数不大于比较的次数，所以快速排序的最坏时间复杂度应为0(n2)，最好时间复杂度为O(nlgn)。事实上只要划分是常数比例的，算法的运行时间总是O(nlgn)。 假设按照 9:1 划分，每层代价最多为 cn，递归深度为 log(10/9, n)=O(lgn)，故排序的总代价为O(nlgn)。平均情况下，比如一次坏的划分接着一次好的划分，坏的划分那一项可以合并到好的划分里，统计上来讲平均情况下的时间复杂度仍然是O(nlgn)。

优化

在当前无序区中选取划分的基准关键字是决定算法性能的关键。

1. “三者取中”规则，即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准
2. 取位于low和high之间的随机数k(low≤k≤high)，用R[k]作为基准， 随机化的快速排序与一般的快速排序算法差别很小。但随机化后，算法的性能大大地提高了，尤其是对初始有序的文件，一般不可能导致最坏情况的发生。

参考

白话经典算法系列之六 快速排序 快速搞定
快速排序的时间和空间复杂度
快速排序算法分析

本文链接： http://w4lle.com/2016/07/03/快速排序/

版权声明：本文为 w4lle 原创文章，可以随意转载，但必须在明确位置注明出处！
本文链接： http://w4lle.com/2016/07/03/快速排序/