# Sort

## Preface

|  算法 |   是否原地  | 是否稳定 |    平均    |       最好      |    最坏    | 基于比较 |
| :-: | :-----: | :--: | :------: | :-----------: | :------: | :--: |
|  冒泡 |    是    |   是  |  O(n^2)  |      O(n)     |  O(n^2)  |   是  |
|  插入 |    是    |   是  |  O(n^2)  |      O(n)     |  O(n^2)  |   是  |
|  选择 |    是    |   否  |  O(n^2)  |     O(n^2)    |  O(n^2)  |   是  |
|  归并 | 否: O(n) |   是  | O(nlogn) |    O(nlogn)   | O(nlogn) |   是  |
|  快速 |    是    |   否  | O(nlogn) |    O(nlogn)   |  O(n^2)  |   是  |
|  堆  |    是    |   否  | O(nlogn) |    O(nlogn)   | O(nlogn) |   是  |
|  计数 |    否    |   是  |          | O(n+k), k数据范围 |          |   否  |
|  桶  |    否    |   是  |          |      O(n)     |          |   否  |
|  基数 |    否    |   是  |          |   O(dn), d位数  |          |   否  |

**评价排序算法的维度**：

1. 时间复杂度：最好、最坏、平均，以及对应的原始数据类型。
2. 时间复杂度的系数、常数、低阶，时间复杂度反应的是随数据规模 n 增大的增长趋势，一般是在 n 很大的情况下得出。但是在实际中，n 可能不是很大，所以在同一个阶时间复杂度下，需要考虑系数、常数、低阶。
3. 比较次数与交换（移动）次数的分析。
4. 内存消耗。**原地排序**（sorted in place）指空间复杂度为 O(1) 的排序算法。
5. 稳定性，如果待排序的序列中存在值相等的元素，经过排序之后，相等的元素之间原有的先后顺序不变。实际中，我们是根据对象的某个 field 来排序，对象还有其它 field，所以需要分析稳定性。例子：订单有时间和金额，希望 order by amount, time，那么先对时间排序，然后用稳定的排序算法对金额排序，得到的结果就是金额从小到大，相同金额从早到晚。

## Bubble Sort

**描述**：冒泡排序仅会操作相邻的两个元素，比较两个相邻元素，若不满足大小关系，则交换。每次冒泡会让一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序。

![](/files/-LwwixxB8jRomnw45pGX)

**优化**：当某次冒泡没有数据交换时，则完成排序。

```java
public void sort(Integer[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        boolean exchanged = false;
        for (int j = 1; j < n - i; j++) {
            if (nums[j - 1] > nums[j]) {
                exchanged = true;
                exchange(nums, j - 1, j);
            }
        }
        if (!exchanged) {
            break;
        }
    }
}
private void exchange(Integer[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}
```

**原地排序**：只需要常量级的额外空间。

**稳定排序**：当相邻两个元素相等时，不交换就行。

**最好时间复杂度**：若数据本来有序，则只需要一次冒泡，所以最好为 O(n)。

**最坏时间复杂度**：若数据刚好为逆序，则要进行 n 次冒泡，所以最坏为 O(n^2)。

**平均时间复杂度**：

有序度是数组中具有有序关系的元素对的个数，有序元素对定义：`a[i] <= a[j], i < j`。如`2, 4, 3, 1, 5, 6`有序度为`4 + 2 + 2 + 2 + 1 = 11`。完全有序的数组的有序度叫满有序度(`n * (n - 1) / 2`)。`逆序度 = 满有序度 - 有序度`。

冒泡有两个比较和交换两个操作，每次交换，有序度加1，所以`交换次数 = 逆序度`。平均交换次数`n * (n - 1) / 4`，比较次数 > 交换次数，时间复杂度上限 O(n^2)，所以平均时间复杂度 O(n^2)。

注意此种平均时间复杂度分析并不严格。

## Insertion Sort

**描述**：将数组分为两个区域，已排序和未排序，初始已排序为第一个元素。每次取未排序的第一个元素，在已排序中找到合适位置插入。

![](/files/-LwwjXM4VaAfdlSVEt9K)

```java
public void sort(Integer[] nums) {
    int n = nums.length;
    for (int i = 1; i < n; i++) {
        int tmp = nums[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
            if (tmp < nums[j]) {
                nums[j + 1] = nums[j];
            } else {
                break;
            }
        }
        nums[j + 1] = tmp;
    }
}
```

**特点**：包含比较和移动两种操作。移动次数等于逆序度。

**原地排序**：不需要额外存储空间。

**稳定排序**：当两个元素相等时，将后面插入的元素放到前面出现的元素后面，就可以保证顺序不变。

**最好时间复杂度**：如数据本来有序，则不需要搬动任何数据，查找插入位置时从尾到头，则每次只需要比较一次，所以最好为 O(n)。

**最坏时间复杂度**：如果数据是倒序的，每次都要移动有序区域的所有数据，所以最坏为 O(n^2)。

**平均时间复杂度**：在有序数组中插入一个数据的平均时间复杂度为 O(n)，所以插入排序的平均时间复杂度为 O(n^2)。

