1: 把长度为 n 的输入序列分成两个长度为 n/2 的子序列;
2: 对这两个子序列分别采用归并排序;
3: 将两个排序好的子序列合并成一个最终的排序序列.
- Array.prototype.mergeSort = function() {
- let merge = function(left, right) {
- let resArr = []
- while(left.length && right.length) {
- // 这里 shift() 方法用于把数组的第一个元素从其中删除, 并返回第一个元素的值.
- if(left[0] < right[0]) {
- resArr.push(left.shift())
- }else {
- resArr.push(right.shift())
- }
- }
- return resArr.concat(left , right)
- }
- let mSort = function(arr) {
- let len = arr.length
- if (len < 2) {
- return arr
- }
- let index = Math.floor(len / 2),
- left = arr.slice(0,index), // 得到下标从 0~index-1 的数组
- right = arr.slice(index) // 得到下标从 index 开始到末尾的数组
- return merge(mSort(left) , mSort(right)) // 里面采用递归
- }
- // 这里 this 不能直接赋值数组, 我们就只能采取 splice 剪切数组再替换新的
- this.splice(0, this.length, mSort(this))
- }
- let arr = [2,9,5,7,1,1,6,3,3,4]
- arr.mergeSort()
- console.log("排序后:", arr.toString())
- // 1,1,2,3,3,4,5,6,7,9
来源: http://www.bubuko.com/infodetail-3463920.html