常见排序算法

## 简单选择排序

### 算法原理

1. 简单排序算法的基本思想为**每一趟从待排序的数据元素中选择最小（最大）的一个元素作为首元素，直到所有元素排完为止**。

### 参考代码

1. 在算法实现时，每一趟确定最小元素的时候会通过**不断地比较交换**来使得**首位置为当前最小**。
2. **交换是个比较耗时的操作**，其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。
3. 我们可以通过设置一个变量 `minInd`，每一次比较仅存储较小元素的数组下标，当这一轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/5/3 20:52
 * @Description 简单选择排序算法
 */
public class SimpleSelectionSort {
    public static void sort(int[] arr) {
        int m = arr.length;
        for (int i = 0; i < m - 1; i++) {
            int minInd = i;
            for (int j = minInd + 1; j < m; j++) {
                //  只记录最小元素的位置，而不是每一次比较都交换，减少交换的次数
                if (arr[minInd] > arr[j]) {minInd = j;}
            }
            if (minInd != i) {
                //  如果当前位置 i 不是这一次的最小元素，再交换元素的位置
                CommonUtils.swap(arr, i, minInd);
            }
        }
    }
}
```

### 算法分析

1. 简单排序算法无论数组原始排列如何，比较次数是不变的；对于交换操作，在最好情况下也就是数组完全有序的时候，无需任何交换移动，在最差情况下，也就是数组倒序的时候，交换次数为 `n-1` 次，综合下来，时间复杂度为 $O(n^2)$。
2. 简单排序算法是**不稳定**的排序算法。

### 适用场景

1. 选择排序**实现也比较简单**，并且由于在各种情况下**复杂度波动较小**，因此一般是**优于冒泡排序**的。
2. 在所有的完全交换排序中，选择排序也是比较不错的一种算法，但是由于固有的 $O(n^2)$ 复杂度，选择排序在海量数据面前显得力不从心，因此，它**适用于简单数据排序**。

## 冒泡排序

### 算法原理

1. 冒泡排序的基本思想是**对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小（最大）的元素浮到顶端，最终达到完全有序**。

![](https://notebook.ricear.com/media/202105/2021-05-04_183505.png)

### 参考代码

1. 在冒泡排序过程中，如果某一趟执行完毕，没有做任何一次交换操作，这就说明剩下的序列已经是有序的，排序操作也就可以完成了。

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/5/3 21:10
 * @Description 冒泡排序算法
 */
public class BubbleSort {
    public static void sort(int[] arr) {
        int m = arr.length;
        for (int i = 0; i < m - 1; i++) {
            //  判断是否需要交换
            boolean exchange = false;
            for (int j = 0; j < m - i - 1; j++) {
                //  如果前面一个元素比后面一个元素大，则交换两个元素的位置，同时将 exchange 置为 true
                if (arr[j] > arr[j+1]) {
                    CommonUtils.swap(arr, j, j+1);
                    exchange = true;
                }
            }
            if (!exchange) {
                //  如果这一次冒泡没有发生交换，则说明前面的元素都已经有序了，没有必要再进行下一次冒泡了
                break;
            }
        }
    }
}
```

### 算法分析

1. 对于冒泡排序算法，若原数组本身就是有序的，仅需 $n-1$ 次比较即可完成；若是倒序，比较次数为 $(n-1) + (n-2) + ... + 1 = n(n-1)/2$，交换次数和比较次数等值，所以，时间复杂度依然为 $O(n^2)$。
2. 综合来看，冒泡排序性能还是稍差于上面的**简单选择排序**的。
3. 在相邻元素相等时，他们不会交换位置，所以，冒泡排序是**稳定排序**。

### 适用场景

1. 冒泡排序思路简单，代码也简单，特别**适合小数据的排序**，但是，由于**算法复杂度较高**，在**数据量大的时候不适用**。

## 直接插入排序

### 算法原理

1. 直接插入排序算法的基本思想是**每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止**。

