快速排序(Quick Sort)

快速排序(Quick Sort) 1960年由 查尔斯.安东尼.理查德.霍尔提出。

执行流程
  • 随机选择一个为数列的轴点元素
  • 遍历数组，把小于轴点的元素，放在轴点的左边
  • 把大于轴点的元素，放在轴点的右边
  • 遍历完后，分别对轴点元素左右两边，都执行以上操作
快速排序 - 时间复杂度
  • 在轴点左右元素比较均匀的情况下，同时也是最好的情况
    • 时间复杂度为 : O(N * log N)
  • 如果轴点元素数量极度不均匀，最坏情况
    • 时间复杂度为 : O(N ^ 2)
  • 为了降低最坏情况的出现概率，一般采取的做法是
    • 随机选择轴点元素
  • 最好，平均时间复杂度都是 : O(N * log N)
  • 最坏时间复杂度 : O(N ^ 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

 
 /*
    * 交换，array i 和 j位置的元素
    * */
    protected void swap(int i1, int i2){
        swapcount ++;

        int tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }

    /*
    * 比较两个下标的元素
    * 返回值等于0 , 代表array[i1] == array[i2]
    * 返回值 < 0,  代表array[i1] < array[i2]
    * 返回值 > 0,  代表array[i1] > array[i2]
    * */
    protected int cmp(int i1, int i2){
        cmpcount ++;
        return array[i1] - array[i2];
    }

 @Override
    protected void sort() {
        sort(0, array.length);
    }

    private void sort(int begain ,int end){
        // 至少有两个元素
        if (end - begain < 2) return;

        int mid = pivotIndex(begain, end);
        sort(begain, mid);
        sort(mid + 1, end);
    }

    int pivotIndex(int begain ,int end){

        int tmp = array[begain];
        boolean isright = true;

        end --;
        while (begain < end){
            // 从右往左找
            if (isright){
                if (array[end] > tmp){
                    end --;
                }else {
                    array[begain ++] = array[end];
                    isright = false;
                }
            }else{
                // 从左往右找
                if (array[begain] < tmp){
                    begain ++;
                }else {
                    array[end --] = array[begain];
                    isright = true;
                }
            }
        }

        array[begain] = tmp;
        return begain;
    }