# 排序和递归

# 排序算法

在生活中，我们离不开排序。例如体育课上按身高排的队；又如考试过后按成绩排的名次。在编程中也是如此，例如当开发一个学生管理系统，需要按照学好从小到大进行排序；开发一个平台，需要把同类商品按价格从高到低排序。（当然，一般前端不负责处理业务逻辑。）由此可见，排序无处不在。排序看似简单，但是背后却隐藏了多种多样的算法与思想。

一个算法的好坏是通过 时间复杂度 与 空间复杂度 来衡量的。简单来说，时间复杂度 就是执行算法的 时间成本 ，空间复杂度 则是执行算法的 空间成本 。

# 稳定性

稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面

不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面

# 复杂度

时间复杂度 与 空间复杂度 都是用 “大 O” 来表示，写作 O(*)。有一点值得注意的是，我们谈论复杂度，一般谈论的都是时间复杂度。

常见时间复杂度的 “大 O 表示法” 描述有以下几种：

一个算法在 N 规模下所消耗的时间消耗从大到小如下：

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n)

# 常见数组排序方法

# 冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
5. 之所以叫冒泡排序，每一轮两两比较之后，都会冒出一个本轮最大的数，将其移动到本轮尾部。

// 需要几个轮次 6个数排序 最大需要5轮
// 外层循环控制轮次
for (var i = 1; i < arr.length; i++) {
	for (var j = 0; j < arr.length - i; j++) {
		// 经过这样for循环,我们能找到本轮最大的数,并排在本轮尾部
		if (arr[j] > arr[j + 1]) {
			// 交换位置
			var temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
}
console.log(arr); // [1, 5, 12, 32, 40, 41]

# 选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

for (var i = 0; i < arr.length; i++) {
	var minIndex = i;
	for (var j = i + 1; j < arr.length; j++) {
		if (arr[minIndex] > arr[j]) {
			minIndex = j;
		}
	}
	if (minIndex !== i) {
		// 交换位置
		var temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
}
console.log(arr);

# 插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序的算法步骤如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤 2~5。

var len = arr.length;
var j, temp;
for (var i = 1; i < len; i++) {
	j = i - 1;
	temp = arr[i];
	while (j >= 0 && arr[j] > temp) {
		arr[j + 1] = arr[j];
		j--;
	}
	arr[j + 1] = temp;
}

# 堆排序

堆排序 是指利用 二叉堆 这种数据结构所设计的一种排序算法。堆是一个近似 完全二叉树 的结构，并同时满足 堆积的性质 ：即子节点的键值或索引总是小于（或者大于）它的父节点。

二叉堆分以下两个类型：

• 最大堆： 最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。

数组表示如下：[10, 8, 9, 7, 5, 4, 6, 3, 2]

• 最小堆：最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。

数组表示如下：[1, 3, 2, 6, 5, 7, 8, 9, 10]

堆排序的算法步骤如下：

• 把无序数列构建成二叉堆；
• 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶。

/* 堆下沉调整 */
function adjustHeap (arr, parentIndex, length) => {
	var temp = arr[parentIndex]; /* temp保存父节点值，用于最后赋值 */
	var childIndex = 2 * parentIndex + 1; /* 保存子节点位置 */
	while (childIndex < length) {
		/* 如果有右子节点，且右子节点大于左子节点的值，则定位到右子节点 */
		if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
			childIndex++;
		}
		/* 如果父节点小于任何一个子节点的值，直接退出循环 */
		if (temp >= arr[childIndex]) {
			break;
		}
		/* 无序交换，单向赋值即可 */
		arr[parentIndex] = arr[childIndex];
		parentIndex = childIndex;
		childIndex = 2 * childIndex + 1;
	}
	arr[parentIndex] = temp;
};
function heapSort(arr) {
	/* 把无序数列构建成最大堆 */
	for (let i = Math.floor(arr.length / 2); i >= 0; --i) {
		adjustHeap(arr, i, arr.length - 1);
	}
	for (let i = arr.length - 1; i > 0; --i) {
		/* 交换最后一个元素与第一个元素 */
		[arr[i], arr[0]] = [arr[0], arr[i]];
		/* 调整最大堆 */
		adjustHeap(arr, 0, i);
	}
	return arr;
}

# 递归

递归是一种编程模式，用于一个任务可以被分割为多个相似的更简单的任务的场景。

当一个函数解决一个任务时，在该过程中它可以调用很多其它函数。那么当一个函数调用自身时，就称其为递归。

# 两种思考方式

简单起见，我们写一个函数 pow(x, n)，它可以计算 x 的 n 次方，即用 x 乘以自身 n 次。

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

有两种实现方式。

1. 迭代思路：for 循环：

   function pow(x, n) {
   	let result = 1;
   
   	// 在循环中用 x 乘以 result
   	for (let i = 0; i < n; i++) {
   		result *= x;
   	}
   
   	return result;
   }
   
   alert(pow(2, 3)); // 8
   

2. 递归思路：简化任务，调用自身：

   function pow(x, n) {
   	if (n == 1) {
   		return x;
   	} else {
   		return x * pow(x, n - 1);
   	}
   }
   
   alert(pow(2, 3)); // 8
   

注意递归方式完全不相同。

当 pow(x, n) 被调用时，执行分为两个分支：

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

1. 如果 n == 1，所有事情都会很简单，这叫做递归的基础(跳出条件)，因为它立即得到显而易见的结果：pow(x, 1) 等于 x。
2. 否则，我们可以用 x * pow(x, n - 1) 表示 pow(x, n)。在数学里，可能会这么写 xn = x * xn-1。这叫做一个递归步骤：我们将任务转变为更简单的行为（x 的乘法）和更简单的同类任务调用（更小的 n 给 pow）。后面步骤继续简化直到 n 等于 1。

我们也可以说 pow 递归的调用自身 直到 n == 1。

比如，为了计算 pow(2, 4)，递归变体经过了下面几个步骤：

1. pow(2, 4) = 2 * pow(2, 3)
2. pow(2, 3) = 2 * pow(2, 2)
3. pow(2, 2) = 2 * pow(2, 1)
4. pow(2, 1) = 2

所以，递归生成了更简单的函数调用，然后 —— 更加简单，继续，直到结果变得很明显。

递归解决方案一般比迭代更简洁。

这里我们可以使用三元运算符 `?` 来替换 `if` 语句，从而让 `pow(x, n)` 更简洁并且可读性依然很高：

```js run
function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}
```

最大的嵌套调用次数（包括首次）称为递归深度。在我们的例子中，它正好等于 n。

最大递归深度受限于 JavaScript 引擎。我们可以确信基本是 10000，有些引擎可能允许更大，但是 100000 很可能就超过了限制。有一些自动优化能够缓解这个（「尾部调用优化」），但是它们还没有被完全支持，只能用于简单场景。

这就限制了递归的应用，但是递归仍然被广泛使用。有很多任务使用递归思路会让代码更简单，更容易维护。

# 斐波那契数列