快速排序

要想学习快速排序，前提必须了解 递归算法

概况

快速排序是一种高效的排序算法，它采用了分治的策略。

基本思想是选择一个基准数，通过一趟排序将待排序序列划分成两个子序列，其中一个子序列的所有元素小于基准数，另一个子序列的所有元素大于基准数。然后对这两个子序列递归地应用快速排序算法，直到子序列的长度为1或0，即达到最终的排序结果。

快速排序是一种原地排序算法，它的平均时间复杂度为O(nlogn)，其中n是待排序序列的长度。但在最坏情况下，即待排序序列已经有序或近乎有序时，快速排序的时间复杂度为O(n^2)，这是因为每次划分都只能减少一个元素的位置。

步骤

其基本步骤如下：

1. 选择一个基准数（通常是序列的第一个元素）。

2. 定义两个指针，一个指向序列的起始位置，另一个指向序列的末尾位置。

3. 从右向左移动右指针，直到找到一个小于基准数的元素。

4. 从左向右移动左指针，直到找到一个大于基准数的元素。

5. 交换左右指针所指向的元素。

6. 重复步骤3、4、5，直到左指针和右指针相遇。

7. 将基准数和左指针所指向的元素进行交换，使得基准数归位。

8. 对基准数左边的子序列和右边的子序列递归应用以上步骤，直到子序列的长度为1或0。

9. 完成排序后，序列就被分成了若干个以基准数为中心的子序列，子序列的元素都已经有序。

代码示例

需求：采用快速排序将下列数据进行排序，数据如下{6, 2, 6, 3, 9, 4, 7, 8, 5, 1, 10}

例如：

package text.text02;

/*
快速排序：
            以0索引的数字为基准数，确定基准数在数组中正确的位置。
            比基准数小的全部在左边，比基准数大的全部在右边。
            后面以此类推。
步骤：
    1. 从数列中挑出一个元素，一般都是左边第一个数字，称为 "基准数";
    2. 创建两个指针，一个从前往后走，一个从后往前走。
    3. 先执行后面的指针，找出第一个比基准数小的数字
    4. 再执行前面的指针，找出第一个比基准数大的数字
    5. 交换两个指针指向的数字
    6. 直到两个指针相遇
    7. 将基准数跟指针指向位置的数字交换位置，称之为：基准数归位。
    8. 第一轮结束之后，基准数左边的数字都是比基准数小的，基准数右边的数字都是比基准数大的。
    9. 把基准数左边看做一个序列，把基准数右边看做一个序列，按照刚刚的规则递归排序
 */
public class text15A {
    public static void main(String[] args) {
        int[] arr = {6, 2, 6, 3, 9, 4, 7, 8, 5, 1, 10};
        //调用quickSort方法
        quickSort(arr, 0, arr.length - 1);
        //遍历数组输出数组数据
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");      //1  2  3  4  5  6  6  7  8  9  10
        }
    }

    //创建快速排序方法quickSort
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        //定义变量接受startIndex和endIndex，方便以后递归
        int i = startIndex;
        int j = endIndex;

        //起始索引大于结束索引，说明遍历完成，结束方法（出口）
        if (startIndex > endIndex) {
            return;
        }

        //定义个变量记录基准数
        int number = arr[startIndex];

        //当起始索引小于结束索引时
        while (startIndex < endIndex) {
            //当起始索引小于结束索引并且从右向左遍历时的某个数大于基准数时
            while (startIndex < endIndex && arr[endIndex] >= number) {
                endIndex--;
            }

            //当起始索引小于结束索引并且从左向右遍历时的某个数小于基准数时
            while (startIndex < endIndex && arr[startIndex] <= number) {
                startIndex++;
            }

            //将从右向左遍历时大于基准数的某个数与从左向右遍历时小于基准数的某个数进行交换
            int temp = arr[endIndex];
            arr[endIndex] = arr[startIndex];
            arr[startIndex] = temp;
        }
        //当起始索引与结束索引相等时，将其对应的数与基准数进行交换
        int num = arr[startIndex];
        arr[startIndex] = number;
        arr[i] = num;

        //在基准数左边的数接着递归调用该方法
        quickSort(arr, i, startIndex - 1);
        //在基准数右边的数接着递归调用该方法
        quickSort(arr, startIndex + 1, j);
    }
}

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

输出结果

流程图：

开始
├─ 定义快速排序方法 quickSort
│    ├─ 如果起始索引大于结束索引，返回
│    ├─ 选择数组中的一个元素作为基准数
│    ├─ 定义指针 i 指向起始索引
│    ├─ 定义指针 j 指向结束索引
│    ├─ 循环直到指针 i 和 j 相遇
│    │    ├─ 从右向左移动指针 j，找到一个比基准数小的数字
│    │    ├─ 从左向右移动指针 i，找到一个比基准数大的数字
│    │    ├─ 如果指针 i 和 j 没有相遇
│    │    │    ├─ 交换指针 i 和指针 j 指向的数字
│    ├─ 交换基准数与指针 i 指向的数字，基准数归位
│    ├─ 递归调用 quickSort 方法，对基准数左边的序列进行排序
│    ├─ 递归调用 quickSort 方法，对基准数右边的序列进行排序
├─ 创建数组 arr
├─ 调用 quickSort 方法，对数组 arr 进行排序
├─ 遍历数组 arr，输出排序后的数据
结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18