基本思想
- 将序列拆成两个或两个以上分别排序，然后再合并成一个；
- 归并排序使用的 分而治之 是非常经典且常用的算法思想，分而治之思想有以下三个步骤：
- 分解（Divide）：将原问题划分为一些子问题，子问题的形式与原问题相同，只是规模更小；
- 解决（Conquer）：递归地求解出子问题。如果子问题的规模足够小，则停止递归，直接求解；
- 合并（Combine）：将子问题的解组合成原始问题的解；
- 采用分治思想，基于归并操作的一种稳定排序算法（稳定排序：对于关键字相等的元素在排序前后相对顺序保持不变）；
图解
复杂度
-
时间复杂度：
O(NlogN)- 递归时长：每一次都切割成原来的一半，即
N、N/2、N/4、......、1，2^n = N，n = log2^N 👉 O(logN)； - 每一层处理 N 个元素，一共有 logN 层，则时间复杂度为
O(NlogN)；
- 递归时长：每一次都切割成原来的一半，即
-
空间复杂度：
O(N)- 每次切割数组要产生两个子数组，这两个子数组的长度和为 N ，则空间复杂度为
O(N)； - 每次合并两个子数组要创建一个长度为 N 的数组，则空间复杂度为
O(N)； - 递归调用的深度是
O(logN)； - 则空间复杂度为
O(N) + O(N) + O(logN) 👉 O(N)；
- 每次切割数组要产生两个子数组，这两个子数组的长度和为 N ，则空间复杂度为
代码实现
/* 归并排序 */
function mergeSort(nums, left, right) {
// 终止条件
if (left >= right) return;
// 划分阶段
let mid = Math.floor((left + right) / 2); // 计算中点
mergeSort(nums, left, mid); // 递归左子数组
mergeSort(nums, mid + 1, right); // 递归右子数组
// 合并阶段
merge(nums, left, mid, right);
}
/* 合并左子数组和右子数组 */
function merge(nums, left, mid, right) {
// 左子数组区间为 [left, mid], 右子数组区间为 [mid+1, right]
// 创建一个临时数组 tmp ，用于存放合并后的结果
const tmp = new Array(right - left + 1);
// 初始化左子数组和右子数组的起始索引
let i = left,
j = mid + 1,
k = 0;
// 当左右子数组都还有元素时，进行比较并将较小的元素复制到临时数组中
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
tmp[k++] = nums[i++];
} else {
tmp[k++] = nums[j++];
}
}
// 将左子数组和右子数组的剩余元素复制到临时数组中
while (i <= mid) {
tmp[k++] = nums[i++];
}
while (j <= right) {
tmp[k++] = nums[j++];
}
// 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间 [left, right]
for (k = 0; k < tmp.length; k++) {
nums[left + k] = tmp[k];
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
比较排序🔮 希尔排序
上一篇
评论
