排序算法的详细介绍(一) -- 插入排序

常见排序算法归档介绍:

插入排序 Insertion Sort

算法描述

从第一个元素开始,该元素可以认为已经被排序.
取出下一个元素,在已经排序的元素序列中从后向前扫描.
如果该元素(已排序)大于新元素,将该元素移到下一位置.
重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置.
将新元素插入到该位置后.
重复步骤 2~5.

如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目.该算法可以认为是插入排序的一个变种,称为 二分查找排序.

Insertion_sort_animation

实例分析

数组: [5, 6, 3, 1, 8, 7, 2, 4], 排序过程:


[5]   6   3   1   8   7   2   4
  ↑   │
  └───┘
[5, 6]   3   1   8   7   2   4
↑        │
└────────┘
[3, 5, 6]  1   8   7   2   4
↑          │
└──────────┘
[1, 3, 5, 6]  8   7   2   4
           ↑  │
           └──┘
[1, 3, 5, 6, 8]  7   2   4
            ↑    │
            └────┘
[1, 3, 5, 6, 7, 8]  2   4
   ↑                │
   └────────────────┘
[1, 2, 3, 5, 6, 7, 8]  4
         ↑             │
         └─────────────┘
 
[1, 2, 3, 4, 5, 6, 7, 8]

Insertion_sort_example

代码实现

function insertionSort(array) {
  var length = array.length,
    i,
    j,
    temp;
  for (i = 1; i < length; i++) {
    temp = array[i];
    for (j = i; j >= 0; j--) {
      if (array[j - 1] > temp) {
        array[j] = array[j - 1];
      } else {
        array[j] = temp;
        break;
      }
    }
  }
  return array;
}

此文参考于 bubkoo.com,十分感谢.
所有引用内容版权归原作者所有.
使用知识共享“署名-非商业性使用-相同方式共享 3.0 中国大陆”许可协议授权.

常见排序算法归档介绍:

插入排序 Insertion Sort

算法描述

实例分析

代码实现

CATALOG

FEATURED TAGS