1、归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。

1.1、排序原理

  • 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是
    1 为止。
  • 将相邻的两个子组进行合并成一个有序的大组；
  • 不断的重复步骤 2 ，直到最终只有一个组为止。

image-20210906230251468

归并排序中，是在最后的合并阶段进行排序的。

1.2、API 设计

类名MergeSort
构造方法MergeSort()：构造 MergeSort 对象
成员方法1.public static void sort(int[] a)：对数组内的元素进行排序
2.private static void sort(int [] a, int low, int high)：对数组a中从索引lo到索引hi之间的元素进行排序
3.private static void merge(int [] a, int lo, int mid, int hi):从索引lo到所以mid为一个子组，从索引mid+1到索引hi为另一个子组，把数组a中的这两个子组的数据合并成一个有序的大组（从索引lo到索引hi）
4.private static void exch(int [] a,int i,int j)：交换a数组中，索引i和索引j处的值
成员变量private static int [] assist：完成归并排序操作所需要的辅助数组

1.3、归并原理

在归并排序中，数据的排序发生在数据的合并阶段，下面介绍一下数据合并过程中的排序过程

  • 以 arr = {5,6,7,2,8,9} 为例

此时 low = 0, high = 5, mid = low + (high - low) / 2 = 2

image-20210906234050748

辅助数组中元素情况与指针状态如下

image-20210906234313826

使用两个指针遍历两个数组，如果此时 p1 指针指向的元素的值小于 p2 指针指向的元素的值，那么将 p1 对应的元素放入到 assist 数组中，同时让 p1 和 assist 的指针后移一个单位。

如果 p2 对应的元素的值小于 p1 对应的元素的值，那么将 p2 对应的元素的值放入 assist 数组中，同时让 p2 指针和 assist 的指针后移一个位置。

在上面的图中，可以看到， p2 对应的元素 2 小于 p1 对应的元素 5 ，所以我们需要将 p2 对应的元素加入到 assist 数组中，然后令 p2 的指针和 assist 的指针后移一个单位。

  • 第一次填充

image-20210906235256347

同理，进行第二次填充，此时指针 p1 对应的元素小于 p2 对应的元素，将 5 加入到 assist 数组后，令 p1 与 assist 指针后移一个单位

  • 第二次填充

image-20210906235405052

以此类推，知道所有数据均被填充到 assist 数组为止。

  • 特殊情况

image-20210906235724501

如上图所示，当 p1 指针移动到 7 的位置时，此时左子组的指针已经达到末尾，同时右子组中的剩余数据已经保证有序，所以我们只需要将右子组的剩下的所有数据均填充到 assist 数组中即可。

这种思路类似在两个有序链表的排序中，如果一个链表已经遍历完成，那么只需要在合并后的链表的最后挂上那个未遍历完的链表的剩余元素即可。

  • 合并完成

合并完成后，我们需要将辅助数组 assist 中的下标从 [low,high] 的所有元素拷贝到原数组中即可。

image-20210907000107308

1.4、排序代码

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
public class MergeSort {

    /**
     * 完成归并排序所需要的辅助数组
     */
    private static int[] assist;



    /**
     * 对 arr 数组中的元素进行归并排序
     * @param arr
     */
    public static void sort(int [] arr) {
        //1 初始化辅助数组 assist，令 assist 数组的大小与待排序数组大小相同
        assist = new int[arr.length];
        //2 定义一个 low 变量和一个 high 变量，分别记录数组中最小的索引和最大的索引
        int low = 0;
        int high = arr.length - 1;
        //3 调用 sort 重载方法完成数组 arr 中，从索引 low 到 high 的元素的排序
        sort(arr, low , high);
    }

    /***
     * 对数组中下标从 low 到 high 的元素进行排序
     * @param arr
     * @param low
     * @param high
     */
    public static void sort(int[] arr, int low, int high) {
        //1 进行安全性校验
        if (arr == null || arr.length == 0 || low >= high) {
            return;
        }
        //2 对 low 到 high 之间的元素进行分组
        int mid = low + (high - low) / 2;
        //3 分组对每一组数据进行排序
        sort(arr, low , mid);
        sort(arr, mid + 1, high);
        //4 再把两个组中的数据进行归并
        merge(arr, low, mid , high);



    }

