快速排序

发表于 | 分类于

快速排序算是我接触的第一个排序速度比较快的算法，之前一直也没有写快排的博客，闲来无事，就算温习一下了。

快排的原理

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。(来自wiki百科)

quick_sort

我们首先设置一个哨兵，为了方便，就设置第一个为哨兵（这里哨兵的设置对快排的性能也有影响），然后设置两个指针，分别指向数组的首地址和尾地址，这两个数分别和哨兵进行比较，比哨兵大的放它右边，比哨兵小的放它左边，最终不仅能确定这个哨兵在该数组的位置，并且将数组分割成三部分，一个是排好序的，另外分别是比哨兵大的和比哨兵小的三部分。然后再用递归，对未排序好的两部分做同样的操作。

quick_sort1

实现代码

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
40
41
42
43
44
45
46
47
48
public int change(int[] arr,int l,int r){
    /**
     * 设置哨兵
     */
    int guard = arr[l];
    /**
     * 设置指针指向数组的首尾元素
     */
    int i = l, j = r;
    while(i<j){
        /**
         * 先从j开始比较
         */
        while (i < j && arr[j] >= guard){
            j--;
        }
        /**
         * 当j指向的元素比哨兵大的时候，将j指向的元素
         * 赋值给i指向的位置,i++,但是要保证i<j
         */
        if (i<j){
            arr[i++] = arr[j];
        }
        /**
         * 现在开始从i指向的位置与哨兵比较
         */
        while(i < j && arr[i] < guard){
            i++;
        }
        if(i < j){
            arr[j--] = arr[i];
        }
    }
    /**
     * 将哨兵的值赋给最后一个空缺的位置
     */
    arr[i] = guard;
    return i;
}

public void quick_sort(int[] arr, int l,int r){
    if (l<r){
        int boundry;
        boundry = change(arr,l,r);
        quick_sort(arr,l,boundry-1);
        quick_sort(arr,boundry+1,r);
    }
}

这里需要解释的是change()函数里为什么要这么多$i<j$,因为有一些特殊情况需要应对。
举个例子，比如[1 2 3 4 5 6],这是已经排好序的数组了，当执行比较的while循环时，如果不限制$i<j$,会下标越界。

时间复杂度

在change函数里，对数据进行一次排序，需要$O(n)$,而又需要递归，所以得出下面的递推公式：

这里证明太过复杂，使用递归树可能比较好理解。