**为什么插入排序比冒泡排序更好？**&#x5192;泡和插入的交换或移动次数是固定的，等于逆序度。但是冒泡一次交换需要三个操作，差插入一次移动仅需一个操作。

**插入排序优化**：希尔排序，开始用大的步长，最后一次就是普通的插入，但是基本已经排好序。用大的步长是每次可以移动较大的位置。

## Selection Sort

**描述**：将数组分为两个区域，已排序和未排序，初始已排序为空，每次找到未排序的最小元素，放入已排序的末尾，即与未排序的第一个元素交换。

![](/files/-LwwqaADmN-Kwd4XEEKg)

```java
public void sort(Integer[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int min = nums[i];
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < min) {
                min = nums[j];
                minIndex = j;
            }
        }
        int tmp = nums[i];
        nums[i] = min;
        nums[minIndex] = tmp;
    }
}
```

**原地排序**：不需要额外存储空间。

**最好、最坏、平均时间复杂度**：都是 O(n^2)。

**不稳定排序**：每次都从未排序区域中找到最小，与未排序区域的第一个元素交换，破坏了稳定性。

{% hint style="info" %}
冒泡排序与选择排序仅用作理论，实际中基本不用，而插入排序有时会用到。
{% endhint %}

{% hint style="info" %}
若是链表实现，冒泡排序的交换操作更加复杂；插入排序不需要移动，直接插入；选择排序的交换同样比较复杂。
{% endhint %}

## Merge Sort

**描述**：采用分治的思想。先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并。

![](/files/-Lx-B4WA8HDq3s7EK4MN)

```java
public void sort(Integer[] nums) {
    mergeSort(nums, 0, nums.length - 1);
}

private void mergeSort(Integer[] nums, int p, int r) {
    if (p >= r) {
        return;
    }
    
    int q = (p + r) / 2;
    mergeSort(nums, p, q);
    mergeSort(nums, q + 1, r);
    merge(nums, p, r);
}

private void merge(Integer[] nums, int p, int r) {
    int q = (p + r) / 2;
    
    int[] tmp = new int[r - p + 1];
    
    int i = p, j = q + 1, cur = 0;
    while (i <= q && j <= r) {
        if (nums[i] <= nums[j]) {
            tmp[cur++] = nums[i++];
        } else {
            tmp[cur++] = nums[j++];
        }
    }
    
    for (; i <= q; i++) {
        tmp[cur++] = nums[i];
    }
    
    for (; j <= r; j++) {
        tmp[cur++] = nums[j];
    }
    
    cur = 0;
    for (int k = p; k <= r; k++) {
        nums[k] = tmp[cur++];
    }
}
```

**递推公式**：`merge_sort(p, r) = merge(merge_sort(p, q), merge_sort(q + 1, r))`

**终止条件**：`p >= r`；其中，`q = (p + r) / 2`。

**稳定排序**：关键看 merge 操作，在 merge 过程中，把 A\[p, q] 中的元素先放入临时数组，那么值相同的元素保证了顺序不变，所以归并排序是稳定的。

**最好、最坏、平均时间复杂度**：都是 O(nlogn)，分析过程如下：

```
// 假设对 n 个元素进行归并排序时间为 T(n)，那么两个子数组进行归并排序的时间都是 T(n/2)，
// merge 操作的时间复杂度是 O(n)，所以递推公式如下
T(1)=C
T(n)=2*T(n/2)+K
```

其中 K 为将两个子问题合并所需时间，`K = O(n)`。所以归并时间复杂度为 O(nlogn)，与原始数据有序程度无关。

**非原地排序**：合并操作需要一个临时数组，最大为 n，所以归并排序的空间复杂度为 O(n)。

## Quick Sort

**描述**：快排也是分治思想，将 A\[p, r] 排序，选择 p 到 r 之间任意一个数据作为 pivot（分区点），将小于pivot 的放到左边，大于 pivot 的放到右边，pivot 放到中间。

```java
public void sort(Integer[] nums) {
    _sort(nums, 0, nums.length - 1);
}

private void _sort(Integer[] nums, int p, int q) {
    if (p >= q) {
        return;
    }
    
    int r = partition(nums, p, q);
    _sort(nums, p, r - 1);
    _sort(nums, r + 1, q);
}

// 快排的分区函数类似选择排序：将数组分为两个区域，初始已处理为空，
// 每次从未处理选一个与 pivot 比较，若小于pivot，则放入已处理末尾，即与未处理的第一个元素交换。
private int partition(Integer[] nums, int p, int q) {
    int i = p;
    int pivot = nums[q];
    for (int j = p; j < q; j++) {
        if (nums[j] < pivot) {
            int tmp = nums[j];
            nums[j] = nums[i];
            nums[i++] = tmp;
        }
    }
    nums[q] = nums[i];
    nums[i] = pivot;
    return i;
}
```

**递推公式**：`quick_sort(p, r) = quick_sort(p, q - 1) + quick_sort(q + 1, r)`

**终止条件**：`p >= r`

