《Algorithms Unlocked》是 《算法导论》的合著者之一 Thomas H. Cormen 写的一本算法基础，算是啃CLRS前的开胃菜和辅助教材。如果CLRS的厚度让人望而生畏，这本200多页的小读本刚好合适带你入门。
书中没有涉及编程语言，直接用文字描述算法，我用 JavaScript 对书中的算法进行描述。
二分查找
在排好序的数组中查找目标值x。在p到r区间中，总是取索引为q的中间值与x进行比较，如果array[q]大于x，则比较p到q-1区间，否则比较q+1到r区间，直到array[q]等于x或p>r。
// 利用二分法在已经排好序的数组中查找值x
function binarySearch(array, x) {
let p = 1;
let r = array.length - 1;
while (p <= r) {
let q = Math.round((p + r) / 2); //四舍五入取整
if (array[q] === x) {
return q;
} else {
if (array[q] > x) {
// 如果q没有减一，遇到找不到x的情况，
// 就会陷入while循环中出不来，因为p会一直等于r
r = q - 1;
} else {
p = q + 1;
}
}
}
return 'NOT-FOUND';
}
也可以把二分查找写成递归风格。
// 二分法递归风格
function recursiveBinarySearch(array, p, r, x) {
if (p > r) { // 基础情况
console.log('NOT-FOUND');
return;
}
let q = Math.round((p + r) / 2);
if (array[q] === x) { // 基础情况
console.log(q);
return;
} else {
if (array[q] > x) {
recursiveBinarySearch(array, p, q-1, x);
} else {
recursiveBinarySearch(array, q+1, r, x);
}
}
}
排序
选择排序
从第一个元素开始遍历，把该元素跟在它之后的所有元素进行比较，选出最小的元素放入该位置。
以书架上的书本排序为例。我们看一眼书架上的第一本书的书名，接着与第二本进行比较，如果第二本书的书名第一个字母的顺序小于第一本，那我们忘掉第一本书的书名，记下第二本书的书名，此时我们并没有对书籍进行移动，只是比较了书名的顺序，并把顺序最小的书名记在脑子里。直到与最后一本进行比较结束，我们把脑子里顺序最小的书名对应的书与第一本书对调了一下位置。
function selectionSort (array) {
for (let i = 0; i < array.length - 1; i++) {
let smallest = i;
let key = array[i]; // 保存当前值
for (let j = i + 1; j < array.length; j++) {
// 比较当前值和最小值，如果当前值小于最小值则把当前值的索引赋给smallest
if (array[j] < array[smallest]) {
smallest = j;
}
}
// 最小值和当前值交换
array[i] = array[smallest];
array[smallest] = key;
}
return array;
}
选择排序效率很低，因为选择排序进行了较多的比较操作，但移动元素的操作次数很少。所以当遇到移动元素相当耗时——或者它们所占空间很大或者它们存储在一个存储较慢的设备中——那么选择排序可能是一个合适的算法。
插入排序
以书架为例，假设前4个位置已经排好序了，我们拿起第五本书与第四本进行比较，如果第四本大于第五本，把第四本向右移动一个位置，再把第三本与第五本进行比较，如果第三本还大于第五本，把第三本向右移动一个位置，刚好放入第四本空出来的位置。直到遇到一本小于第五本的书或者已经没有书可以比较了，把第五本书插入小于它的那本书的后面。
function insertionSort (array) {
for (let i = 1; i < array.length; i++) {
let key = array[i]; // 把当前操作值保存到key中
let j = i - 1; // j 为当前值的前一位
// 在j大于等于0且前一位大于当前值时，前一位向右移动一个位置
while (j >= 0 && array[j] > key) {
array[j+1] = array[j];
j -= 1;
};
// 直到遇到array[j]小于当前操作值或者j小于0时，把当前值插入所空出来的位置
array[j+1] = key;
}
return array;
}
插入排序与选择排序时间差不多，如果移动操作太过耗时最好用选择排序。插入排序适用于数组一开始就已经“基本有序”的状态。
归并排序
归并排序中使用一个被称为分治法的通用模式。在分治法中，我们将原问题分解为类似原问题的子问题，并递归的求解这些子问题，然后再合并这些子问题的解来得出原问题的解。
- 分解：把一个问题分解为多个子问题，这些子问题是更小实例上的原问题。
- 解决：递归地求解子问题。当子问题足够小时，按照基础情况来求解。
- 合并：把子问题的解合并成原问题的解。
在归并排序中，我们把数组不断用二分法分解成两个小数组，直到每个数组只剩一个元素（基础情况）。再把小数组排好序并进行合并。
// array: 数组
// p: 开始索引
// r: 末尾索引
function mergeSort (array, p, r) {
if (p >= r) {
return;
} else {
// 不可以用四舍五入，找了一夜的bug竟然是因为四舍五入这个小蹄子
let q = Math.floor((p + r) / 2);
// 递归调用，把数组拆分成两部分，直到每个数组只剩一个元素
mergeSort(array, p, q);
mergeSort(array, q + 1, r);
// 把两个子数组排序并合并
merge(array, p, q, r);
}
return array;
}
程序的真正工作发生在 merge 函数中。归并排序不是原址的。
假设有两堆已经排好序的书，书堆A和书堆B。把A中的第一本与B中的第一本拿起来比较，小的那本放入书架中，再把A中的“第一本”和B中的“第一本”进行比较，此时的“第一本”不一定是刚才的第一本了，因为已经有一本书放入书架了，不过该书堆的“第一本”任然是该书堆中最小的一本。直到把两堆书全部放入书架。
function merge (array, p, q, r) {
let n1 = q - p + 1; // 子数组的长度
let n2 = r - q;
// 把两个子数组拷贝到B、C数组中
// slice不包含end参数，所以end参数要加一
let arrB = array.slice(p, q + 1);
let arrC = array.slice(q + 1, r + 1);
// 两个数组的最后一个元素设为无穷大值，确保了无需再检查数组中是否有剩余元素
arrB[n1] = Number.MAX_VALUE;
arrC[n2] = Number.MAX_VALUE;
// 因为回填入原数组的个数是固定的，所以无穷大值不会被填入，也无需判断是否有剩余
// 一旦B、C两个数组中的所有元素拷贝完就自动终止
// 因为B、C中的元素已经按照非递减顺序排好了，所以最小索引值对应的就是最小值
// 两个子数组的最小值比较，小的则为当前最小值
let i = j = 0;
for (let k = p; k < r + 1; k++) {
if (arrB[i] < arrC[j]) {
array[k] = arrB[i];
i++;
} else {
array[k] = arrC[j];
j++;
}
}
return;
}
由于归并排序不是在原址上工作，需要拷贝出子数组，如果你的储存空间较小或空间非常宝贵，可能不适合使用归并排序。
快速排序
与归并排序类似，快速排序也是使用分治模式。与归并排序不同的是，快速排序是在原址上工作的，归并排序是拷贝出两个子数组进行操作并不在原址上工作。
在书架中随机挑选一本书作为主元（这里我们总是选择位于书架最末尾的那本书），所有小于主元的书放在主元左侧，所有大于或等于主元的书放在主元右侧，这时就把书分为左右两组（不包括主元），再分别对这两组书进行相同的操作（递归），直到子数组只剩一本书触发基础情况。
function quickSort (array, p, r) {
if (p >= r) {
return;
} else {
let q = partition(array, p, r);
// 递归中不再包含array[q]，因为它已经处在正确的位置（左边所有元素都小于它，右边所有元素都大于或等于它）
// 如果递归调用还包含array[q]，就会陷入死循环
quickSort(array, p, q - 1);
quickSort(array, q + 1, r);
}
return array;
}
重要的操作都在 partition 函数中。这个函数把数组按照大于或小于主元分为左右两堆，并返回主元所在位置的索引q。注意，左右两堆数组并不是有序的（见上图），只是大于或小于主元。
在书架中随机挑选一本书作为主元（这里我们总是选择位于书架最末尾的那本书），此时主元位于最末尾。还未进行比较的为未知组，称为组U，位于主元左侧。小于主元的称为组L，位于书架最左侧。大于或小于主元的称为组R，位于组L左侧组U右侧。如下图。
我们拿起组U中最左侧的那本书，与主元进行比较，如果小于主元则放入组L，大于或等于主元则放入组R。放入组R的操作比较简单，只需要把组R和组U的分割线往右移一位，无需移动书籍。
放入组L的操作则比较复杂。我们将它与组R中最左侧的书籍进行调换，并将组L和组R之间的分割线向右移一位，将组R和组U的分割线向右移一位。如下图
// 主元：数组中随机挑选单独的一个数（这里我们总是选数组中的最后一位）array[r]
// 组L（左侧组）：所有小于主元的数，array[p...q-1]
// 组R（右侧组）：所有大于或等于主元的数，array[q...u-1]
// 组U（未知组）：还未进行比较的数，array[u...r-1]
function partition(array, p, r) {
let q = p;
// 遍历array[p...r-1]
for (let u = p; u < r; u++) {
// 如果未知数小于主元，放入组L
if (array[u] < array[r]) {
// 把未知数和组R最左侧值(array[q])进行交换，并让q和u往右移一位(加1)
let key = array[q];
array[q] = array[u];
array[u] = key;
q += 1;
}
// 如果未知数大于或等于主元，放入组R
// 无需其他操作，只需要把u往右移一位
}
// 把主元和组R最左侧值(array[q])进行交换，让主元位于组L合组R中间
let key = array[q];
array[q] = array[r];
array[r] = key;
return q;
}
本例的快速排序总是选择最末尾的元素作为主元，称为确定的快速排序。如果每次选择主元时都从数组中随机选择，则称为随机快速排序，随机快速排序在测试中会快于确定的快速排序。
根据数据量的不同，储存空间的大小，存储速度的快慢，每个排序方法都有不同的表现，并不是说哪个方法一定是最快的，也不一定最快就是最好的，合适才是最好的。