插入排序的 javascript 实现。

插入排序

排序问题

• 输入：n 个数的一个序列<a1, a2, ..., an>
• 输出：输入序列的一个排列<a1', a2', ..., an'>，满足a1' <= a2' <= ... <= an'

思路

插入排序的工作方式像许多人排序一手扑克牌：

1. 左手为空，桌子上牌面向下
2. 每次从桌子上拿走一张牌插入左手中正确的位置
3. 为了找到正确位置，从右到左将它与已经在手中的每张牌进行比较，然后插入
4. 重复步骤 2~3

js 实现

function insertionSort(iArr) {
  var oArr = [iArr[0]];
  var n = iArr.length;
  // 从左边开始，每次拿一个与已排列好的数组进行比较
  for (var i = 1; i < n; i++) {
    for (var j = 0; j < i; j++) {
      if (iArr[i] <= oArr[j]) {
        // 若介于小于该元素，则插入其前方
        oArr.splice(j, 0, iArr[i]);
        break;
      } else if (j === i - 1) {
        // 若比最后一个还大，则排在最右侧
        oArr.push(iArr[i]);
      }
    }
  }
  return oArr;
}

验证

insertionSort([5, 2, 4, 6, 1, 3]);
// 输出[1, 2, 3, 4, 5, 6]

insertionSort[5, 2, 12, 2, 134, 1, 3, 34, 4, 6, 1, 3]);
// 输出[1, 1, 2, 2, 3, 3, 4, 5, 6, 12, 34, 134]

单数组插入排序

思路

这里在一个数组中进行插入排序：

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
3. 如果该元素（已排序）小于新元素，将新元素插入该元素下一位置
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置，将新元素插入到该位置后
5. 若无，则将新元素插入最左侧
6. 重复步骤 2~5

js 实现

function insertionSort(iArr) {
  var n = iArr.length;
  // 从第一个元素开始，该元素可以认为已经被排序
  for (var i = 1; i < n; i++) {
    // 取出下一个元素，在已经排序的元素序列中从后向前扫描
    for (var j = i - 1; j >= 0; j--) {
      if (iArr[i] >= iArr[j]) {
        // 如果该元素（已排序）小于新元素，将新元素插入该元素下一位置
        iArr.splice(j + 1, 0, iArr.splice(i, 1)[0]);
        break;
      } else if (j === 0) {
        // 如果已是最小元素，则插入最左侧
        iArr.splice(j, 0, iArr.splice(i, 1)[0]);
      }
    }
  }
  return iArr;
}

验证

insertionSort([5, 2, 4, 6, 1, 3]);
// 输出[1, 2, 3, 4, 5, 6]

insertionSort[5, 2, 12, 2, 134, 1, 3, 34, 4, 6, 1, 3]);
// 输出[1, 1, 2, 2, 3, 3, 4, 5, 6, 12, 34, 134]