数据结构与算法 12 快速排序（快排）_对12个数进行快速排序

3.7 快速排序（快排）

---

快速排序是对 冒泡排序 的一种 改进。它的基本思想是∶通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序， 整个排序过程可以递归进行， 以此达到整个数据变成有序序列。
快排 和 归并排序 是相似的，不同的是 归并排序是直接分组，而快排是有要求的进行分组。但快排 没有所谓的 辅助数组，所以要比 归并排序省一部分空间。

• 需求:
  排序前:{6,1,2,7,9,3,4,5,8}
  排序后:{1,2,3,4,5,6,7,8,9}

• 排序原理∶

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分;
2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值;
3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右边的数组数据也可以做类似处理。
4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

• 快速排序 API 设计：
  
• 切分原理：

把一个数组切分成两个子数组的基本思想：

1. 找个基准值，用两个指针分别指向数组的头部和尾部;
2. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置;
3. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置;
4. 交换当前左边指针位置和右边指针位置的元素;
5. 重复2,3.4步骤，直到左边指针的值大于右边指针的值时，我们才停止搜索。

• 解决二元素一组问题和需要注意的事项

6. 为什么要解决 二元素一组问题呢？因为 在实际的 程序操作中，我们会发现 指针 对于 二元素一组的 搜索是可能存在 left > right 的情况。因为两个元素的时候，基准值就是第一个元素，这个时候是比较特殊的。我们需要在草稿纸上写一写，画一画，找到 一些 特殊情况判断的解决方法。
7. right 再不断的 递减，那么在 递减的时候 就必须 用 一个 if 的语句 保证，right 不能 减到 低于 hi 初始的位置。
8. left 再不断的 递增，那么在 递增的时候 就必须 用 一个 if 的语句 保证，left 不能 增到 高于 hi 最高的位置。
9. 我们必须知道的是，无论发生什么 特殊的情况，最终 lo 位置 和 right 位置进行 交换 肯定是不会错的！！这也是 必然情况。因为 我们的基准值 就在 最左侧。而 right < left 的时候，往往 就是 来到了 基准值的位置（即特殊情况。）。
10. 在指针搜索的时候，如果一旦 遇到了 left >= right 的情况 就有 极大的几率 是 left > right 所以 必须 直接 break 出去，让 lo 和 right 进行交换！即可完成 特殊情况和 正常情况的所有处理。
11. 如果 想把 正常情况 和 特殊情况 都 包含进来！那么我们就需要 利用 最外层的 死循环。否则 循环写死了，那就完了，可能会 少一些情况。

• 快速排序 算法代码

package com.muquanyu.algorithm.sort;

public class Quick {
    /*
    比较 元素 v 是否 小于 元素 w
     */
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }

    /*
    数组元素 i 和 j 交换位置
     */
    private static void exch(Comparable[] a,int i,int j)
    {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    /*
    对数组 a 中的元素 进行排序
     */
    public static void sort(Comparable[] a)
    {
        int lo = 0;
        int hi = a.length - 1;
        sort(a,lo,hi);
    }

    /*
    对数组 a 中 从 lo 到 hi 的元素 进行排序
     */
    private static void sort(Comparable[] a,int lo,int hi)
    {
        //安全性校验
        if(lo > hi)
        {
            return;
        }
        //切记：partation 返回的索引是 分组后的 分界值 索引
        int partation = partation(a,lo,hi);

        //让左子组有序
        sort(a,lo,partation-1);

        //让右子组有序
        sort(a,partation+1,hi);


    }

    private static int partation(Comparable[] a,int lo,int hi)
    {
        Comparable key = a[lo];
        //设定两个指针
        int left = lo;
        int right = hi + 1;

        while(true)
        {
            while(less(key,a[--right]))
            {
                if(right == lo)
                {
                    break;
                }
            }
            while(less(a[++left],key))
            {
                if(left == hi)
                {
                    break;
                }
            }
            if(left >= right)
            {
                break;
            }else{
                exch(a,left,right);
            }
        }

        /*while(true)
        {
            while(less(key,a[right]))
            {
                if(right == lo)
                {
                    break;
                }
                right--;
            }
            while(less(a[left],key))
            {
                if(left == hi)
                {
                    break;
                }
                left++;
            }
            if(left >= right)
            {
                break;
            }
            exch(a,left,right);
        }*/
        exch(a,lo,right);
        return right;
    }
}

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

• 快速排序 算法测试

package com.muquanyu.algorithm.test;

import com.muquanyu.algorithm.sort.Quick;

import java.util.Arrays;

public class QuickTest {
    public static void main(String[] args) {
        Integer[] arr = {6,1,2,7,9,3,4,5,8};
        Quick.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 快速排序和归并排序的区别:

快速排序是另外一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序是互补的:归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。

• 快速排序时间复杂度分析:

快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为o(n),但整个快速排疗的时间复杂度和切分的次数相关。
最优情况∶每一次切分选择的基准数字刚好将当前序列等分。

反正 我在 测快排的时候挺慢的，没有 希尔排序 和 归并排序快！也不知为啥，差了将近 10倍，而且 好像是 递归 压栈的事，10w条 逆序数据，就处理不了了！直接 就提示栈溢出了。

但是 官方说 快排的 时间复杂度 是 O(n) = n lgn