    /**
     * 对数组中的两组数组进行排序
     * 第一组数据为 [low, mid]
     * 第二组数据为 [mid + 1, high]
     * @param arr
     * @param low
     * @param mid
     * @param high
     */
    public static void merge(int[] arr, int low, int mid, int high) {
        //1 定义三个指针，第一个指针 p1 指向low，即左子数组的首元素
        int leftPoint = low;
        // 第二个指针 p2 指向 mid + 1 ，即右子数组的首元素
        int rightPoint = mid + 1;
        // 第三个指针 p 指向 low
        int assistPoint = low;
        //2 循环比较 p1 与 p2 对应值的大小，将对应较小的元素放入到 assist 数组中，然后令指向较小的值的指针和 assist 数组的指针向后移
        while (leftPoint <= mid && rightPoint <= high) {
            if (arr[leftPoint] < arr[rightPoint]) {
                // 如果 p1 指向的元素小于 p2 指向的元素，那么将 p1 指向的元素放入 assist 数组中
                assist[assistPoint] = arr[leftPoint];
                leftPoint++;
            } else {
                assist[assistPoint] = arr[rightPoint];
                rightPoint++;
            }
            // 别忘了让辅助数组的指针后移
            assistPoint++;
        }
        //3 如果上一步执行完成后， p1 指针还没有走到最后，那么遍历 左子数组中未遍历的元素，将其填充到 assist 数组对应的位置中
        while (leftPoint <= mid) {
            assist[assistPoint++] = arr[leftPoint++];
        }
        //4 同理，如果 p2 还未走完，那么遍历右子数组中没有完成的元素
        while (rightPoint <= high) {
            assist[assistPoint++] = arr[rightPoint++];
        }
        //5 将辅助数组中下标符合 [low, high] 的元素拷贝到原数组中
//        if (high + 1 - low >= 0) {
//            System.arraycopy(assist, low, arr, low, high + 1 - low);
//        }
        for (int index = low; index <= high; index++) {
            arr[index] = assist[index];
        }
    }

1.5、测试

1
2
3
4
5
public static void main(String[] args) {
    int[] arr = {1,4,2,6,-1,128,-123,111};
    sort(arr);
    System.out.println(Arrays.toString(arr));
}

image-20210907084646734

2、堆排序（不稳定）

2.1、什么是堆？

堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

  • 堆中某个结点的值总是不大于或不小于其父结点的值；

将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。

和 BST 不一样，在大顶堆中，根节点的值大于/等于它的左右子树的值，在小顶堆中，根节点的值小于 / 等于它的左右子树的值，没有对结点的左右孩子结点的大小关系做要求。

  • 堆总是一棵完全二叉树。

完全二叉树：一棵深度为 k 的有 n 个结点的二叉树，对树的结点从上到下，从左到右的顺序进行编号，如果编号为 i (1 <= k <= n) 的结点与满二叉树中编号为 i 的结点在二叉树的位置相同，那么称这棵树为完全二叉树。

2.2、堆排序基本介绍

  • 堆排序就是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏、最好，平均时间复杂度均为 O(nlogn)，堆排序是不稳定排序

  • 大顶堆举例说明

image-20210912222622558

我们对堆中元素进行从上到下，从左到右的编号，放在一个数组中，此时对于编号为 i 的根节点来说，它的左子结点是 2 * i + 1 ，右子节点是 2 * i + 2，故大顶堆的性质有：arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2] (i 从 0 开始编号)

  • 小顶堆举例说明

image-20210912222645955

同理，小顶堆的性质为 arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2]

  • 一般来说，升序使用大顶堆，而降序使用小顶堆。

2.3、堆排序基本思想

堆排序的基本思想如下

  • 将待排序序列构造成一个大顶堆
  • 此时，整个序列的最大值就是堆顶的根节点
  • 将根节点与末尾元素进行交换，此时末尾为最大值。
  • 然后将剩余 n - 1 个元素重新构造成一个堆，这样就会得到 n 个元素的次小值。如此反复，即可得到一个有序序列。

每次构造大顶堆时，可以看到构造大顶堆的元素逐渐减少，最后得到一个有序序列。

2.4、图解

给定一个数组 {4,6,8,5,9}，要求使用排序法，将数组升序排序。

  • 假定原有的序列如下 {4,6,8,5,9}，构造而成的堆为

image-20210912224030575

  • 此时我们从最后一个非叶子结点开始，第一个非叶子结点的推导公式为 arr.length / 2 - 1 = 5 / 2 - 1 = 1，然后从左到右，从上到下进行调整

此时将 5 6 9 构成的堆构造成一个大顶堆，将 6 与 9 互换

image-20210912224227812

  • 找到第二个非叶子结点 4 ，由于 4 9 8 中 9 最大，所以让 9 和 4 交换

image-20210912224347337

  • 交换后 4 5 6 构成的子堆混乱，此时需要继续调整，让 6 与 4 交换位置

image-20210912224440097

这样我们就将一个无序序列构造成了一个大顶堆。

  • 这个时候将堆顶元素 9 与数组最后一个元素进行交换

此时 9 就脱离了数组，剩下的就是将序列 4 6 8 5 建成堆，然后交换，最后得到一个有序序列。

image-20210912224539115

2.5、代码实现

