一天一算法 - 基础排序
准备
在实现排序算法之前，先介绍将用到的几个函数。比如说为了将数组中数字的顺序打乱，我们可能需要一个洗牌函数，为了记录代码运行的时间，我们需要一个记录时间的函数。下面来介绍这些函数的实现。
-
洗牌方法
function shuffle() { return Math.random() - 0.5; }
因为 Math.random() 方法产生的数值在 [0,1) 之间，所以这个方法可以确保返回的数值是随机的。有了这个函数之后，只需要将其传入数组的 sort() 方法作为参数即可打乱数组。这个方法借鉴自 《12 个 JavaScript 技巧》 一文。
- 记录时间
记录时间其实很简单，我们只需要在代码执行前获取到时间，然后执行完毕之后再获取一次时间，取二者之间的差值即可，就像下面这样。
var Clock = {
"time": function() {
this.start = new Date().getTime();
},
"timeEnd": function() {
this.end = new Date().getTime();
return Math.floor(this.end - this.start);
}
}
如果你在 Java 中利用上面这个方面来计时，那是合情合理的，不过我们这是在写 JavaScript 代码，我们的宿主环境非常体贴，为我们提供了 console.time() 和 console.timeEnd() 方法来帮助我们计算 js 代码执行的时间。
不过值得一提的是，如果你利用 Clock 对象来计时会让你感到失望，因为它计时不是太准确，我使用上面提到的方法对选择排序进行了千数量级的计时， Clock 对象给我的结果使 8ms 左右，而 console.time() 和 console.timeEnd() 给出的结果却是 4ms, 咋一看，好像时间长了两倍，当我在进行万数量级测验时，发现二者计时还是相差 4ms 左右，所以我的理解是，我们使用自定义计时方法是创建了一个对象，而这 4ms 使我们创建这个对象花费的时间。
好了，说的已经够多了，下面开始进入正题。
选择排序
选择排序的思想非常简单，首先，找到数组中最小的那个元素，然后将它和数组的第一个元素交换位置。其次，在剩下的元素中找到最小的元素，将它和数组的第二个元素位置交换。如此往复，直到整个数组排序。
从算法的思想中我们可以得出结论，在最好的情况下，也就是说数组元素全部有序的情况下，选择排序需要经历 N^2 / 2 次比较，0 次位置变换。在最差的情况下，也就是说所有数组元素一开始都不在最终位置上，需要经历 N^2 / 2 次比较和 N-1 次移位。
function selectionSort(array) {
var length = array.length,
min,
temp;
for(var i = 0; i < length; i++) {
min = i;
for(var j = i; j < length;j++) {
if (array[min] > array[j]) {
min = j;
}
}
if (min !== i) {
temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
可见，这种算法实现起来十分简单，不过遗憾的是这种排序算法用于处理小数组的排序尚能称职，对于比较多的数据却是无力回天，这也正是我们探索其他方法的动力所在，下面来讲一个同样简单但是性能优于选择排序的算法 —— 插入排序。
插入排序
插入排序的思想就是从第二个元素开始，与前面的元素进行比较，直到找到比当前元素还要小的元素之后，将元素放下来，然后将后面的元素依次后移，腾出位置。
举个例子来说，对于数组 [2， 1，0， 4]，首先从 1 也就是第二个元素开始，与前面的 2 进行对比，发现 1 比 2 小，而且 2 前面也没有元素了，所以要将 1 放置在 2 的前面，这个时候 2 就需要后移为 1 腾出位置，这个时候数组元素就变成了 [1, 2, 0, 4]。然后 0 与 2 比较，发现 0 比 2 小，这个时候交换 0 与 2 的位置，再 与 1 进行比较，发现 0 还是比 1 小，所以交换 1 与 0 的位置，这个时候数组就变成了 [0, 1, 2, 4]。4 与 2 比较，比 2 大，保持原位置不变。
那么，插入排序与选择排序的差别在哪里呢？选择排序会对余下的所有元素进行大小比较，而插入排序则不是这样，对位于 i 下标的元素来说，只要它在 （i-1） - 0 的路径中找到比 i 小的元素，它就会终止比较，这对于一个已经基本排序的数组来说，是一个非常大的优化。不过，有利也有弊，插入排序相对于选择排序的缺点就是它移动次数会显著增加。
在最佳情况下，也就是说对于一个有序数组，插入排序只需要 N-1 次比较和 0 次交换。在最差情况下，也就是对于一个逆序数组，它需要 N^2 / 2 次比较和 N^2 /2 次交换。
function swap(array, i, j) {
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
function insertionSort(array) {
var length = array.length,
temp;
for(var i = 1; i < length; i++) {
for(var j = i; j > 0 && array[j] < array[j - 1]; j--) {
swap(array, j, j-1);
}
}
}
插入排序平均情况下会比选择排序快一倍左右，我以万级数量级数据对这两个算法进行了比较，选择排序耗时 120 ms 左右， 插入排序在 65ms 左右。当然，这只是在我电脑上的数据，根据电脑配置的不同得出的结果会有所不同。
还有一点值得提及，对于一个基本有序的数据来说，插入排序可能比任何排序算法都要快，也就是说它可能比归并排序和快速排序还要快。那么该怎么定义基本有序呢？满足下面三个条件之一就可以了。
- 数组中的每个元素距离它的最终位置都不远。
- 一个有序的大数组接一个小数组。
- 数组中只有几个元素的位置不正确。
希尔排序
希尔排序其实就是对插入排序进行改进，让其适应大数组排序。看了插入排序的代码你可能也发现了一个问题，如果一个非常大的数组，比如千万数量级的数组，它是逆序的，使用插入排序的话，那么我们不得不将最后一个元素一步步的移动到第一位，将倒数第二个元素一步步的移动到第二位，这样的话真的是拖垮了这个算法的性能，也就是插入排序的最坏情况。
希尔排序只是对插入排序进行了一点点修改，却将这个算法的性能提升了一大截，将细节的作用展现的淋漓尽致。简单地说，希尔排序的思想就是使数组中任意间隔 h 的元素都是有序的，这样的数组被称为 h 有序数组。如果 h 很大，那么我们一次就可以将一个元素移动到很远的位置，这样就弥补了插入排序的缺陷。
所以，关键的就是这个 h 的值该如何选择呢？事实上算法的性能和 h 的大小是有关系的，不过到目前为止并不知道 h 选取什么值是最好的，所以我一般选择数组长度的 1/3 左右 。
function shellSort(array) {
var length = array.length,
temp,
h = 1;
while (h < length / 3) {
h = 3 * h;
}
while (h >= 1) {
for (var i = h; i < length; i++) {
for (var j = i; j >= h && array[j] < array[j - h]; j -= h) {
swap(array, j, j - h);
}
}
h = h / 3;
}
}
关于希尔排序的运行时间具体是多少，目前尚不清楚，只能说它的运行时间达不到平方级别，最坏情况下的比较次数与 N^（3/2） 成正比。
对于万级数量级数组，我用希尔排序只花了 8ms 的时间，相比于插入排序和选择排序，这种算法真是快了不知多少倍！
冒泡排序
对于冒泡排序是真的没什么好讲的了，它和选择排序一样，是各教科书介绍的重点，它的思想就是每次迭代将最大的元素排到末尾。我感觉这种算法在比较次数上和选择排序相同，而移动次数却又和插入排序差不多，所以性能比较差，是理论上的排序算法，并不实用。
function bubleSort(array) {
var length = array.length;
for (var i = 0; i < length; i++) {
for (var j = 0; j < length - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
}
}
}
}
