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

发表于 | 阅读 128

《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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 利用二分法在已经排好序的数组中查找值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';
}

也可以把二分查找写成递归风格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 二分法递归风格
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);
    }
  }
}

排序

选择排序

从第一个元素开始遍历，把该元素跟在它之后的所有元素进行比较，选出最小的元素放入该位置。

以书架上的书本排序为例。我们看一眼书架上的第一本书的书名，接着与第二本进行比较，如果第二本书的书名第一个字母的顺序小于第一本，那我们忘掉第一本书的书名，记下第二本书的书名，此时我们并没有对书籍进行移动，只是比较了书名的顺序，并把顺序最小的书名记在脑子里。直到与最后一本进行比较结束，我们把脑子里顺序最小的书名对应的书与第一本书对调了一下位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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个位置已经排好序了，我们拿起第五本书与第四本进行比较，如果第四本大于第五本，把第四本向右移动一个位置，再把第三本与第五本进行比较，如果第三本还大于第五本，把第三本向右移动一个位置，刚好放入第四本空出来的位置。直到遇到一本小于第五本的书或者已经没有书可以比较了，把第五本书插入小于它的那本书的后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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. 合并：把子问题的解合并成原问题的解。

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

mergesort1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 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中的“第一本”进行比较，此时的“第一本”不一定是刚才的第一本了，因为已经有一本书放入书架了，不过该书堆的“第一本”任然是该书堆中最小的一本。直到把两堆书全部放入书架。

mergesort2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
}

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

快速排序

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

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

quicksort1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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的分割线向右移一位。如下图

quicksort2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 主元：数组中随机挑选单独的一个数（这里我们总是选数组中的最后一位）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;
}

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

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