快速排序（QuickSort）是对冒泡排序的一种改进。由 C. A. R. Hoare 在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法过程

设要排序的数组是 A[0] …… A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

1. 设置两个变量 I、J，排序开始的时候：I = 0，J = N - 1；
2. 以第一个数组元素作为关键数据，赋值给 key，即 key = A[0]；
3. 从 J 开始向前搜索，即由后开始向前搜索（ J = J - 1），找到第一个小于 key 的值 A[ J ] ，并与 A[ I ] 交换；
4. 从 I 开始向后搜索，即由前开始向后搜索（ I = I + 1 ），找到第一个大于 key 的 A[ I ]，与 A[ J ] 交换；
5. 重复第3、4、5步，直到 I = J； (3,4步是在程序中没找到时候 j = j - 1，i = i + 1，直至找到为止。找到并交换的时候 i， j 指针位置不变。另外当 i = j这过程一定正好是i+或j-完成的最后另循环结束)

上面这种算法的描述理解起来有点绕（通过Java代码做了示例），但是这种算法通过交换的方式节省了空间。在现在内存空间比较大的情况下，可以考虑下面这种算法（通过Python代码做了示例）：

1. 从数组 A 中取一个中间值 t，创建两个数组B、C，一个（B）用来存放小于 t 的数据，另一个（C）用来存放大于 t 的数据。
2. 遍历数组 A 并与中间值 t 进行比较，将小于中间值的数据放入数组 B，将大于中间值的数据放入数组 C。
3. 对数组 B、C 按照1、2步进行排序。
4. 将 B、t、C组合后输出为排序后的结果。

Java示例

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
35
36
37
38
39

class QuickSort {
    public static int[] qsort(int arr[], int start, int end){
        int refNumber = arr[start];
        int i = start;
        int j = end;

        while( i < j ){
            while( (i < j) && (arr[j] > refNumber) ){
                j--;
            }
            while( (i < j) && (arr[i] < refNumber) ){
                i++;
            }

            if( (arr[i] == arr[j]) && (i < j)){
                i++;
            }else{
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        if( i - 1 > start) arr = qsort(arr, start, i - 1);
        if( j + 1 < end ) arr = qsort(arr, j + 1 ,end);

        return arr;
    }

    public static void main(String[] args){
        int arr[] = new int[]{ 5, 10, 2, 15, 21, 99, 3, 1, 17, 23, 1, 35};
        int len = arr.length - 1;
        arr = qsort(arr, 0, len);

        for(int i:arr){
            System.out.print(i + "\t");
        }
    }
}

Python示例

这个算法使用的数组支持不定长，对于其他语言来说不一定适用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# -*- coding: utf-8 -*-
def quick_sort(data):
    if len(data) >= 2:          # 递归入口及出口        
        mid = data[0]           # 选取基准值，也可以选取第一个或最后一个元素        
        left, right = [], []    # 定义基准值左右两侧的列表        
        data.remove(mid)        # 从原始数组中移除基准值        
        for num in data:            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data
 
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array))
# 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]

算法变种

快速排序(Quicksort)有几个值得一提的变种算法，这里进行一些简要介绍：

• 随机化快排：快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下，每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法，即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2)，但最坏情况不再依赖于输入数据，而是由于随机函数取值不佳。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结：“随机化快速排序可以满足一个人一辈子的人品需求。”
• 平衡快排（Balanced Quicksort）：每次尽可能地选择一个能够代表中值的元素作为关键数据，然后遵循普通快排的原则进行比较、替换和递归。通常来说，选择这个数据的方法是取开头、结尾、中间3个数据，通过比较选出其中的中值。取这3个值的好处是在实际问题（例如信息学竞赛……）中，出现近似顺序数据或逆序数据的概率较大，此时中间数据必然成为中值，而也是事实上的近似中值。万一遇到正好中间大两边小（或反之）的数据，取的值都接近最值，那么由于至少能将两部分分开，实际效率也会有2倍左右的增加，而且利于将数据略微打乱，破坏退化的结构。
• 外部快排（External Quicksort）：与普通快排不同的是，关键数据是一段buffer，首先将之前和之后的M/2个元素读入buffer并对该buffer中的这些元素进行排序，然后从被排序数组的开头（或者结尾）读入下一个元素，假如这个元素小于buffer中最小的元素，把它写到最开头的空位上；假如这个元素大于buffer中最大的元素，则写到最后的空位上；否则把buffer中最大或者最小的元素写入数组，并把这个元素放在buffer里。保持最大值低于这些关键数据，最小值高于这些关键数据，从而避免对已经有序的中间的数据进行重排。完成后，数组的中间空位必然空出，把这个buffer写入数组中间空位。然后递归地对外部更小的部分，循环地对其他部分进行排序。
• 三路基数快排（Three-way Radix Quicksort，也称作Multikey Quicksort、Multi-key Quicksort）：结合了基数排序（radix sort，如一般的字符串比较排序就是基数排序）和快排的特点，是字符串排序中比较高效的算法。该算法被排序数组的元素具有一个特点，即multikey，如一个字符串，每个字母可以看作是一个key。算法每次在被排序数组中任意选择一个元素作为关键数据，首先仅考虑这个元素的第一个key（字母），然后把其他元素通过key的比较分成小于、等于、大于关键数据的三个部分。然后递归地基于这一个key位置对“小于”和“大于”部分进行排序，基于下一个key对“等于”部分进行排序。

参考资料

1. http://baike.baidu.com/view/19016.htm