- 前言
- 归并排序
- 原理
- 代码实现
- 复杂度分析
- 总结
前言
归并排序是一种稳定的、时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)的排序算法，算是较快的算法。
与快速排序一样，主要思想是分治，不同的是快排自顶向下(类似于二叉树的前序遍历)，归并排序自底向上（类似于二叉树的后序遍历）。
平均：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
最坏：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
最好：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
空间：
O
(
n
)
O(n)
O(n)
归并排序 原理
归并排序是建立在归并操作上的一种有效的排序算法。将一个数组分为两个子数组，通过递归重复地将数组切分到只剩一个元素为止。然后将每个子数组中的元素排序后合并，通过不断合并子数组，最后就会得到一个排好序的大数组。
与快排一样，也是分而治之算法，主要包括两个步骤：
切分步骤：将大问题变为小问题，通过递归解决更小的子问题
合并步骤：将小问题的结果合并，以此找到大问题的答案。
图示
具体步骤
- 把长度为n的输入序列分成两个长度为n/2的子序列；再递归切分子序列；
- 如果数组长度小于等于1，无需排序，直接返回结果；
- 否则将当前数组分为两个子数组，递归排序这两个子数组；
- 将两个排序好的子数组合并成一个最终的排好序的数组。
实现代码
void Sort::merge_sort(vector复杂度分析& nums, int l, int r) { if (l == r) return; int mid = (l + r) >> 1; merge_sort(nums, l, mid); //[l, mid] merge_sort(nums, mid + 1, r); //[mid + 1, r] _merge(nums, l, mid, r); } void _merge(vector & nums, int l, int mid, int r) { int n= r - l + 1; vector res; int i = l, j = mid + 1; while (i <= mid && j <= r) { if (nums[i] <= nums[j]) res.push_back(nums[i]), i++; else res.push_back(nums[j]), j++; } while (i <= mid) res.push_back(nums[i]), i++; while (j <= r) res.push_back(nums[j]), j++; for (int i = 0; i < n; i++) nums[l + i] = res[i]; //*** nums = res XXXX }
时间复杂度：
O(nlog)：每次将数组切一半，要logn次才能将数组切到一个元素，故递归的层数的logn，在每一层中，要对子数组进行归并，要扫描所有元素，所以每一层需要n次扫描，时间复杂度就是层级乘以每层的操作=logn×n = O(nlogn)。
空间复杂度：
O(n)：在每一层中，需要一个临时数组来存放原先的数据，然后在这个数组中扫描子数组的元素，并将其排好序放回原来的数组，所以空间复杂度就是O(n).
归并排序采用分治思想，不断将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。
时间复杂度：
平均：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
最坏：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
最好：
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
空间复杂度：
O
(
n
)
O(n)
O(n)
