数据结构与算法 - 排序算法

【1】 基本排序算法

1.冒泡排序 (比较容易实现，但是是最慢的排序算法之一)

数据像气泡一样从数组的一端漂浮到另一端。算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们互换。
里层循环是两个相互比较，把最大的值放到最右边。外层循环表示把最大值放到最右边的循环的次数，直到最后剩下两个比较；

<!-- 写到数组原型上可以直接调用 -->
function bubbleSort() {
    var dataStore = this;
    var numElements = dataStore.length;
    var temp;
    for (var outer = numElements; outer >= 2; --outer) {
        for (var inner = 0; inner <= outer-1; ++inner) {
            if (dataStore[inner] > dataStore[inner+1]) {
                <!-- swap(dataStore, inner, inner+1); -->
                dataStore.swap(inner, inner+1);
            }
        }
    }
    return this;
}
Array.prototype.bubbleSort = bubbleSort;

swap是一个交换数组的方法
// 写到原型链上
Array.prototype.swap = function(index1, index2) {
let temp = this[index1];
this[index1] = this[index2];
this[index2] = temp;
return this;
}

2.选择排序

从数组的开头开始，将第一个元素和其他元素进行比较，检查完所有元素后，最小的元素会被放到元素的第一个位置，然后算法会从第二个位置继续第一个元素的操作。
取出数组中的每一位，然后和剩下的元素比较，把最小的放到首位。

<!-- 写到数组原型上可以直接调用 -->
function selectionSort() {
    var dataStore = this;
    var min, temp;
    for (var outer = 0; outer <= dataStore.length-2; ++outer) {
        min = outer;
        for (var inner = outer + 1;inner <= dataStore.length-1; ++inner) {
            if (dataStore[inner] < dataStore[min]) {
                min = inner;
            }
        }
        dataStore.swap(outer, min);
   }
   return this;
}
Array.prototype.selectionSort = selectionSort;

3.插入排序

用一个很形象的例子来解说插入排序吧。 就好比一摞钱，里边1分，一角，一元，两元，五元，十元，五十，一百……等等，大小规格都一样，按照大小顺序排列。
我们先拿出一张，再拿第二张，如果比第一张小，就放在它前面，如果比他大呢，就放在第一张的后边。再放第三张，第四张……以此类推。直至结束。

<!-- 写到数组原型上可以直接调用 -->
function insertionSort() {
   var dataStore = this;
   var temp, inner;
   for (var outer = 1; outer <= dataStore.length-1; ++outer) {
      temp = dataStore[outer];
      inner = outer;
      while (inner > 0 && (dataStore[inner-1] >= temp)) {
         dataStore[inner] = dataStore[inner-1];
         --inner;
      }
      dataStore[inner] = temp;
   }
   return this;
}
Array.prototype.insertionSort = insertionSort;

这三种基本排序算法，当处理的数据量小（100,1000）的时候，计时是差不多的，看不错区别的，但是当数据量达到10000甚至更多时就会出现计时不同的问题。对算法测试比较：
对10000个元素冒泡排序消耗的时间为1096ms，选择排序消耗计时为591毫秒，插入排序消耗计时为471毫秒。

下一章，高级排序算法。