在堆排序中，我们需要先建堆，然后再进行排序，这里以升序排序为例

  • 用于调整堆的方法
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
/**
 * 将一个数组（二叉树），调整成一个大顶堆
 * 将以 i 对应的非叶子节点的数调整成一个大顶堆
 * 举例：原来的树如下
 *      4                                     4
 *     / \  当传入的 i = 1 时                 / \
 *    6  8  我们将 6 这个非叶子节点            9  8
 *   / \    对应的树(659)调整为一个大顶堆     / \
 *  5   9                                5   6
 *
 * 如果我们再次调用 adjustHeap ，那么传入的 i 为 0
 * @param arr 待调整数组
 * @param i 表示非叶子节点在数组中的索引
 * @param length 对多少个元素继续进行调整，length 是在逐渐减少的
 */
private static void adjustHeap(int[] arr, int i, int length) {
    // 使用 maxIndex 变量保存当前待调整非叶子节点下标 i
    // maxIndex 用于保存该非叶子节点和它的左右节点中最大值的下标
    // 比如说 arr[i] > arr[i * 2 + 1] > arr[i * 2 + 2]
    // 那么 maxIndex = i
    // 如果说 arr[i * 2 + 1] > arr[i] > arr[i * 2 + 2]
    // 那么 maxIndex = i * 2 + 1
    int maxIndex = i;
    // 根据堆的性质，获取它的左右子树节点下标
    int leftChildren = i * 2 + 1;
    int rightChildren = i * 2 + 2;
    // 找到非叶子节点 i 和它左右子树中值最大的那个下标，然后将这个下标赋给 maxIndex
    if (leftChildren < length && arr[maxIndex] < arr[leftChildren]) {
        maxIndex = leftChildren;
    }
    if (rightChildren < length && arr[maxIndex] < arr[rightChildren]) {
        maxIndex = rightChildren;
    }
    // 如果发现三者（非叶子节点 i 、左右孩子节点中不是 i 最大，那么我们需要将 i 对应的值变为最大）
    if (i != maxIndex) {
        swap(arr, i, maxIndex);
        // 交换后，我们需要维护交换后子堆的性质
        adjustHeap(arr, maxIndex, length);
    }
}
  • 进行堆排序的方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 不稳定！
 * 时间复杂度：
 * O(NlogN)，其中建堆复杂度为 O(N)，而调整堆（adjustHeap）的时间复杂度为 O(logN)
 * 我们需要对 N 个数进行 adjustHeap
 * @param arr
 * @param length
 */
public static void heapSort(int[] arr, int length) {
    //1 建堆
    for (int i = (length / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i ,length);
    }
    //2 排序
    for (int i = length - 1; i > 0; i--) {
        swap(arr, i , 0);
        adjustHeap(arr, 0 , i);
    }

}
  • swap 方法，这个方法用于交换数组中索引 i 与索引 j 的元素
1
2
3
4
5
6
7
8
9
10
11
/**
 * 交换数组中下标 i 与 j 的值
 * @param arr
 * @param i
 * @param j
 */
public static void swap (int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

3、排序稳定性

3.1、稳定性的定义

数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保证A元素依然在B元素的前面，可以说这个该算法是稳定的。

  • 对于数列 {3,2,4,1,4,5}

image-20210913231925203

  • 排序后

image-20210913231952950

3.2、稳定性的定义

如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。

例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。

3.3、常见算法的稳定性

  • 冒泡排序：稳定

只有当arr[i]>arr[i+1]的时候，才会交换元素的位置，而相等的时候并不交换位置，所以冒泡排序是一种稳定排序算法。

  • 选择排序：不稳定

选择排序是给每个位置选择当前元素最小的,例如有数据{5(1)，8，5(2)，2，9 },第一遍选择到的最小元素为2，所以5(1)会和2进行交换位置，此时5(1)到了5(2)后面，破坏了稳定性，所以选择排序是一种不稳定的排序算法。

  • 插入排序：稳定
  • 希尔排序：不稳定
  • 快速排序：不稳定
  • 归并排序：稳定

归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。

  • 堆排序：不稳定

总结：

稳定算法冒泡算法、插入排序、归并排序
不稳定算法选择排序、希尔排序、快速排序、堆排序

4、常见排序算法时间复杂度说明

排序算法最坏情况最好情况平均时间复杂度
冒泡排序O(n ^ 2)O(n)O(n ^ 2)
选择排序O(n ^ 2)O(n ^ 2)O(n ^ 2)
插入排序O(n ^ 2)O(n)O(n ^ 2)
快速排序O(n ^ 2)O(nlogn)O(nlogn)
归并排序O(nlogn)O(nlogn)O(nlogn)
堆排序O(nlogn)O(nlogn)O(nlogn)
希尔排序O(nlog^2 n)O(nlog^2 n)O(nlogn)