**不稳定排序**：快速排序涉及交换，所以不稳定。

**原地排序**：分区函数不需要额外空间。

**时间复杂度分析**：大部分情况是 O(nlogn)，O(n^2) 的概率非常小，可以合理选择 pivot 来降低概率。最坏情况即数组已经有序，选择最后一个元素作为 pivot，则时间复杂度为 O(n^2)。.

```
T(1) = C
T(n) = 2 * T(n / 2) + n
```

**归并排序与快速排序的区别**：归并是由下到上，先处理子问题，再合并；快速是由上到下，先分区，再处理子问题。

### 求无序数组中第 K 大元素

**思路**：将数组 A\[0:n-1] 最后一个元素 A\[n-1] 作为 pivot，原地分区，分成了 A\[0: p - 1], A\[p], A\[p + 1: n - 1]，若 p + 1 = K，则 A\[p] 就是要求解的，否则按上述思路继续查找。

**时间复杂度**：n + n / 2 + n / 4 + n / 8 + ... + 1 = 2n - 1，为 O(n)。

## 线性排序

线性排序时间复杂度是线性 O(n) 的：桶排序、计数排序、基数排序。能做到线性，原因都是非基于比较，不涉及元素之间比较操作。

线性排序对数据的要求很严苛，都有各自的适用场景。

### Bucket Sort

**描述**：将排序的数据分到几个**有序的桶**中，每个桶内单独排序，再按照桶的顺序依次取出。

**时间复杂度**：O(n)。n 个数据，m 个桶，每个桶的数据个数为 k = n / m，`O(m*k*logk) = O(n*log(n/m))`，当 m 接近 n 时，log(n/m) 很小。

**对数据要求**：1. 数据很容易划分成 m 个桶；2. 桶与桶有天然有序；3. 能够比较均匀分布在各个桶中。

**适用场景**：适合外部排序，数据量大，无法全部加载到内存中。

**案例**：10GB 的订单数据，只有几百 MB 内存，希望按照订单金额排序。1. 扫描一遍文件，得到订单金额所处范围；2. 根据范围分为 100 个桶，每个桶对应一个文件；3. 再扫描一遍，把数据分到 100 个文件中，若分布均匀，每个文件大约 100MB；4. 100 个文件分别放在内存中排序；5. 然后将 100 个文件依次写入到一个文件中；6. 若分布不均匀，则可以对数据比较多的小文件再次分割。

### Counting Sort

**描述**：需要排序的 n 个数据，仅有 k 个可能值，则可以把数据划分到 k 个桶中，每个桶内的数据值一样，桶内不需要排序。

{% hint style="info" %}
有人认为，计数排序是特殊的桶排序。我认为不是。因为桶排序中，每个桶存放的是所有数据，每个桶单独排序；而计数排序中，每个桶中存放的是数据的个数，算法思路不一样。
{% endhint %}

**流程**：假设数据 A\[n] 有 k 个可能值。1. 先准备一个大小为 k 的数组 C，C 的下标为数据值，C 的值为数据值的个数；2. 扫描一遍数据，得到 C；3. 对 C 顺序求和，此时 C\[i] 中存放的是小于等于 i 的个数；4. 准备数组 R\[n]，从后往前扫描 A\[n]，若值为 i，则`R[C[i]]=i, C[i]=C[i]-1`。

![](/files/-Lx0WhNGG3lIVQyq-h_-)

**适用场景**：数据值范围不大；只能给非负整数排序，若是其它类型，在不改变相对大小的情况下，转化为非负整数。

**案例**：考生满分 900 分，对高考成绩排序，则可以划分成 901 个桶。

### Radix Sort

**描述**：比如，对手机号排序，从低位开始，每一位分别用线性排序。要求稳定的排序。

![](/files/-Lx0YHAdawsH4AXMzOrG)

{% hint style="info" %}
若数据不是等长，可以补齐。
{% endhint %}

**适用场景**：数据可以分割出位，位有递进关系，高位比较大，则低位就不用比较了，每一位的数据范围不大，对每位就可以用线性排序了。

## 工程应用

**如何实现一个通用的、高性能的排序函数**：

* 通用，所以不能选择对数据要求比较严格的线性排序。
* 小规模数据可选择 O(n^2)，大规模一般选择 O(nlogn)。
* O(nlogn) 比较多，Java 采用堆排序，C 采用快速排序。
* 归并用的少，原因是非原地。
* 解决快排在最坏情况 O(n^2) 的方式：a、首、尾、中三个数取中间值；b、随机；
* 快排递归，防止栈溢出，可以限制深度，也可以手动实现栈。

**Glibc 的 qsort**：

* 优先使用归并，在数据量小时。
* 数据量大，变成快排。
* 快排采用三数取中法。
* 自己在堆上实现栈。
* 当排序取件小于等于 4 时，退化为插入排序。

**O(n^2) 算法不一定比 O(nlogn) 执行时间长**：

* 时间复杂度反映的是增长趋势
* 但是会省略低阶、常数、系数，所以数据量小时，O(n^2) 可能会更快。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm/sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.