几种常见排序算法

前端开发在工作中很少会遇到这些算法，但作为一个程序员的基本素质需要了解。
毕竟，首先是个程序员，其次才是前端。

什么是算法

高德纳《计算机程序设计艺术》里对算法的归纳（符合以下5个定义的都叫算法）：

1. 输入：一个算法必须有零个或以上输入量
2. 输出：一个算法应有一个或以上输出量
3. 明确性：算法的描述必须无歧义，实际运行结果是确定的
4. 有限性：必须在有限个步骤内结束
5. 有效性：又称可行性。能够被执行者实现

权威书籍推荐《数据结构与算法分析》: 数据结构［算法分析／表栈队列／树／散列］／排序......

排序算法研究的是：N个正整数排序。

• 定义问题：
  数组array含有N个正整数，
  输入量为 array，
  请将array中的数字从大到小排列，
  输出量为排序好的数组。
• 例如：
  var array = [5,2,4,6,8];
  function sort(){
  //to do ...
  }
  sort(array) === [2,4,5,6,8];

结合算法可视化工具，一目了然，方便总结。

目录

• 冒泡排序
• 选择排序
• 插入排序
• 合并排序
• 快速排序

（默认按从小到大排序。）

1. 冒泡排序

现实场景：教官双手算法，较高的往后站。每遍历1次所有都将1个最大值往后放，直到遍历所有成员，排序结束。

冒泡排序.gif

js代码：

function bubbleSort(myArray){
  var len = myArray.length;
  var i;
  var j;
  var stop;

  for (i = 0; i < len - 1; i++){
    for (j = 0, stop = len - 1 - i; j < stop; j++){
      if (myArray[j] > myArray[j + 1]){
        swap(myArray, j, j + 1);
      }
    }
  }
  return myArray;
}

function swap(myArray, p1, p2){
  var temp = myArray[p1];
  myArray[p1] = myArray[p2];
  myArray[p2] = temp;
}

2. 选择排序

现实场景：教官一指算法，最矮的到前面来。每次选择最小的与前面互换位置。

选择排序.gif

js代码：

function selectionSort(myArray){

  var len = myArray.length,
    min;

  for (i=0; i < len; i++){

    // 将当前位置设为最小值
    min = i;

    // 检查数组其余部分是否更小
    for (j=i+1; j < len; j++){
      if (myArray[j] < myArray[min]){
        min = j;
      }
    }

    // 如果当前位置不是最小值，将其换为最小值
    if (i != min){
      swap(myArray, i, min);
    }
  }

  return myArray;
}
function swap(myArray, p1, p2){
  var temp = myArray[p1];
  myArray[p1] = myArray[p2];
  myArray[p2] = temp;
}

3. 插入排序

现实场景：扑克牌起牌。
基本思路：

1. 把数组分为[已排序]和[未排序]两部分。
2. 从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置。

插入排序.gif

js代码：

function insertionSort(myArray) {
    var len = myArray.length,       // 数组的长度
        value,                      // 当前比较的值
        i,                          // 未排序部分的当前位置
        j;                          // 已排序部分的当前位置

    for (i=0; i < len; i++) {
        value = myArray[i];          // 储存当前位置的值
        /*
         * 当已排序部分的当前元素大于value，
         * 就将当前元素向后移一位，再将前一位与value比较
         */
        for (j=i-1; j > -1 && myArray[j] > value; j--) {
            myArray[j+1] = myArray[j];
        }
        myArray[j+1] = value;
    }
    return myArray;
}

4. 合并排序(分而治之)

现实场景：领导任务拆分法。
基本思路：

1. 不断将数组对半分，直到每个数组只有一个。
2. 将分出来的部分重新合并。
3. 合并的时候按顺序排列。

合并排序.gif

js代码：

// 被拆分的数组重新合并
function merge(left, right) {
    var result = [],
        left_index = 0,
        right_index = 0;

    // 将两个数组合并
    // 合并的时候按从小到大的顺序
    while (left_index < left.length && right_index < right.length) {
        if (left[left_index] < right[right_index]) {
            result.push(left[left_index++]);
        } else {
            result.push(right[right_index++]);
        }
    }

    // 和其他数组拼接
    return result.concat(left.slice(left_index)).concat(right.slice(right_index));
}

function mergeSort(myArray) {
    // 只有一个数的时候退出递归
    if (myArray.length < 2) {
        return myArray;
    }

    var middle = Math.floor(myArray.length / 2),
        left = myArray.slice(0, middle),
        right = myArray.slice(middle);

    // 递归
    // 不断拆分只到一个数组只有一个数
    return merge(mergeSort(left), mergeSort(right));
}

5. 快速排序

现实场景：自私的认为，我前面的都比我矮，我后面的都比我高，每个人都只找准自己的位置。
基本思路：

1. 以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边。
2. 再按此方法对这两部分数据分别进行快速排序（递归进行）。
3. 不能再分后退出递归，并重新将数组合并。

合并排序.gif

js代码：

var quickSort = function(myArray) {　　
// 当被分的数组只剩一个时，退出递归
if (myArray.length <= 1) {
return myArray;
   }

// 中间基准值的index
var pivotIndex = Math.floor(myArray.length / 2);　　
// 基准值
var pivot = myArray.splice(pivotIndex, 1)[0];　　
var left = [];　　
var right = [];　　
// 小的放左边，大的放右边
for (var i = 0; i < myArray.length; i++) {　　　　
if (myArray[i] < pivot) {　　
left.push(myArray[i]);　
       } else {
right.push(myArray[i]);　
       }　　
   }　　
// 递归
// 把数组合并在一起
return quickSort(left).concat([pivot], quickSort(right));
};