《Algorithms Unlocked》读书笔记2——二分查找和排序算法

《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;
}

插入排序与选择排序时间差不多,如果移动操作太过耗时最好用选择排序。插入排序适用于数组一开始就已经“基本有序”的状态。

归并排序

归并排序中使用一个被称为分治法的通用模式。在分治法中,我们将原问题分解为类似原问题的子问题,并递归的求解这些子问题,然后再合并这些子问题的解来得出原问题的解。

  1. 分解:把一个问题分解为多个子问题,这些子问题是更小实例上的原问题。
  2. 解决:递归地求解子问题。当子问题足够小时,按照基础情况来求解。
  3. 合并:把子问题的解合并成原问题的解。

在归并排序中,我们把数组不断用二分法分解成两个小数组,直到每个数组只剩一个元素(基础情况)。再把小数组排好序并进行合并。

《Algorithms Unlocked》读书笔记2——二分查找和排序算法

// 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中的“第一本”进行比较,此时的“第一本”不一定是刚才的第一本了,因为已经有一本书放入书架了,不过该书堆的“第一本”任然是该书堆中最小的一本。直到把两堆书全部放入书架。

《Algorithms Unlocked》读书笔记2——二分查找和排序算法

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;
}

由于归并排序不是在原址上工作,需要拷贝出子数组,如果你的储存空间较小或空间非常宝贵,可能不适合使用归并排序。

快速排序

与归并排序类似,快速排序也是使用分治模式。与归并排序不同的是,快速排序是在原址上工作的,归并排序是拷贝出两个子数组进行操作并不在原址上工作。

在书架中随机挑选一本书作为主元(这里我们总是选择位于书架最末尾的那本书),所有小于主元的书放在主元左侧,所有大于或等于主元的书放在主元右侧,这时就把书分为左右两组(不包括主元),再分别对这两组书进行相同的操作(递归),直到子数组只剩一本书触发基础情况。

《Algorithms Unlocked》读书笔记2——二分查找和排序算法

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的分割线向右移一位。如下图

《Algorithms Unlocked》读书笔记2——二分查找和排序算法

// 主元:数组中随机挑选单独的一个数(这里我们总是选数组中的最后一位)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;
}

本例的快速排序总是选择最末尾的元素作为主元,称为确定的快速排序。如果每次选择主元时都从数组中随机选择,则称为随机快速排序,随机快速排序在测试中会快于确定的快速排序。

根据数据量的不同,储存空间的大小,存储速度的快慢,每个排序方法都有不同的表现,并不是说哪个方法一定是最快的,也不一定最快就是最好的,合适才是最好的。

上一篇:Django【进阶】权限管理


下一篇:进程分析之CPU