随笔分类
归并
看完此篇,练手:https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/,但注意一点:当数组长度 > 100000,最坏情况下是超出 Integer.MAX_VALUE,此时便需要 long来存.
同样是 分治思想,区别于快排
先递归进行排序,再进行合并
基本思想:
- 确定分界点:mid = l + r >> 1
- 递归排序,区间划分,即对子区间先进行排序 -> 此步结束后实际上已经是有序的两个区间的了
- 归并有序区间
- 对于两个有序的区间进行合并,这也是最难的一步
- 使用 双指针算法实现!
归并排序是稳定的 -> 数组中值相同的元素位置实际上是不会发生变化的
时间复杂度:O(NlogN),区别于快排,归并排序需要一个额外的数组空间.
static void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
// 递归划分区间
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
// k:记录已排好序中元素个数
// i:左区间起点
// j:右区间起点
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r) {
tmp[k ++] = arr[i] <= arr[j] ? arr[i ++] : arr[j ++];
}
// 可能存在有一个区间没有排完的情况
while (i <= mid) tmp[k ++] = arr[i ++];
while (j <= r) tmp[k ++] = arr[j ++];
// 将tmp已排好续的赋值给老数组
for (i = l, j = 0; i <= r; i ++, j ++) arr[i] = tmp[j];
}