排序算法之归并排序
📝个人主页:爱吃炫迈
💌系列专栏:数据结构与算法
🧑💻座右铭:道阻且长,行则将至💗
文章目录
- 归并排序
- 算法描述
- 算法原理
- 算法实现
- 代码实现
-
- 递归算法
- 非递归算法
- 💞总结💞
归并排序
归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
动图演示
算法描述
归并操作的描述如下:
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
- 设定两个指针,最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
- 重复步骤3直到某一指针超出序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
算法原理
归并排序算法的原理如下(假设序列有n个元素):
- 将序列每相邻两个数字进行归并操作,形成(n/2)或(n/2+1)个序列,排序后每个序列包含两个元素
- 将上述序列再次归并,形成(n/4)或(n/4+1)个序列,对每个序列进行排序
- 重复步骤2,直到所有元素排序完毕
算法实现
🌰举个栗子!
用归并排序算法实现数列{4,1, 3, 2}的升序排序
- 整体思路就是先拆分,再合并
拆分数列
合并数列
🪄🪄🪄开始排序啦~~~🪄🪄🪄
初始状态
4,1, 3, 2
第一次归并排序
{1,4}, {2, 3}
第二次归并排序
{1,2, 3, 4}
归并排序圆满完成!!🎉🎉🎉
代码实现
递归算法
function merge(left, right){var result=[];while(left.length>0 && right.length>0){if(left[0]<right[0]){/*shift()方法用于把数组的第一个元素从其中删除,并返回第一个元素的值。*/result.push(left.shift());}else{result.push(right.shift());}}return result.concat(left).concat(right);
}
function mergeSort(items){if(items.length == 1){return items;}var middle = Math.floor(items.length/2),left = items.slice(0, middle),right = items.slice(middle);return merge(mergeSort(left), mergeSort(right));
}
非递归算法
function mergePass(arr = []) {let t; // 迭代深度。let length = 1; // 将每个元素看作是相邻的数组长度为1。let N = arr.length; let temp = new Array(arr.length);//初始化一个数组,长度为arr.lengthfor (t = 0; Math.pow(2, t) < N; t++, length *= 2) { // 每次跳过的长度翻倍。const even = t % 2 === 0; // 复用 arr 和 temp 来回赋值。for (let left = 0; left < N; left += 2 * length) {// 左边数组起始位置 left 从0开始。const middle = left + length < N ? left + length : left;// 右边数组起始位置 middle 就是left + 一个数组长度length 但是不要超过 N 。const right = left + 2 * length < N ? left + 2 * length : N;// 右边界 right 就是 left + 两个数组长度。merge(even ? arr : temp, even ? temp : arr, left, middle, right);// 合并每两个相邻的数组。}}if (t % 2 === 0) {return arr; //返回arr}return temp; // 返回 temp 。
}
function merge(arr, temp, left, middle, right) {const leftEnd = middle - 1; // 通过右边数组的起始位置得到左边数组的结束位置。while (left <= leftEnd && middle < right) {// 如果‘指针’没有越界。if (arr[left] > arr[middle]) {// 如果左边数组第一个元素比右边数组第一个元素大。temp[left + middle - leftEnd - 1] = arr[middle++]; // 将右边数组最小的放入有序数组 temp(初始值为空)。} else {temp[left + middle - leftEnd - 1] = arr[left++]; // 将左边数组最小的放入有序数组 temp(初始值为空)。}}while (left > leftEnd && middle < right) {// 如果左边数组放完了,右边数组还有元素。temp[left + middle - leftEnd - 1] = arr[middle++]; // 那么依次将右边数组剩余的元素放入 temp 。}while (left <= leftEnd && middle >= right) {// 如果右边数组放完了,左边数组还有元素temp[left + middle - leftEnd - 1] = arr[left++]; // 那么依次将左边数组剩余的元素放入 temp 。}
}
let items = [4, 2, 3, 1];
let res = mergePass(items);
console.log(res);
💞总结💞
希望我的文章能对你学习归并排序有所帮助!