乐趣区

关于javascript:javascript数据结构与算法归并排序

归并排序采纳了分治策略,在对数组进行排序的时候,先将数组宰割成更小的子数组,而后对子数组排序,最初排序后的子数组合并成一个实现的数组,在对子数组排序的时候能够应用雷同的策略持续对子数组进行宰割,直到子数组中只蕴含一个元素。
例如咱们须要数组 [3,2,6,4,8,1,7,5] 排序,首先将数组宰割成只蕴含单个元素的子数组:

[3] [2]  [6] [4]  [8]  [1]  [7]  [5]

将相邻的两个子数组合并,失去蕴含两个元素的已排序子数组:

[2, 3]   [4, 6]  [1, 8]  [5, 7]

持续两两合并:

[2, 3, 4, 6]  [1, 5, 7, 8]

最终就能够失去一个实现的排序好的数组了:

[1, 2, 3, 4, 5, 6, 7, 8]

上面看一下怎么用 JS 代码实现一个归并排序。
首先看一下怎么合并两个已排序的子数组,代码如下:

/**
 * 辅助办法,合并数组 arr 中的两个已排序的子数组
 * 作为例子只思考从小到大排序,其余排序可自定义比拟函数,相似于 Array#sort
 * @param {*} arr 数组
 * @param {*} start 起始地位
 * @param {*} end 完结地位(蕴含在范畴内)* @param {*} mid 两个子数组的宰割地位
 */
function merge(arr, start, end, mid) {
 // 须要合并的元素个数
 const count = end - start + 1;
 // 左侧已排序数组
 const left = arr.slice(start, mid + 1);
 // 右侧已排序数组
 const right = arr.slice(mid + 1, end + 1);
 // 退出守卫元素,这样能够不必判断子数组是否为空
 left.push(Infinity);
 right.push(Infinity);
 // 顺次取出两个子数组中的较小的值
 let i = 0;
 let l = 0;
 let r = 0;
 while(i < count) {if (left[l] < right[r]) {arr[start + i] = left[l];
 l++;
 } else {arr[start + i] = right[r];
 r++;
 }
 i++;
 }
}

能够把两个已排序的子数组看作是两堆扑克,每次从两队扑克中取出较小的一张牌,直到所有的牌取完,失去的就是一副排好序的扑克。

上面看一下如何应用递归实现归并排序:

首先计算出中心点将数组宰割成两个子数组,对两个子数组别离排序,最初调用 merge 函数将两个已排序的子数组合并失去最终的排序数组。

退出移动版