![](https://notebook.ricear.com/media/202105/2021-05-04_195701.png)

### 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/5/3 21:28
 * @Description 直接插入排序算法
 */
public class DirectInsertionSort {
    public static void sort(int[] arr) {
        int m = arr.length;
        for (int i = 1; i < m; i++) {
            int j = i;
            while (j > 0 &amp;&amp; arr[j - 1] > arr[j]) {
                CommonUtils.swap(arr, j - 1, j);
                j--;
            }
        }
    }
}
```

### 算法分析

1. 简单插入排序在**最好情况下**需要比较 $n-1$ 次，无需交换元素，**时间复杂度为 $O(n)$**；在最坏情况下，时间复杂度依然为 $O(n^2)$。
2. 但是，在**数组元素随机排列**的情况下，插入排序还是要**优于上面两种排序**的。
3. 由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是**稳定排序**。

### 适用场景

1. 简单插入排序由于 $O(n^2)$ 的复杂度，在数组较大时不适用，但是，当数据比较少的时候，是一个不错的选择，一般作为**快速排序的扩充**。
2. 例如，在 `JDK 7` 中的 `java.util.Arrays` 所用的 `sort` 方法的实现中，当待排序数组长度小于 47 时，会使用插入排序。

## 希尔排序

### 算法原理

1. 希尔排序也是一种**插入排序**，它是**简单插入排序**经过改进之后的一个更高效的版本，也称为**递减增量排序算法。**

2. 希尔排序的基本思想是**把记录按下标的一定增量分组，对每组使用直接插入算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止**。

3. **简单插入排序很循规蹈矩**，不管数组分布是怎样的，依然一步一步对元素进行比较、移动、插入，比如 $[5,4,3,2,1]$ 这种倒序序列，数组末端的 0 要回到首位是很费劲的，比较和移动元素均需 $n-1$ 次。

4. 而希尔排序在数组中采用**跳跃式分组**的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为 1。

5. 希尔排序通过这种策略使得整个数组**在初始阶段达到从宏观上看基本有序**，**小的基本在前**，大的基本在后，然后缩小增量，到增量为 1 时，大多数情况下只需微调即可，不会涉及过多的数据移动。

6. 希尔排序的具体排序过程如下：

1. 假如有这样一组数 $[13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10]$，如果我们以步长为 5 开始进行排序，我们可以通过将这列表放在有 5 列的表中来更好的描述算法：

```txt
      13 14 94 33 82
      25 59 94 65 23
      45 27 73 25 39
      10
      ```

2. 然后我们对每列进行**直接插入排序**：

```txt
      10 14 73 25 23
      13 27 94 33 39
      25 59 94 65 82
      45
      ```

3. 然后再以 3 为步长进行排序：

```txt
      10 14 73
      25 23 13
      27 94 33
      39 25 59
      94 65 82
      45
      ```

4. 排序之后的结果为：

```txt
      10 14 13
      25 23 33
      27 25 59
      39 65 73
      45 94 82
      94
      ```

5. 最后再以 1 为步长进行排序，此时就是简单排序了。

### 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/5/4 19:34
 * @Description 希尔排序
 */
public class ShellSort {
    public static void sort(int[] arr) {
        int len = arr.length;
        //  增量 gap，并不断缩小增量
        for (int gap = len / 2; gap >= 1; gap = gap / 2) {
            //  从第 gap 个元素开始，对每个组使用直接插入排序
            for (int i = gap; i < len; i++) {
                int j = i;
                int temp = arr[i];
                while (j - gap >= 0 &amp;&amp; temp < arr[j - gap]) {
                    //  将元素向后移动 gap 位
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }
}
```

### 算法分析

1. 希尔排序算法中对**增量序列的选择**十分重要，直接影响到希尔排序的性能，当选择增量序列为 $n/2^i$ 时，其最坏时间复杂度依然为 $O(n^2)$。
2. 希尔排序是**不稳定排序算法**。

### 适用场景

1. 希尔排序虽然快，但是毕竟是插入排序，其数量级并**没有快速排序快**，在大量数据面前，希尔排序不是一个好的算法，但是**中小型规模的数据完全可以使用它**。

## 快速排序

### 算法原理

1. 快速排序是对**冒泡排序**的改进，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和交换次数少了很多，速度也快了不少。

2. 快速排序的基本思想是：

1. 在待排序的元素**任取一个元素作为基准**（通常选第一个元素），称为**基准元素**。
   2. 将待排序的元素进行**分区**，**比基准元素大的元素放在他的右边，比其小的放在他的左边**。
   3. **对左右两个分区重复以上的步骤直到所有元素都是有序的**。

3. 快速排序算法的具体过程如下图：

![](https://notebook.ricear.com/media/202206/2022-06-27_110211_290113.gif)

### 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/5/4 20:54
 * @Description 快速排序算法
 */
public class QuickSort {
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

/**
     * 快速排序算法
     * @param arr   数组
     * @param _left 左边界
     * @param _right 右边界
     */
    public static void quickSort(int[] arr, int _left, int _right) {
        int left = _left;
        int right = _right;
        int temp = 0;
        if (left <= right) {
            //  待排序的第一个元素作为基准元素
            temp = arr[left];
            //  从左到有交替扫描，直到 left = right
            while (left != right) {
                //  从右往左扫描，找到第一个比基准元素小的元素
                while (right > left &amp;&amp; arr[right] >= temp) {right--;}
                //  找到这种元素 arr[right] 后与 arr[left] 交换
                arr[left] = arr[right];

//  从左往右扫描，找到第一个比基准元素大的元素
                while (left < right &amp;&amp; arr[left] <= temp) {left++;}
                //  找到这种元素 arr[left] 后与 arr[right] 交换
                arr[right] = arr[left];
            }
            //  基准元素归位
            arr[right] = temp;
            //  对基准元素左边的元素进行递归排序
            quickSort(arr, _left, left - 1);
            //  对基准元素右边的元素进行递归排序
            quickSort(arr, right + 1, _right);
        }
    }
}
```

### 算法分析

1. 当分区选取的基准元素为待排元素中的**最大或最小值**时，为**最坏的情况**，**时间复杂度**和直接插入排序的一样，移动次数达到最大值 $C_{max}=1+2+...+(n-1)=n*(n-1)/2=O(n^2)$。
2. 当分区选取的基准元素为待排序中的**中值**，为最好的情况，**时间复杂度为 $O(nlog_2n)$**。
3. 快速排序的**空间复杂度**为 $O(log_2n)$。
4. 当待排元素类似 $[6,1,3,7,3]$ 且基准元素为 6 时，经过分区，形成 $[1,3,3,6,7]$，两个 3 的相对位置发生了改变，所以快速排序是一种**不稳定排序算法**。

### 适用场景

1. 快速排序在**大多数情况下**都是**适用**的，**尤其在数据量大的时候**性能优越更加明显，但在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。

### 扩展题目

#### 单链表快速排序

> 对于『将两个无序链表合并为一个新的有序链表』的题目，我们可以把两个无序链表连接为一个无序链表，然后对这个无序链表进行排序即可。

##### 值交换

###### 问题分析

1. 快速排序的思想就是**找一个 `pivot`**，**把小于 `pivot` 分在一边**，**大于等于 `pivot` 的分在另一边**。

2. 这个过程也叫做 `partition` 分区，数组的分区很好做，左右两个指针，不断交换就可以了，链表因为只能单向遍历，所以要换一种 `partition` 方法，目的是**使得左边的值都小于 `pivot`**，**右边的值都不小于 `pivot`**，所以**用一个索引记录左边的坐标**，**遍历过程中**，**每次碰到比 `pivot` 小的**，**都要交换一下**，**放到左边**，**遍历完成后**，**再把 `pivot` 放到中间来**，**这样就达成了目的**。

![](https://notebook.ricear.com/media/202206/2022-06-27_170430_826067.gif)

###### 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/9/20 15:08
 * @Description 快速排序算法
 */
public class QuickSort {
    /**
     * 使用单链表实现快速排序算法（值交换）
     * @param head  单链表头结点
     * @return  排序后的单链表
     */
    public ListNode sortList(ListNode head) {
        quickSortWithValExchange(head, null);
        return head;
    }

/**
     * 单链表快速排序算法（值交换）
     * @param head  单链表头结点
     * @param tail  单链表尾节点
     */
    private void quickSortWithValExchange(ListNode head, ListNode tail) {
        if (head == tail || head.next == tail) {return;}
        int pivot = head.val;
        ListNode left = head, cur = head.next;

while (cur != tail) {
            if (cur.val < pivot) {
                left = left.next;
                swap(left, cur);
            }
            cur = cur.next;
        }

swap(head, left);
        quickSortWithValExchange(head, left);
        quickSortWithValExchange(left.next, tail);
    }

/**
     * 交换链表中两个节点的值
     * @param left  其中一个链表节点
     * @param cur   另外一个链表节点
     */
    private void swap(ListNode left, ListNode cur) {
        int temp = left.val;
        left.val = cur.val;
        cur.val = temp;
    }
}
```

##### 指针交换

###### 问题分析

1. 这道题目的解题方法如下：

1. 首先**对链表进行划分**。
   2. 然后**递归调用**，**先重排右边的**，**然后把指针置空**，**再重排左边的**。
   3. 最后**将左半部分和右半部分进行拼接即可**。

###### 5.5.1.2.2 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/9/20 15:08
 * @Description 快速排序算法
 */
public class QuickSort {
    /**
     * 使用单链表实现快速排序算法（指针交换）
     * @param head  单链表头结点
     * @return  排序后的单链表
     */
    public ListNode sortList(ListNode head) {
        return quickSortWithPointerExchange(head);
    }

/**
     * 单链表快速排序算法（指针交换）
     * @param head  单链表头结点
     * @return  排序后的单链表
     */
    private ListNode quickSortWithPointerExchange(ListNode head) {
        if (head == null || head.next == null) {return head;}

int pivot = head.val;
        //  链表划分
        ListNode ls = new ListNode(-1), rs = new ListNode(-1);
        ListNode l = ls, r = rs, cur = head;

while (cur != null) {
            if (cur.val < pivot) {l.next = cur; l = l.next;}
            else {r.next = cur; r = r.next;}
            cur = cur.next;
        }

l.next = rs.next;
        r.next = null;

//  递归调用，先重排右边的，然后把指针置空，再重排左边的
        ListNode right = quickSortWithPointerExchange(head.next);
        head.next = null;
        ListNode left = quickSortWithPointerExchange(ls.next);

//  拼接左半部分和右半部分
        cur = left;
        while (cur.next != null) {cur = cur.next;}
        cur.next = right;

return left;
    }
}
```

## 堆排序

### 算法原理

1. 堆是具有以下性质的完全二叉树：

1. **每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆**。
   2. **每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆**。
      ![](https://notebook.ricear.com/media/202105/2021-05-05_203837.png)

2. 堆排序的基本思想为：

1. **将待排序序列构造成一个大顶堆**（构造大顶堆的时候选取的初始值为**最后一个非叶子节点**），此时，整个序列的**最大**值就是**堆顶的根节点**。
   2. 将**堆顶的根节点与末尾元素进行交换**，此时**末尾元素就是最大值**。
   3. 将剩余的 $n - 1$ 个元素看作一个新堆，**原来根的孩子节点仍是大顶堆**，而**新的根节点可能会违背最大堆的性质**，因此我们需要采用上面构造大顶堆的方法来**调整堆**，使其**符合大顶堆的性质**。
   4. 然后重复上面交换新堆末尾元素和调整堆的过程，即可依次获取次小值，进而完成数据的排序。

### 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/5/5 19:49
 * @Description 堆排序
 */
public class HeapSort {
    public static void sort(int[] arr) {
        //  1. 构建大顶堆：从第一个非叶子节点开始从下至上，从右至左调整结构
        int len = arr.length;
        //  第一个非叶子节点
        int beginIndex = (len >> 1) - 1;
        for (int i = beginIndex; i >= 0; i--) {
            adjustHeap(arr, i, len - 1);
        }

//  2.调整堆结构:
        //      2.1 每次都是移出最顶层的根节点，与最尾部节点位置调换，同时遍历长度-1。
        //      2.2 然后重新整理被换到根节点的末尾元素，使其符合堆的特性。
        //      2.3 直到未排序的堆长度为 0
        for (int i = len - 1; i > 0; i--) {
            CommonUtils.swap(arr, 0, i);
            adjustHeap(arr, 0, i - 1);
        }
    }

/**
     * 调整大顶推（仅是调整过程，建立在大顶堆已经构建的基础上）
     * @param arr   数组
     * @param index 需要堆化处理的数据的索引
     * @param length    未排序的数组的长度
     */
    public static void adjustHeap(int[] arr, int index, int length) {
        //  左子节点索引
        int left = (index << 1) + 1;
        //  右子节点索引
        int right = left + 1;
        //  子节点的最大索引，默认是左子节点
        int max = left;

// 如果左子节点索引超出范围，则直接返回
        if (left > length) {return;}
        //  判断左右子节点哪个最大
        if (right <= length &amp;&amp; arr[right] > arr[left]) {max = right;}
        //  判断是否需要交换子节点和父节点：
        //      如果需要的话，则交换相应的子节点和父节点，然后调整换下父节点后的堆使其符合堆的特性
        if (arr[max] > arr[index]) {
            CommonUtils.swap(arr, max, index);
            adjustHeap(arr, max, length);
        }
    }
}
```

### 算法分析

1. 堆排序算法**在最好和最坏情况下的时间复杂度都为 $O(nlog_2n)$**，**空间复杂度为 $O(1)$**。
2. 堆排序算法是**不稳定排序算法**。

### 适用场景

1. 堆排序在**建立堆**和**调整堆**的过程中会产生比较大的开销，在**元素少的时候**并**不适用**，但是**在元素比较多的时候**还**是一个不错的选择**。
2. **在解决诸如 `前 n 的数` 一类问题时**，几乎**是首选算法**。

### 扩展题目

#### 数组中的第 K 个最大元素]

> 题目来源：[215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array)。

##### 堆排序

###### 问题分析

1. 我们可以构建一个大顶堆，然后在堆排序的过程中，每次调整大顶堆，我们都可以获取一个较大的元素，这样我们只需调整 $k$ 次，便可以将前 $k$ 大的元素排好位置，然后直接返回第 $arr.length - k$ 个元素即可。
2. 对于求**前 $k$ 大元素**的题目，一般用**堆排序**来解决。

###### 参考代码

```java
/**
 * 调整堆
 * @param arr   数组
 * @param index 需要堆化处理的数据的索引
 * @param length    未排序的数组的长度
 */
public static void adjustHeap(int[] arr, int index, int length) {
    int left = (index << 1) + 1;
    int right = left + 1;
    int max = left;
    if (left > length) return;
    if (right <= length &amp;&amp; arr[right] > arr[left]) {max = right;}
    if (arr[max] > arr[index]) {
        CommonUtils.swap(arr, max, index);
        adjustHeap(arr, max, length);
    }
}

/**
 * 堆排序
 * @param arr   数组
 * @param k 前几个数
 */
public static void sort(int[] arr, int k) {
    //  1. 构造大顶堆
    int length = arr.length;
    int beginIndex = (length >> 1) - 1;
    for (int i = beginIndex; i >= 0; i--) {
        adjustHeap(arr, i, length - 1);
    }

//  2. 调整大顶堆
    for (int i = length - 1; i >= length - k; i--) {
        CommonUtils.swap(arr, 0, i);
        adjustHeap(arr, 0, i - 1);
    }
}

/**
 * 215. 数组中的第 K 个最大元素（版本 2：堆排序）
 * @param nums  数组
 * @param k 前几个数
 * @return  第 K 个最大元素
 */
public int findKthLargestV2(int[] nums, int k) {
    sort(nums, k);
    return nums[nums.length - k];
}
```

##### 快速排序

###### 问题分析

1. 该题目还可以利用 **快速排序** 来解决：

1. 快速排序每进行一次遍历，都会将一个元素放到其最终位置上，**左边的元素都小于该元素**，**右边的元素都大于该元素**。

2. 因此我们可以在完成一轮遍历后，判断 **当前已放置到最终位置的元素的位置 $cur$ 和目标元素的位置 $target$ 的关系**：

1. 如果 $target = cur$，说明当前元素就是目标元素，**直接返回** 即可。
      2. 如果 $target < cur$，说明目标元素在当前元素的 **左边**，因此只 **向左边进行遍历** 即可。
      3. 如果 $target > cur$，说明目标元素在当前元素的 **右边**，因此只 **向右边进行遍历** 即可。

> 目标元素的位置 $target$ 等于数组的长度减去 $k$。

###### 参考代码

```java
/**
 * 采用快速排序查找目标位置的元素
 * 
 * @param arr   数组
 * @param _left 左边界
 * @param _right    右边界
 * @param target    目标元素的位置
 */
public static void quickSort(int[] arr, int _left, int _right, int target) {
    int left = _left, right = _right;
    int temp = 0;

if (left <= right) {
        temp = arr[left];
        while (left != right) {
            while (right > left &amp;&amp; arr[right] >= temp) {right--;}
            arr[left] = arr[right];
            while (left < right &amp;&amp; arr[left] <= temp) {left++;}
            arr[right] = arr[left];
        }
        arr[right] = temp;
        if (target == right) {return;}
        else if (target < right) {quickSort(arr, _left, left - 1, target);}
        else if (target > right) {quickSort(arr, right + 1, _right, target);}
    }
}
```

#### 数据流中的中位数

> 题目来源：[剑指 Offer 41. 数据流中的中位数](https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof)。

##### 问题分析

1. 我们可以**建立一个小顶堆 $A$ 和大顶堆 $B$**，**各保存列表的一半元素**，且规定：

1. **$A$ 保存较大的一半**，**长度为 $\frac{N}2$**（$N$ 为偶数）**或 $\frac{N + 1}2$**（$N$ 为奇数）。
   2. **$B$ 保存较小的一半**，**长度为 $\frac{N}2$**（$N$ 为偶数）**或 $\frac{N - 1}2$**（$N$ 为奇数）。

2. 随后，**中位数可仅根据 $A、B$ 的堆顶元素计算得到**：

![Picture1.png](https://notebook.ricear.com/media/202202/2022-02-09_1419550.3791480604271996.png)

3. 算法流程如下：

1. **设元素总数为 $N = m + n$**，**其中 $m$ 和 $n$ 分别为 $A$ 和 $B$ 中的元素个数**。

2. `addNum(num)`**函数**：

1. **当 $m = n$**（即 $N$**为偶数**）：**需向 $A$ 添加一个元素**，实现方法为**将新元素 $num$ 插入至 $B$**，**再将 $B$ 堆顶元素插入至 $A$**。

2. **当 $m \ne n$**（即 $N$**为奇数**）：**需向 $B$ 添加一个元素**，实现方法为**将新元素 $num$ 插入至 $A$**，**再将 $A$ 堆顶元素插入至 $B$**。

> 假设插入数字 $num$ 遇到情况 1，由于 $num$**可能属于较小的一半**（即属于 $B$），因此**不能将 $num$ 直接插入 $A$**，**而应先将 $num$ 插入 $B$**，**再将 $B$ 堆顶元素插入至 $A$**，**这样就可以始终保持 $A$ 保存较大一半**，$B$**保存较小一半**。

3. `findMedian()`**函数**：

1. **当 $m = n$**（即 $N$**为偶数**）：**则中位数为 $\frac{A 的堆顶元素 + B 的堆顶元素}2$**。
      2. **当 $m \ne n$**（即 $N$**为奇数**）：**则中位数为 $A$ 的堆顶元素**。

##### 参考代码

```java
/**
 * 剑指 Offer 41. 数据流中的中位数
 */
class MedianFinder {

Queue<Integer> A, B;

/** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x, y) -> (y - x));
    }

public void addNum(int num) {
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }

public double findMedian() {
        int size = A.size() + B.size();
        if (size % 2 != 0) {
            return (double)A.peek();
        } else {
            return (double)(A.peek() + B.peek()) / 2;
        }
    }
}
```

## 归并排序

### 算法原理

1. 归并排序是**创建在归并操作上的一种有效的排序算法**。
2. 该算法是采用**分治法**（Divide and Conquer）的一种非常典型的应用，且各层递归可以同时进行。
3. 归并算法的具体过程如下（**分而治之**）：

![](https://notebook.ricear.com/media/202105/2021-05-05_212356.png)

4. **合并相邻有序子序列**的方法：

![](https://notebook.ricear.com/media/202105/2021-05-05_212635.png)

![](https://notebook.ricear.com/media/202105/2021-05-05_212646.png)

### 参考代码

```java
/**
 * @author peng.wei
 * @version 1.0
 * @date 2021/5/5 21:28
 * @Description 归并排序
 */
public class MergeSort {
    /**
     * 归并排序
     * @param arr   数组
     */
    public static void sort(int[] arr) {
        int length = arr.length;
        int[] temp = new int[length];
        sort(arr, 0, length - 1, temp);
    }

/**
     * 归并排序（递归）
     * @param arr   数组
     * @param left  左边界
     * @param right 右边界
     * @param temp  临时数组
     */
    public static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            //  左边归并排序，使得左子序列有序
            sort(arr, left, mid, temp);
            //  右边归并排序，使得右子序列有序
            sort(arr, mid + 1, right, temp);
            //  将两个有序子数组合并
            merge(arr, left, mid, right, temp);
        }
    }

/**
     * 合并两个序列
     * @param arr   数组
     * @param left  左边界
     * @param mid   中间元素
     * @param right 右边界
     * @param temp  临时数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        //  左序列指针
        int i = left;
        //  右序列指针
        int j = mid + 1;
        //  临时数组指针
        int t = 0;

//  开始遍历左右两个序列
        while (i <= mid &amp;&amp; j <= right) {
            //  如果左边的元素小一些，则将左边的元素移动到 temp 数组中，同时左边的指针加 1
            if (arr[i] <= arr[j]) {temp[t++] = arr[i++];}
            //  如果右边的元素小一些，则将右边的元素移动到 temp 数组中，同时右边的指针加 1
            else if (arr[i] > arr[j]) {temp[t++] = arr[j++];}
        }

//  将左边的剩余元素移动到 temp 中
        while (i <= mid) {temp[t++] = arr[i++];}
        //  将右边的剩余元素移动到 temp 中
        while (j <= right) {temp[t++] = arr[j++];}

//  将 temp 中的元素全部拷贝到原数组中
        t = 0;
        while (left <= right) {arr[left++] = temp[t++];}
    }
}
```

### ![](https://notebook.ricear.com/media/202105/2021-05-06_191525.png)算法分析

1. 归并排序算法**在最好情况下和最坏情况下的时间复杂度均为 $O(nlog_2n)$，空间复杂度为 $O(n)$。**
2. 归并排序算法是一种**稳定排序算法**，同时也是一种十分高效的排序算法，其速度仅次于快速排序。

### 适用场景

1. 归并排序在**数据量比较大**的时候在**效率上**也**有较为出色的表现**。
2. 但是，其**空间复杂度**$O(n)$ 使得**在数据量特别大的时候**（例如 1000 万条数据）几乎**不可接受**，而且，考虑到有的机器内存本身就比较小，因此，**采用归并排序时一定要注意**。

### 扩展题目

#### 数组中的逆序对

> 题目来源：[剑指 Offer 51. 数组中的逆序对](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof)。

##### 问题分析

1. **[归并排序](#7-归并排序)与逆序对是息息相关的**，**归并排序体现了分而治之的思想**，**具体为**：

1. **分**：**不断将数组从中点位置划分开**，**将整个数组的排序问题转化为子数组的排序问题**。
   2. **治**：**划分到子数组长度为 1 时**，**开始向上合并**，**不断将较短排序树组合并为较长排序树组**，**直至合并至原数组时完成排序**。

2. **合并阶段本质上是合并两个排序数组的过程**，**而每当遇到 $ 左子数组当前元素 \gt 右子数组当前元素 $ 时**，**意味着 $ 左子数组当前元素至末尾元素 $ 与 $ 右子数组当前元素 $ 构成了若干逆序对**。

3. **因此**，**考虑在归并排序的合并阶段统计逆序对数量**，**完成归并排序时**，**也随之完成所有逆序对的统计**。

![Picture2.png](https://notebook.ricear.com/media/202202/2022-02-10_1954210.9101305560938778.png)

##### 参考代码

```java
/**
 * 剑指 Offer 51. 数组中的逆序对
 * @param nums  数组
 * @return  数组中的逆序对的总数
 */
public int reversePairs(int[] nums) {
    int length = nums.length;
    int[] temp = new int[length];
    return sort(nums, 0, length - 1, temp);
}

/**
 * 归并排序（递归）
 * @param arr   数组
 * @param left  左边界
 * @param right 右边界
 * @param temp  临时数组
 * @return 数组中的逆序对的总数
 */
public int sort(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        //  左边归并排序，使得左子序列有序
        int res = sort(arr, left, mid, temp);
        //  右边归并排序，使得右子序列有序
        res += sort(arr, mid + 1, right, temp);
        //  将两个有序子数组合并
        return merge(arr, left, mid, right, temp, res);
    }
    return 0;
}

/**
 * 合并两个序列
 * @param arr   数组
 * @param left  左边界
 * @param mid   中间元素
 * @param right 右边界
 * @param temp  临时数组
 * @return 数组中的逆序对的总数
 */
public int merge(int[] arr, int left, int mid, int right, int[] temp, int res) {
    //  左序列指针
    int i = left;
    //  右序列指针
    int j = mid + 1;
    //  临时数组指针
    int t = 0;

//  开始遍历左右两个序列
    while (i <= mid &amp;&amp; j <= right) {
        //  如果左边的元素小一些，则将左边的元素移动到 temp 数组中，同时左边的指针加 1
        if (arr[i] <= arr[j]) {temp[t++] = arr[i++];}
        //  如果右边的元素小一些，则将右边的元素移动到 temp 数组中，同时右边的指针加 1，然后统计逆序对的数量
        else if (arr[i] > arr[j]) {
            temp[t++] = arr[j++];
            res += mid - i + 1;
        }
    }

//  将左边的剩余元素移动到 temp 中
    while (i <= mid) {temp[t++] = arr[i++];}
    //  将右边的剩余元素移动到 temp 中
    while (j <= right) {temp[t++] = arr[j++];}

//  将 temp 中的元素全部拷贝到原数组中
    t = 0;
    while (left <= right) {arr[left++] = temp[t++];}

return res;
}
```

## 总结

### 算法分类

十种常见排序算法可以分为两大类：

* **比较类排序：** 通过**比较**来决定**元素间的相对次序**，由于其**时间复杂度不能突破 $O(nlogn)$**，因此也称为**非线性时间比较类排序**。
* **非比较类排序：不通过比较**来决定**元素间的相对次序**，他**可以突破基于比较排序的时间下界**，以线性时间运行，因此也称为**线性时间非比较类排序**。

![](https://notebook.ricear.com/media/202105/2021-05-06_184235.png)

### 算法复杂度

* **稳定：** 如果 `a` 原本在 `b` 前面，且 `a=b`，排序之后 `a` 仍然在 `b` 前面。
* **不稳定：** 如果 `a` 原本在 `b` 前面，且 `a=b`，排序之后 `a` 可能会在 `b` 的后面。
* **时间复杂度：** 对排序数据的**总的操作次数**，反映当 `n` 变化时呈现什么规律。
* **空间复杂度：** 指**算法在计算机内执行时所需存储空间的度量**，他也是数据规模 `n` 的函数。

![](https://notebook.ricear.com/media/202105/2021-05-06_191453.png)

#### 稳定性

**稳定**的算法有：**插（如排序）、冒（泡排序）、归（并排序）、计（数排序）、桶（排序）、基（数排序）**。

**不稳定**的算法有：其他的 4 种都为不稳定的排序算法。

#### 时间复杂度

平均时间复杂度为 $O(nlog_2n)$ 的有：**堆（排序）、快（速排序）、归（并排序）**。

平均时间复杂度为 $O(n^{1.3})$ 的有：**希（尔排序）**。

平均时间复杂度为 $O(n^2)$ 的有：**插（入排序）、选（择排序）、冒（泡排序）**。

#### 空间复杂度

空间复杂度为 $O(1)$ 的有：**插（入排序）、希（尔排序）、选（择排序）、堆（排序）、冒（泡排序）**。

空间复杂度为 $O(n)$ 的有：**归（并排序）**。

空间复杂度为 $O(nlog_2n)$ 的有：**快（速排序）**。

## 参考文献

1. [图解排序算法(一)之 3 种简单排序(选择，冒泡，直接插入)](https://www.cnblogs.com/chengxiao/p/6103002.html)。
2. [希尔排序](https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F)。
3. [图解快速排序](https://www.cnblogs.com/MOBIN/p/4681369.html)。
4. [快速排序算法详解（原理、实现和时间复杂度）](http://data.biancheng.net/view/117.html)。
5. [图解排序算法(三)之堆排序](https://www.cnblogs.com/chengxiao/p/6129630.html)。
6. [堆排序](https://zh.wikipedia.org/zh-cn/%E5%A0%86%E6%8E%92%E5%BA%8F)。
7. [图解排序算法(四)之归并排序](https://www.cnblogs.com/chengxiao/p/6194356.html)。
8. [【算法】排序算法之归并排序](https://zhuanlan.zhihu.com/p/124356219)。
9. [[算法总结] 十大排序算法](https://weiweiblog.cn/10sort)。
10. [十大经典排序算法（动图演示）](https://www.cnblogs.com/onepixel/p/7674659.html)。
11. [ 面试官：你写个链表快排吧（不准交换节点的值哦）](https://leetcode-cn.com/problems/sort-list/solution/gui-bing-pai-xu-he-kuai-su-pai-xu-by-a380922457)。
13. [面试题 41. 数据流中的中位数（优先队列 / 堆，清晰图解）](https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/solution/mian-shi-ti-41-shu-ju-liu-zhong-de-zhong-wei-shu-y)。