排序算法（二）
归并排序
归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。提到分而治之一般就需要用到递归。
假如有两个排好序的数组：
// left 数组
[1,3,6]
// right 数组
[2,4,5]
将这两个数组放入下面的算法中：
let left = [1,3,6], right = [2,4,5];
function sort<T>(left: T[], right: T[]): T[]{
let i = 0, j = 0;
const result: T[] = [];
while(i < l.length && j < r.length){
result.push(l[i] < r[j] ? l[i ++] : r[j ++]);
}
return result.concat(i < l.length ? l.slice(i) : r.slice(j));
}
// 执行函数：
sort<number>(left, right);
程序会这样运算：
// 判断循环条件（满足）
1 < 2; result = [1]; i=1; j=0;
3 > 2; result = [1,2]; i=1; j=1;
3 < 4; result = [1,2,3]; i=2; j=1;
6 > 4; result = [1,2,3,4]; i=2; j=2;
6 > 5; result = [1,2,3,4,5]; i=2; j=3;
// j = 3; 循环结束
result.concat(l.slice(2)) --> result = [1,2,3,4,5,6]。
通过上面的算法可以看到，两个排好序的数组使用 merge 函数后可以合并成一个大的排好序的数组。归并排序就是利用这样的规则构建的。那小数组又如何排序呢？当一个数组只有一个元素时，这个数组不相当于排好序了吗？当 left、right 两个数组都是长度为 1 时，将他们传入 merge 函数中可以得到正确的排序结果。而我们可以把一个大数组分解成只有单个元素的小数组，然后合并、合并，最终就合并成了一个排好序的数组了！首先我们分解数组，然后合并数组，这就像是递归中的递推与回溯。比如下面的示意图：
归并排序
实现代码：
function mergeSort<T>(array: T[]): T[]{
var len = array.length;
if(len > 1){
// len 大于 1，表明数组最少有两个元素
const middle = Math.floor(len / 2);
// 把这个元素分裂成左右两个数组
const left = mergeSort(array.slice(0, middle));
const right = mergeSort(array.slice(middle, len));
// 将这两个数组再合并成排好序的数组
array = merge(left, right);
}
function merge(l: T[], r: T[]): T[]{
let i = 0, j = 0;
const result: T[] = [];
// while 循环停止时，r 或 l 数组必定有一个，它们里面的元素全部 push 进了 result 中
// l 或 r 都是已经排好序的小数组
while(i < l.length && j < r.length){
result.push(l[i] < r[j] ? l[i ++] : r[j ++]);
}
// 把剩下的元素合并到 result 数组后面（没有 push 到 result 中的元素都是值比较大的元素）
return result.concat(i < l.length ? l.slice(i) : r.slice(j));
}
// 当 length > 1 时，返回的是 left 和 right 小数组
// 执行完 merge 函数后，返回的是排序后的结果
return array;
}
堆排序
堆排序可以参考之前的一篇消息，里面介绍了二叉堆和堆排序的内容（堆排序在文章最后）。
链接：二叉堆与堆排序
排序算法的稳定性
在百度百科上，排序算法的稳定性定义为：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，
r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
这很好理解，比如我们之前的冒泡排序，两个元素相等时是不去做交换的，冒泡排序算法是稳定的。希尔排序则不是一个稳定的算法，比如下面的图片，第一个 16 最终会跑到第二个 16 的后面：
希尔排序不稳定
选择排序也不是一个稳定排序算法，例如有这么一个数组：[6,5,4,6,1,2]，第一轮排序时会选择 1 与第一个 6 交换，第一个 6 本来在前面，却跑到了第二个 6 的后面。
快速排序同样也是一个非稳定排序算法。假如主元就是数组的最后一个元素，而主元的前一个元素是与它相等的元素，例如：[6,45,10,4,11,36,23,29,29]，运行代码如下：
[6,45,10,4,11,36,23,29,29]
// 45 与 23 交换
[6,23,10,4,11,36,45,29,29]
// 最后 left 与 right 指针会指向 36 的位置
// 29 与 36 做交换，结果主元 29 跑到了倒数第二个元素（也是 29）的前面。
算法复杂度
算法复杂度分为时间复杂度和空间复杂度。
时间复杂度用来描述一个算法的运行时间，算法复杂度并不能准确地计算出一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。
空间复杂度是指执行这个算法所需要的内存空间（寄存器）。
这里主要说一下时间复杂度。
大 O 表示法
算法的复杂度可以用大 O 表示法表述。例如我们常见的冒泡排序的时间复杂度：O(n^2)，它是怎么算出来的呢？
假设有这么一个搜索程序：
function find(array, item){
for(let i = 0;i < array.length;i ++){
if(array[i] === item){
return i;
}
}
return -1;
}
将包含 10 个元素的数组：[1, ..., 10] 传递给函数，假如搜索 1 这个元素，那么循环中的判断语句就会执行 1 次，如果要搜索 11 这个元素，那么循环中的判断语句就会执行 10 次（找到最后都没找到）。这个函数在最好的情况下，开销是 1，在最坏的情况下开销是 10。可以得出这个函数的时间复杂度是 O(n)，n 是输入数组的大小（n 也表示为一个问题的规模）。
三种规则
大 O 表示法有三个运算规则。
- 用常数 1 取代运算时间中的所有加法常数；
例如下面的函数：
function fn(sum){
sum += 10; // {1}
console.log(sum); // {2}
}
当执行 fn 函数时，函数内部第一行会执行一次（{1} 处），第二行也会执行一次（{2}处），程序一共执行了两次，即：f(n) = 1 + 1。根据第一条规则，fn 函数的时间复杂度可以表示为 O(1)。
- 只保留最高项；
- 去除最高阶的常数；
例如下面的代码：
let number = 1; // 语句执行 1 次
while(number < n){ // 语句会执行 logn 次
number *= 2; // 语句执行 logn 次
}
上面算法中，假如这个循环执行了 m 次，那么 2^m = n，即：m = logn（log 以 2 为底）。所以整段代码的执行次数为 1 + 2*logn，时间复杂度为 O(logn)（只保留最高项，并且去掉高阶的常数）。
又例如下面的代码：
for(let i = 0;i < n;i ++){ // 执行 n 次
for(let j = 0;j < n;j ++){ // 执行 n^2 次
console.log(i * j); // 执行 n^2 次
}
}
外层循环和内层循环都是从零到 n，外层循环执行 n 次，内层循环就执行了 n^2 次，内层循环中的语句也执行了 n^2 次。因此总共执行了 2*n^2 + n 次，时间复杂度是 O(n^2)（去掉最高阶常数、只保留最高项）
指数阶
function f(n){
if(n == 0){
return 1;
}
return f(n - 1) + f(n - 1);
}
- n = 0，f(n) 执行 1 次；
- n = 1，f(n)=f(0)+f(0)，执行 2 次；
- n = 2，f(n)=f(1)+f(1)，执行 4 次；
- n = 3，f(n)=f(2)+f(2)，执行 8 次；
当 n 趋于无穷大时，f(n) = 2^0 + 2^1 + 2^2 +...+ 2^n = 2^(n+1) - 1。因此时间复杂度是 O(2^n)。
常见的时间复杂度比较
O(n!) > O(2^n) > O(n^3) > O(n^2) > O(n*logn) > O(n) > O(logn) > O(1)
常见的时间复杂度图表
复杂度越小说明算法设计的越合理，运算时间也就越短。
冒泡排序的时间复杂度
下面是冒泡排序的代码：
function bubbleSort(array){
var len = array.length;
for(let i = 0;i < len;i ++){
for(let j = 0;j < len - 1 - i;j ++){ // n*(n/2)
if(array[j] > array[j + 1]){
swap(array, j, j + 1);
}
}
}
return array;
}
假如 array 的长度是 n，则外层循环会被执行 n 次，而内层循环第一轮会执行 n-1 次，第二轮循环会执行 n-2 次，第 n 轮循环会执行 1 次，因此内层循环一共会执行 n*(n/2) 次。所以冒泡排序的时间复杂度是 O(n^2)。
下面是常见的排序算法的时间复杂度：
排序算法复杂度
更多有关算法的学习资料可以参考 CSND 上的一篇博文，这篇博文里面使用了许多动图生动的展示了各个排序算法排序过程。
超详细十大经典排序算法总结（java 代码）[1]
数组搜索算法
在一个数组中搜索特定的元素最简单的做法就是遍历数组，没有这个元素就返回 -1，有就返回索引。
function find<T>(array: T[], item: T): number{
for(let i = 0;i < array.length;i ++){
if(array[i] === item) return i;
}
return -1;
}
这种搜索算法是线性的（时间复杂度是 O(n)）。而且它适用于没有排好序的数组。
二分查找
二分查找算法的条件是被查找的数组是排好序的。
二分查找的思路：首先查找数组中间位置的元素是不是与被查找元素相等，如果相等就返回索引值，如果不相等，就看中间元素大于被查找元素，还是小于被查找元素。
如果小于就接着查找中间元素左边的所有子元素，也是先找中间的元素与被查找元素的关系。
如果大于就接着查找中间元素右边的所有子元素，也是先找中间的元素与被查找元素的关系。
这是一个递归的过程，如果被查找的数组长度是 1，并且不等于被查找元素，则说明没找到，返回 -1（递归的出口）。
代码实现：
function binarySearch<T>(array: T[], target: T): number{
var len = array.length;
// 空数组就直接返回 -1
if(!len) return -1;
// 有元素就调用 find 函数
return find<T>(array, target);
function find<T>(array: T[], target: T, low = 0, high = len - 1): number{
// 说明 low 与 high 指向同一个元素
if(low === high){
return array[low] === target ? low : -1;
}
// 不是指向同一个元素就求中间值
var mid = Math.floor((low + high) / 2);
if(array[mid] > target){
// 中间值大于目标元素，说明目标元素在数组的左半部分
return find(array, target, low, mid - 1);
}else if(array[mid] < target){
// 中间值小于目标元素，说明目标元素在数组的右半部分
return find(array, target, mid + 1, high);
}
// 等于目标元素，就直接返回中间索引
return mid;
}
}
二分查找速度很快。在最坏情况下二分查找的时间复杂度为 O(logn)，每次查找数组长度都会折半（n --> n/2 --> n/2/2 --> n/2^i）。假如一个数组的长度是 8，那么在最坏的情况下只需查找 3 次就可以找到目标元素。
参考资料
[1]
超详细十大经典排序算法总结（java 代码）: https://blog.csdn.net/weixin_41190227/article/details/86600821
【2】 排序算法（一）：点击查看
腾讯云开发者
