Three basic Sort Algorithms

[barretlee]

插入排序和选择排序是两种最基本的排序算法，思路完全不一样，但是细思一番，还是挺有意思的：

• insertion sort，插入排序，思路简单来说就是把自己插入到已排好序的列表中去，交换也是颇为频繁的。

function insertion(input) {
  for(var i = 1, len = input.length; i < len; i++) {
    for(var j = i; j > 0; j--) {
      if(input[j] < input[j - 1]) {
        input[j] = [input[j - 1], input[j - 1] = input[j]][0];
      }
    }
  }
  return input;
}

• selection sort，选择排序，选择排序只对最后一个被选中的元素排序。它会往后找到包括自己在内最小的一个元素，替换自己。简单来说就是把第 i 小的元素放到第 i 个序位上。

function selection(input) {
  for(var i = 0, len = input.length; i < len - 1; i++) {
    var min = i;
    for(var j = i + 1; j < len; j++) {
      if(input[j] < input[min]) {
        min = j;
      }
    }
    input[i] = [input[min], input[min] = input[i]][0];
  }
  return input;
}

而冒泡排序，就更简单了，从第一个元素开始，往后比较，遇到比自己小的元素就交换位置，交换的次数最多，自然也是性能最差的。

function bubble(input) {
  for(var i = 0, len = input.length; i < len - 1; i++) {
    for(var j = i + 1; j < len; j++) {
      if(input[j] < input[i]) {
        input[j] = [input[i], input[i] = input[j]][0];
      }
    }
  }
  return input;
}

[barretlee]

针对随机性排列不同（比如完全随机，顺序，倒序，半顺序等状态）的数据，三种效果也是不一样的，可以思考下。