选择排序
如果有一组数，按从大到小排列，遍历列表，找出最大的数并添加到一个新列表，再次这样做，找出第二大的数，以此类推，这样便可得到一个有序列表。
示例
// 找出最大元素
function findLargest(arr){
let largest = arr[0];
let largestIndex = 0;
for (let i in arr){
if (arr[i] > largest) {
largest = arr[i];
largestIndex = i;
}
}
return largestIndex;
}
// 对数组进行排序
function selectionSort(arr){
let newArr = []
while(arr.length > 0){
let largest = findLargest(arr);
newArr.push(arr.splice(largest, 1)[0])
}
return newArr
}
console.log(selectionSort([5, 3, 6, 2, 10]));
选择排序需要的总时间为 O(n × n)，即O(n2)。
需要检查的元素数越来越少
随着排序的进行，每次需要检查的元素数在逐渐减少，最后一次需要检查的元素都只有一 个。既然如此，运行时间怎么还是O(n2)呢?这个问题问得好，这与大O表示法中的常数相关，后面有机会我还详细解释一下。
没错，并非每次都需要检查n个元素。第一次需要检查n个元素，但随后检查的元素 数依次为n - 1, n - 2, ..., 2和1。平均每次检查的元素数为1/2 × n，因此运行时间为O(n × 1/2 × n)。 但大O表示法省略诸如1/2这样的常数，因此简单地写 作O(n × n)或O(n2)。
选择排序是一种灵巧的算法，但其速度不是很快。
快速排序
分而治之
在介绍快速排序之前先介绍一下“分而治之”（divide and conquer，D&C），一种著名的递归问题解决方法。
使用D&C解决问题的过程包括两个步骤：
- 找出基线条件，这种条件必须尽可能简单。
- 不断将问题分解(或者说缩小规模)，直到符合基线条件。
D&C 的工作原理：
- 找出简单的基线条件。
- 确定如何缩小问题的规模，使其符合基线条件。
D&C 并非可用于解决问题的算法，而是一种解决问题的思路。
快速排序
快速排序是一种常用的排序算法，比选择排序快得多。例如，C 语言标准库中的函数 qsort 实现的就是快速排序。快速排序也使用了 D&C。
首先根据 D&C 的步骤，我们需要找到基线条件：数组为空或只包含一个元素。在这种情况下，只需原样返回数组——根本就不用排序。然后缩小问题：分解数组，直到满足基线条件。从数组中选一个元素，作为基准值（pivot）。
接下来，找出比基准值小的元素以及比基准值大的元素，这个过程被称为分区（partitioning），会得到：
- 一个由所有小于基准值的数字组成的子数组
- 基准值
- 一个由所有大于基准值的数组组成的子数组
我们将得到的两个子数组再进行上述操作，直到都满足基线条件。这样我们便得到一个有序列表。
function quicksort(arr) {
if (arr.length < 2){
return arr
} else {
// 递归条件
let pivot = arr[0];
let less = [];
let greater = [];
for (let i in arr){
if (arr[i] < pivot){
less.push(arr[i])
} else if (arr[i] > pivot){
greater.push(arr[i])
}
}
return [...quicksort(less), pivot, ...quicksort(greater) ]
}
}
console.log(quicksort([5, 3, 6, 2, 10]));
分解数组的过程使用了归纳证明的思想，如果是两个元素的数组我们可以轻易对其排序，那如果是三个元素呢，我们可以将其拆分为两个元素的数组，和一个元素的数组，以此类推我们可以对任意长度数组进行拆分，那么我们可以任意长度数组排序。
归纳证明
归纳证明是一种证明算法行之有效的方式，它分两步:基线 条件和归纳条件。是不是有点似曾相识的感觉?例如，假设我要证明我能爬到梯子的最上面。 递归条件是这样的:如果我站在一个横档上，就能将脚放到下一个横档上。换言之，如果我站 在第二个横档上，就能爬到第三个横档。这就是归纳条件。而基线条件是这样的，即我已经站 在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端。
对于快速排序，可使用类似的推理。在基线条件中，我证明这种算法对空数组或包含一个 元素的数组管用。在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两 个元素的数组也将管用;如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用， 以此类推。因此，我可以说，快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明， 但它很有趣，并与D&C协同发挥作用。
快速排序的速度取决于选择的基准值，在最糟情况下，其运行时间为O(n2)。
