背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读四个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》。

当前阅读周书籍：《数据结构与算法JavaScript描述》。

排序算法

基本排序算法

基本排序算法的核心思想是指对一组数据按照一定的顺序重新排列。重新排列时用到的技术是一组嵌套的for循环。其中外循环会遍历数组的每一项，内循环则用于比较元素。这些算法非常逼真地模拟了人类在现实生活中对数据的排序，例如纸牌玩家在处理手中的牌时对纸牌进行排序，或者教师按照字母顺序或者分数对试卷进行排序。

冒泡排序

冒泡排序算法，它是最慢的排序算法之一，但也是一种最容易实现的排序算法。

之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

冒泡排序的代码：

function bubbleSort() {
  var numElements = this.dataStore.length;
  var temp;
  for (var outer = numElements; outer >= 2; --outer) {
    for (var inner = 0; inner <= outer - 1; ++inner) {
      if (this.dataStore[inner] > this.dataStore[inner + 1]) {
        swap(this.dataStore, inner, inner + 1);
      }
    }
  }
}

使用bubbleSort()对10个数字排序：

var numElements = 10;
var mynums = new CArray(numElements);
mynums.setData();
console.log(mynums.toString());
mynums.bubbleSort();
console.log();
console.log(mynums.toString());

以上代码输出为：

10 8 3 2 2 4 9 5 4 3
2 2 3 3 4 4 5 8 9 10

在bubbleSort()函数中小心地加入toString()函数，就可以看到这个数组在排序过程中的当前状态：

function bubbleSort() {
  var numElements = this.dataStore.length;
  var temp;
  for (var outer = numElmeents; outer >= 2; --outer) {
    for (var inner = 0; inner <= outer - 1; ++inner) {
      if (this.dataStore[inner] > this.dataStore[inner + 1]) {
        swap(this.dataStore, inner, inner + 1);
      }
    }
    console.log(this.toString());
  }
}

当我们重新执行上述这段包含了toString()函数的程序时，会得到以下输出结果：

1 0 3 3 5 4 5 0 6 7
0 1 3 3 4 5 0 5 6 7
0 1 3 3 4 0 5 5 6 7
0 1 3 3 0 4 5 5 6 7
0 1 3 0 3 4 5 5 6 7
0 1 0 3 3 4 5 5 6 7
0 0 1 3 3 4 5 5 6 7
0 0 1 3 3 4 5 5 6 7
0 0 1 3 3 4 5 5 6 7
0 0 1 3 3 4 5 5 6 7

0 0 1 3 3 4 5 5 6 7

选择排序

选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

选择排序会用到嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素；内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

selectionSort()函数的代码：

function selectionSort() {
  var min, temp;
  for (var outer = 0; outer <= this.dataStore.length - 2; ++outer) {
    min = outer;
    for (var inner = outer + 1; inner <= this.dataStore.length - 1; ++inner) {
      if (this.dataStore[inner] < this.dataStore[min]) {
        min = inner;
      }
      swap(this.dataStore, outer, min);
    }
  }
}

将下面这行添加到swap之后，就可以看到选择排序函数运行后的输出结果：

console.log(this.toString());
6 8 0 6 7 4 3 1 5 10
0 8 6 6 7 4 3 1 5 10
0 1 6 6 7 4 3 8 5 10
0 1 3 6 7 4 6 8 5 10
0 1 3 4 7 6 6 8 5 10
0 1 3 4 5 6 6 8 7 10
0 1 3 4 5 6 6 8 7 10
0 1 3 4 5 6 6 8 7 10
0 1 3 4 5 6 6 7 8 10
0 1 3 4 5 6 6 7 8 10

0 1 3 4 5 6 6 7 8 10

插入排序

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

插入排序的代码：

function insertionSort() {
  var temp, inner;
  for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
    temp = this.dataStore[outer];
    inner = outer;
    while (inner > 0 && this.dataStore[inner - 1] >= temp) {
      this.dataStore[inner] = this.dataStore[inner - 1];
      --inner;
    }
    this.dataStore[inner] = temp;
  }
}

现在在一个数据集合上执行我们的程序，来看看插入排序是如何运行的：

6 10 0 6 5 8 7 4 2 7
0 6 10 6 5 8 7 4 2 7
0 6 6 10 5 8 7 4 2 7
0 5 6 6 10 8 7 4 2 7
0 5 6 6 8 10 7 4 2 7
0 5 6 6 7 8 10 4 2 7
0 4 5 6 6 7 8 10 2 7
0 2 4 5 6 6 7 8 10 7
0 2 4 5 6 6 7 7 8 10

