数据结构与算法之排序: 归并排序 (Javascript版)

排序

• 排序：把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)

归并排序

• 该排序属于 分治 策略
• 将一个问题分解为两个问题来计算，计算完成之后，就会得到子任务的解，这些解不是最终问题的解，还需要merge起来
• 性能好，火狐的sort方法
• 思路
  • 分：把数组分成2半，再递归地对子数组进行"分"操作，直到分成一个个单独的数
  • 合：把两个数合并为有序数组，再对有序数组进行合并，直到全部子数组，合并为一个完整数组
    • 两个单独的数组成的数组，也是两个有序数组，这两个数组里都只有1个数
    • 合这个操作，就是不断合并有序数组
  • 如何合并两个有序数组
    • 新建一个空数组res, 用于存放最终排序后的数组
    • 比较两个有序数组的头部，较小者出队并推出res中
    • 如果两个数组还有值，就重复第二步
    • 两个数组都空了，合并完成

算法实现

function mergeSort(nums: number[]) {
    // 1. 内部核心函数
	function msFn(arr:number[]) {
        const len: number = arr.length;
		if (len < 2) return arr;
		const mid: number = Math.floor(len / 2);
		const left: number[] = arr.slice(0, mid);
		const right: number[] = arr.slice(mid);
		const orderLeft: any = msFn(left); // 排好序的左侧
		const orderRight: any = msFn(right); // 排好序的右侧
		const res: number[] = [];
		while(orderLeft.length || orderRight.length) {
			if(orderLeft.length && orderRight.length) {
				res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift());
			} else if (orderLeft.length) {
				res.push(orderLeft.shift());
			} else if(orderRight.length) {
				res.push(orderRight.shift());
			}
		}
		return res;
	}
    // 2. 开始排序
	const result = msFn(nums);
    // 3. 替换原数组
    nums.splice(0, nums.length, ...result);
}

const list: number[] = [5, 4, 3, 2, 1];
mergeSort(list);
console.log(list); // [1, 2, 3, 4, 5]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

总结

• 时间复杂度：O(nlogn)
  • 分：每次把数组分成两半，用时 O(logn)， log函数用于求$2^{?}$ = n, 自然 ? = $lo{g}_{2}n$, 即 O(logn)
    • 注意，凡是分的操作，基本都是logn
  • 合：O(n), 一个while循环体
• 上述开辟了额外空间, 一般是不推荐的，一般是交换下标 TODO