冒泡排序
以升序为例，有 N 个数需要排序，从第一个数开始，遍历所有数，将其与它下一个数比较，如果比它下一个数大则交换位置，这样最大的数就跑到最后了。
重复这个操作至多 n - 1 次，最后这 N 个数就被排好了。
动画演示
示例代码
最好时间复杂度为O(n^2)的算法
#include <iostream>
using namespace std;
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 冒泡算法
for (int i = 0; i < maxN - 1; i++) {
// 每次遍历
for (int j = 1; j < maxN - i; j++) {
// 从第一个开始比较，当前面一个大于后面一个时交换位置
if (a[j - 1] > a[j]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}最好时间复杂度为O(n)的改进算法
看书和老师PPT上说冒泡算法最好复杂度为O(n)，可是按照上面的代码无论是刚开始就是升序还是任意情况，粗略的来说进行了两次循环，最好复杂度依旧是O(n^2)，后面网上搜索才有答案：冒泡排序最佳情况的时间复杂度，为什么是O(n) - melon.h - 博客园 (cnblogs.com)。
当没有排好序时，每次遍历一定会交换位置，故当没有交换位置的时候表明已经排好了，可以挑出来不需要再进行排序了，改进后的代码：
#include <iostream>
using namespace std;
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 冒泡算法
bool isSwap;
for (int i = 0; i < maxN - 1; i++) {
// 是否交换位置
isSwap = false;
// 每次遍历
for (int j = 1; j < maxN - i; j++) {
// 从第一个开始比较，当前面一个大于后面一个时交换位置
if (a[j - 1] > a[j]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
isSwap = true;
}
}
// 当遍历到没有交换位置时，表明已经排序好了
if(!isSwap){
break;
}
}
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
因为冒泡排序用了两层循环，嵌套遍历了两次，所以平均时间复杂度为O(n ^2)；当一个序列刚好是升序无需排序时，则只进行一次循环，故最好时间复杂度为O(n)；当一个序列是降序排序时，则只需要的是嵌套循环并且每次需要交换，故最坏时间复杂度为O(n ^2)；在排序过程中无需其他空间存放数据，故空间复杂度为O(1)；在排序时当两数相等时，不进行交换，故此排序算法稳定。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
直接选择排序
以升序为例，有 N 个数需要排序，从第一个数开始，遍历所有数，查找未排序区域的最小值以及其下表，将这个最小数与当前这个数交换位置，以此类推到最后即可得到排序好的序列。
动画演示
示例代码
#include <iostream>
using namespace std;
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 直接选择排序
for (int i = 0; i < maxN - 1; i++) {
// 每次遍历记录最小值
int minIndex = i;
for (int j = i + 1; j < maxN ; j++) {
// 从第 i + 1 个开始比较，当出现小的值时记录最小值下表的值更新
if (a[minIndex] > a[j]) {
minIndex = j;
}
}
// 更新位置
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
因为直接选择排序用了两层循环，嵌套遍历了两次，所以平均时间复杂度为O(n^2)；当一个序列刚好是升序无需排序时，也要进行嵌套排序，故最好的时间复杂度为O(n ^ 2)；当一个序列是降序排序时，进行嵌套排序，故最好的时间复杂度为O(n ^ 2)；在排序过程中无需其他空间存放数据，故空间复杂度为O(1)；在排序时当两数相等时，如果两数后面有一个比它小的数时，则不稳定（如：排序 [5, 5, 2]，第一个5会和2交换，那么稳定性就打破了），故此排序算法不稳定。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
插入排序
插入排序分为 直接插入排序 与 折半插入排序
直接插入排序
从第一个数开始，按照其数字大小，插入到前面已经排好序的前面数组的合适位置之中（前一个小于自己，后一个大于自己），依次排序到最后，即可完成排序。
动画演示
示例代码
#include <iostream>
using namespace std;
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 直接插入排序
for (int i = 1; i < maxN; i++) {
/*
* 因为前部分都是已经排好序的，如果刚开始第 i 个（也就是第 j + 1）个要排序到前面的话，那么必定比刚开始的第 i 个数字小，然后交换两数
* 那么按这样下去的话，这个数一定会遇到前面的数比它小的，就排序结束了
*/
for (int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) {
// 交换数字
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
因为直接插入排序用了两层循环，嵌套遍历了两次，所以平均时间复杂度为O(n^2)；当一个序列刚好是升序无需排序时，在被嵌套的循环中无法进入，故最好的时间复杂度为O(n)；当一个序列是降序排序时，嵌套遍历了两次，故最好的时间复杂度为O(n ^2)；在排序过程中无需其他空间存放数据，故在排序过程中无需其他空间存放数据，故空间复杂度为O(1)；在排序中遇到两数相等的情况时，前面那个总是会被放在前面，后面的那个在进行排序时不会进入交换的循环，故此排序算法稳定。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
折半插入排序
折半插入排序是对直接插入排序的优化，其优化部分是在被嵌套的查找“合适位置”的循环部分，因为前面部分已经排好序了，所以采用折半搜索将第 i 个插入到前面已排好序的序列中。
示例代码
#include <iostream>
using namespace std;
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 直接插入排序
for (int i = 1; i < maxN; i++) {
// 存放此数
int temp = a[i];
// 折半搜索到合适位置
int left = 0, right = i - 1, mid;
while (left <= right) {
// 找到中间位置
// 如果单纯是 mid = (left + right) / 2 的话，如果数字很大，可能会出现整数溢出的情况。
mid = left + (right - left) / 2;
if (a[mid] > a[i]) {
// 当中间位置大于待插入的数时
// 表明此数应该排在 [left, mid) 的位置
// 由于 mid 已经大于了待插入的数，故取 right 为 mid - 1
right = mid - 1;
} else {
// 当中间位置小于等于待插入的数时
// 如果要!!实现稳定!!
// 那么表明此数应该排在 (mid ~ right] 的位置
// 由于 mid 已经小于等于了待插入的数，故取 left 为 mid + 1
left = mid + 1;
}
}
// 在循环的最后，指向的比第 i 个数大的是 left
// 将数组向后移动
// 从第 i 个开始，每个数赋值为前一个数，当 j > left 时表示可移动
for (int j = i; j > left; j--) {
a[j] = a[j - 1];
}
// 插入元素
a[left] = temp;
}
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
因为折半插入排序用了两层循环，嵌套遍历了两次，在嵌套的循环中执行了二分查找以及线性表的插入操作，所以平均时间复杂度还是为O(n^2)；当一个序列刚好是升序无需排序时，在被嵌套的循环中仍然需要执行二分查找，故最好的时间复杂度为O(nlog2n)；当一个序列是降序排序时，嵌套遍历了两次，故最好的时间复杂度为O(n ^2)；在排序过程中无需其他空间存放数据，故在排序过程中无需其他空间存放数据，故空间复杂度为O(1)；在排序中遇到两数相等的情况时，进行的二分查找不会破坏稳定性，故此排序算法稳定。
可以看出，折半插入排序的平均性能优于直接插入，而如果初始排列有序，则直接插入比折半插入比较次数少。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 折半插入排序 | O(n^2) | O(n^2) | O(n \log_2 n) | O(1) | 稳定 |
希尔排序（扇贝排序 Shell sort）
希尔排序时是基于直接插入排序的更优化排序算法，首先它是利用“gap-间隔”来将整个序列数字分为几块来排序。
排序规则
这里以序列 {37, 34, 19, 2, 16, 24, 6, 10, 40, 33} 为例，首先这一串序列有10个数，首先我们将间隔gap 设定为数组长度除以2，即 gap = ⌊10/2⌋ = 5，那么间隔为5的数字可以分为几组：
[37, 24], [34, 6], [19, 10], [2, 40], [16, 33]
这几组数字分别利用直接插入排序排好后，为：
[24, 37], [6, 34], [10, 19], [2, 40], [16, 33]
{24, 6, 10, 2, 16, 37, 34, 19, 40, 33}
再将间隔 gap 除以2，即 gap = ⌊5/2⌋ = 2，又可以分为以下几组：
[24, 10, 16, 34, 40], [6, 2, 37, 19, 33]
这几组数字分别利用直接插入排序排好后，为：
[10, 16, 24, 34, 40], [2, 6, 19, 33, 37]
{10, 2, 16, 6, 24, 19, 34, 33, 40, 37}
再将间隔 gap 除以2，即 gap = ⌊2/2⌋ = 1，这时只有一组：
[10, 2, 16, 6, 24, 19, 34, 33, 40, 37]
这时再利用一次直接插入排序，即可完成排序：
[10, 2, 16, 6, 24, 19, 34, 33, 40, 37]
{2, 10, 6, 16, 19, 24, 33, 34, 37, 40}
我们可以发现，以这个例子为例，到最后一步gap = 1时，在直接插入排序嵌套的循环中只要比较一次就能完成插入。
动画演示
步骤有点多，时间有点长，找到个B站还不错的视频：https://www.bilibili.com/video/BV1FG4y1r7pv
示例代码
#include <iostream>
using namespace std;
// 希尔排序配套的直接插入排序
void InsertSort(int a[], int n, int start, int gap) {
// 就是将间隔为 1 变成了间隔为 gap
for (int i = start + gap; i < n; i += gap) {
for (int j = i - gap; j >= start && a[j] > a[j + gap]; j -= gap) {
int temp = a[j];
a[j] = a[j + gap];
a[j + gap] = temp;
}
}
}
// 希尔排序
void ShellSort(int a[], int n) {
// 间隔首先为 长度/2 ，然后一直除以 2，直到为 1 再执行一次后结束
for (int gap = n / 2; gap >= 1; gap /= 2) {
// 从 0 开始，间隔为 gap ，每一组分别进行直接插入排序
for (int start = 0; start < gap; start++) {
InsertSort(a, n, start, gap);
}
}
}
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 希尔排序
ShellSort(a,maxN);
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
gap序列影响复杂度，如何最优尚未有定论，但 最后一个gap必须为1。
- 时间复杂度：O(n^1.25) ~O (1.6n^1.25) (经验公式)
- 空间复杂度：O(1)
是种 不稳定 的排序方法
- 因为当用gap分组时，如果有两个相同的数，可能会被分到不同组，排序后可能会打破这两个数的先后顺序。
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 希尔排序 | O(n^{1.25}) ~ O(1.6n^{1.25}) | O(1) | 不稳定 |
快速排序
首先找到一个“中间值”（这里我们选用序列的最后一个元素），所有比它小的元素往前放，比它大的元素往后放，形成两个子序列，再对两个子表进行递归，直到子表内只剩1个元素，则表示已经排好序。
所有比它小的元素往前放，比它大的元素往后放 的实现是，选用序列的第一个元素作为“中间值”，定义两个“指针”，一个是 i 指针，一个是 j 指针，i 指针负责遍历序列数组，j 指针负责的是指向比“中间值”大的任务。
假设我们有一个序列数组 a 需要排序，选用序列的第一个元素作为“中间值”，通过指针 i 遍历序列数组，当出现比“中间值”小的数时，则替换 a[i] 和 a[j] 的值，同时 j 指针向右移动；当出现当出现比“中间值”大的数时，不执行动作。
这两步就保证了如果一直比“中间值”小时，指针 i 和 j “同时”向右移动，如果出现比“中间值”大时，指针 j 就留在了比“中间值”大的值上，如果发生了两数交换，因为同时也执行了 j 指针向右移动，j 指针仍然留在了比“中间值“大的数上，如果出现了多个比“中间值”大的数，那么 j 指针留在了比“中间值“大的下一个数上，同时保证了当出现了比“中间值”大的值时就发生交换，没有出现时其实就是交换了自己等于没交换，比“中间值”小的元素一直在往前放，然后交换 j - 1 指针指向的值与“中间值”的位置。
同时也产生了两个子序列，一个在“中间值”左侧，一个在“中间值”右侧，再调用此递归左右两侧，直到序列的元素个数为1为止，表明已经排序好了。
上面这个方法挺巧妙的，建议结合文字，动画，代码 以及 动手分解执行每一步 同时理解
还有一个方法就是老师上课讲的：所有比它小的元素往前放，比它大的元素往后放 的实现是，选用序列的最后一个元素作为“中间值”，定义两个“指针”，一个在序列的最左边的是“左指针”，一个在“中间值”之前的是“右指针”，“左指针”向右移动，寻找比“中间值”小的数，找到后“右指针”再向左移动，寻找比“中间值”大的数，然后交换位置，然后“左右指针”在反复执行上面步骤，直到“左右指针”的位置重合则让“中间值”与重合位置的值交换位置，这时此“中间值”的左侧都比它小，右侧的值都比它大，再将“中间值”左侧和右侧的序列进行上述步骤，直到序列的元素个数为1为止，表明已经排序好了。
但是这里主要以第一个方法为例
动画演示
示例代码
#include <iostream>
using namespace std;
// 快速排序
void QuickSort(int a[], int left, int n) {
/*
* 参数为左闭右开
* 即[left, n)
*/
// 结束终点
if (left >= n - 1) {
return;
}
// 选择最左边的作为“中间值”
int selection = a[left];
// 从左往右，相当于有 i 和 j 两个指针
int j = left + 1;
// 从左遍历到右边
for (int i = left + 1; i < n; i++) {
// 当遍历的值小于“中间值”时
// 交换 a[i] 和 a[j] 的值，同时 j 指针向右移动
// 当遇到比“中间值”大的值时，j 指针会“停止不动”，指向比“中间值”大的值
// 当 j 指针指向比“中间值”大的值后遇到了比“中间值”小的值时，两数交换位置，同时 j 指针向右运动，又回到指向比“中间值”大的值了
if (a[i] < selection) {
if (i != j) {
swap(a[i], a[j]);
}
j++;
}
}
// 遍历结束后，如果中途遇到了比比“中间值”大的值时，j 左边一定全部是比“中间值”小的数，所以将 j-1 指向的数与“中间值”交换
// 如果正好是逆序的情况，j 指针会指向 n ，即为数组右边界再向右一位， j-1 即是数组最后一位，与“中间值”交换后左侧全是小于“中间值”的
swap(a[left], a[j - 1]);
// 再递归“中间值”的左侧和右侧的数
QuickSort(a, left, j - 1);
QuickSort(a, j, n);
}
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = {37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 快速排序
QuickSort(a, 0, maxN);
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
还没有学具体的算法复杂度分析，具体看：https://zhuanlan.zhihu.com/p/341201904 (ToT)/~~~
空间复杂度因为涉及到递归，有压栈的操作，故为 O(log2n) ，稳定性来说因为分隔的数字交换有随机性，故不稳定。
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 快速排序 | O(n \log_2 n) | O(n^2) | O(n \log_2 n) | O(\log_2 n) | 不稳定 |
堆排序
堆排序我们需要一个堆，假设我们是大顶堆，就是一个完全二叉树，其中每个父节点比左节点和右节点都要大。
这里我们利用完全二叉树的一个性质，当我们数组存放完全二叉树是，那就是一个节点 i 的子节点的数组下标分别为 i 2 和 i 2 + 1 ，所以我们还需要维护整个大顶堆的整个顺序。
这里我们要定义两个函数，一个就是调整堆的函数，一个是排序的入口函数。
首先是调整堆的函数：
我们以一般情况为例，假设是第 i 个节点，首先我们要查找它与两个子节点大小关系，我们要找出最大的那个充当第 i 个节点。假如我们找到了这三个中最大的节点 i 2，那我们需要交换它与 i 的位置。此时以 i 2 为父节点它的两个子节点就不一定都小于 i * 2 这个节点的值了，所以我们要进行递归操作，一直调整到不会出现这种情况为止。
其次是排序的入口函数：
我们输入一个序列，首先需要将以它为顶堆的完全二叉树符合每个父节点比左节点和右节点都要大的情况，我们首先要对整棵树进行调整。
我们首先从底部开始向上调整，第一个调整的是最后一个节点的父节点，即 n / 2 开始，调整过后再依次向上将每一个节点进行调整。
将整棵顶堆调整完毕后，接下来就可以开始排序操作了。
我们首先将堆顶的元素（数组下标为1）与最后一个叶子节点交换位置，那么最大的值就在序列数组的最后了，因为结尾的数现在在堆顶的位置，所以除去最后一个最大的值的情况下再去调整整个顶堆的顺序，那么第二个最大的数又出现了在堆顶，此时再将堆顶的元素（数组下标为1）与最后一个叶子节点交换位置，那么第二个最大的值就在序列数组的倒数第二个位置了。依次按照上面的规则进行操作，那么最终整个数组就是按照升序排列的了。
动画演示
没找到合适的动图讲解….www…
不过找到一个不错的视频讲解，这个合集的其他讲解也是很不错的：https://www.bilibili.com/video/BV1fp4y1D7cj/
示例代码
#include <iostream>
using namespace std;
/*
* 堆排序顶堆维护（数组从下标1开始）
* @param a 数组
* @param n 数组长度闭区间
* @param i 维护第几个
*/
void HeapAdjust(int a[], int n, int i) {
// 寻找子节点最大的
int maxIndex = i;
// 子节点1
if (i * 2 <= n && a[maxIndex] < a[i * 2]) {
maxIndex = i * 2;
}
// 子节点2
if (i * 2 + 1 <= n && a[maxIndex] < a[i * 2 + 1]) {
maxIndex = i * 2 + 1;
}
// 交换
if (maxIndex != i) {
// 交换位置，使其满足父节点大于两个子节点
swap(a[maxIndex], a[i]);
// 在交换过后可能其子节点的子节点们又不满足性质
// 故递归进行维护
HeapAdjust(a, n, maxIndex);
}
}
// 堆排序
void HeapSort(int a[], int n) {
// 从最后一个节点的父节点开始维护堆
for (int i = n / 2; i > 0; i--) {
HeapAdjust(a, n, i);
}
// 从最后一个排序
for (int i = n; i > 0; i--) {
// 将堆顶和最后的下标 i 的数交换位置
// 此时数组下标 i 的数为最大的
swap(a[1], a[i]);
// 再维护第一个到第 i - 1 个数
HeapAdjust(a, i - 1, 1);
}
}
int main() {
const int maxN = 11;
// 待排序的数组
int a[maxN] = {0, 37, 34, 19, 2, 16, 24, 6, 10, 40, 33};
// 堆排序
HeapSort(a, maxN - 1);
// 打印
for (int i = 1; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
堆排序的时间复杂度没有相关知识也比较难求得，这里就放出相应的列表大家康叭~ (oﾟvﾟ)ノ
还有，堆排序适用于 n比较大 的情况
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 堆排序 | O(n \log_2 n) | O(n \log_2 n) | O(n \log_2 n) | O(1) | 不稳定 |
归并排序
归并排序的基本方法是将两个有序的序列合并成一个有序的序列，这个算法还是会的。然后基本思想是把整个序列分为若干个子序列，最终整个序列被分为若干个只有一个元素的序列，将这些序列合并为 若干 / 2 个包含两个元素的序列，因为都是有序的，所以还可以进行两两合并为 若干 / 4 个包含四个元素的序列…如此往复，最终将会合成一个包含之前所有元素的有序序列。
动画演示
示例代码
#include <iostream>
using namespace std;
int tempMergeSort[10];
void MergeSort(int a[], int left, int right) {
// 结束条件
if (left >= right - 1) {
return;
}
int mid = left + (right - left) / 2;
// 细分子序列
MergeSort(a, left, mid);
MergeSort(a, mid, right);
// 归并排序的将两个有序序列合并为一个序列
// 两个子序列分别为 [left, mid) 和 (mid, right]
int i = left, j = mid, k = left;
// 当遍历到有一个数的数组越界为 NULL 的时候结束
while (a[i] && a[j] && i < mid && j < right) {
if (a[i] <= a[j]) {
tempMergeSort[k++] = a[i++];
} else {
tempMergeSort[k++] = a[j++];
}
}
// 到这里必定有一个序列已经合并完了
// 如果左子序列没有遍历完，则让它继续合并
while (i < mid) {
tempMergeSort[k++] = a[i++];
}
// 如果右子序列没有遍历完，则让它继续合并
while (j < right) {
tempMergeSort[k++] = a[j++];
}
// 将刚合并完的序列再返回到原来的数组中
for (int l = left; l < right; l++) {
a[l] = tempMergeSort[l];
}
}
int main() {
const int maxN = 10;
// 待排序的数组
int a[maxN] = { 37, 34, 19, 2, 16, 24, 6, 10, 40, 33 };
// 归并排序
MergeSort(a, 0, maxN);
// 打印
for (int i = 0; i < maxN; i++) {
cout << a[i] << ' ';
}
}输出：2 6 10 16 19 24 33 34 37 40
复杂度及稳定性
时间复杂度分析：
来源：https://www.cnblogs.com/tuyang1129/p/12857821.htm
image-20221208204443243
这样分析非常好理解！
因为需要在开辟一个临时数组，所以空间复杂度为O(n)；另外，当有两个数相同时，子序列合并操作并不会将两个数的顺序变换，故此算法稳定。
此算法适用于 需要稳定的时间复杂度为O(n)的排序
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 归并排序 | O(n \log_2 n) | O(n \log_2 n) | O(n \log_2 n) | O(n) | 稳定 |
复杂度总结列表
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 直接选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 直接插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 折半插入排序 | O(n^2) | O(n^2) | O(n \log_2 n) | O(1) | 稳定 |
| 希尔排序 | O(n^{1.25}) ~ O(1.6n^{1.25}) | - | - | O(1) | 不稳定 |
| 快速排序 | O(n \log_2 n) | O(n^2) | O(n \log_2 n) | O(\log_2 n) | 不稳定 |
| 堆排序 | O(n \log_2 n) | O(n \log_2 n) | O(n \log_2 n) | O(1) | 不稳定 |
| 归并排序 | O(n \log_2 n) | O(n \log_2 n) | O(n \log_2 n) | O(n) | 稳定 |
- 稳定的排序：冒泡排序、直接插入排序、折半插入排序、快速排序
- 不稳定的排序：直接选择排序、希尔排序、快速排序、堆排序
部分内容来自郭老师的PPT ( •̀ ω •́ )✧
如果发现有错误或者那个地方表述不当欢迎在评论区提出~~ 😘