0 2 4 5 6 6 7 7 8 10

高级排序算法

高级数据排序算法通常被认为是处理大型数据集的最高效排序算法，它们处理的数据集可以达到上百万个元素，而不仅仅是几百个或者几千个。

希尔排序

希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素。和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的就是相邻元素了。

希尔排序的工作原理是，通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法要用到的间隔序列可以提前定义好。有一些公开定义的间隔序列，使用它们会得到不同的结果。在这里我们用到了Marcin Ciura在他2001年发表的论文“Best Increments for the Average Case of Shell Sort”（http:bit.ly/1b04YFv,2001）中定义的间隔序列。这个间隔序列是：701, 301, 132, 57, 23, 10, 4, 1。

看下希尔排序算法的代码：

function shellsort() {
  for (var g = 0; g < this.gaps.length; ++g) {
    for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
      var temp = this.dataStore[i];
      for (var j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) {
        this.dataStore[j] = this.dataStore[j - this.gaps[g]];
      }
      this.dataStore[j] = temp;
    }
  }
}

对小数据集合执行希尔排序：

load('CArray.js');
var nums = new CArray(10);
nums.setData();
console.log('希尔排序前：\n');
console.log(nums.toString());
console.log('\n希尔排序中：\n');
nums.shellsort();
console.log('\n希尔排序后：\n');
console.log(nums.toString());

以上代码输出的结果为：

1. 希尔排序前：

6 0 2 9 3 5 8 0 5 4

1. 希尔排序中：

5 0 0 5 3 6 8 2 9 4 // 间隔5
4 0 0 5 2 6 5 3 9 8 // 间隔3
0 0 2 3 4 5 5 6 8 9 // 间隔1

1. 希尔排序后：

0 0 2 3 4 5 5 6 8 9

快速排序

快速排序是处理大数据集最快的排序算法之一。它是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。

这个算法首先要在列表中选择一个元素作为基准值（pivot）。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组的顶部。

快速排序的算法如下：

1. 选择一个基准元素，将列表分隔成两个子序列；
2. 对列表重新排序，将所有小于基准值的元素放在基准值的前面，所有大于基准值的元素放在基准值的后面；
3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2。

这个算法的JavaScript程序如下所示：

function qSort(list) {
  if (list.length == 0) {
    return [];
  }
  var lesser = [];
  var greater = [];
  var pivot = list[0];
  for (var i = 1; i < list.length; i++) {
    if (list[i] < pivot) {
      lesser.push(list[i]);
    } else {
      greater.push(list[i]);
    }
  }
  return qSort(lesser).concat(pivot, qSort(greater));
}

这个函数首先检查数组的长度是否为0。如果是，那么这个数组就不需要任何排序，函数直接返回。否则，创建两个数组，一个用来存放比基准值小的元素，另一个用来存放比基准值大的元素。这里的基准值取自数组的第一个元素。接下来，这个函数对原始数组的元素进行遍历，根据它们与基准值的关系将它们放到合适的数组中。然后对于较小的数组和较大的数组分别递归调用这个函数。当递归结束时，再将较大的数组和较小的数组连接起来，形成最终的有序数组并将结果返回。

测试创建一个由随机数字组成的数组，并直接对它进行排序：

function qSort(arr) {
  if (arr.length == 0) {
    return [];
  }
  var left = [];
  var right = [];
  var pivot = arr[0];
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return qSort(left).concat(pivot, qSort(right));
}
var a = [];
for (var i = 0; i < 10; ++i) {
  a[i] = Math.floor(Math.random() * 100 + 1);
}
console.log(a);
console.log();
console.log(qSort(a));

以上程序的输出结果为：

68,80,12,80,95,70,79,27,88,93

12,27,68,70,79,80,80,88,93,95

总结

对计算机中存储的数据执行的两种最常见操作是排序和检索，自从计算机产业伊始便是如此。这也意味着排序和检索在计算机科学中是被研究得最多的操作。本书讨论的许多数据结构，都对排序和查找算法进行了专门的设计，以使对其中的数据进行操作时更简洁高效。

本文介绍数据排序的基本算法和高级算法，这些算法都只依赖数组来存储数据。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。