Fork me on GitHub

排序算法-插入排序

algorithm/insertion_sort/banner

插入排序类似于人们按数字或字母的顺序对数据进行排序。嗯~就像集合排队那样…

原理

插入排序会有两个循环。外层循环将数组挨个移动,而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循中选中的元素小,那么数组元素会向右移动,为内循环中的这个元素腾出位置。

下面对五个元素进行插入排序。初始列表如下:

E B A H D

第一次插入排序,第二个元素挪动到第一位:

B E A H D

第二次插入排序是对A进行操作:

B A E H D

A B E H D

第三次是对H进行操作,因为它比之前的元素都大,所以保持位置。最后一次是对D元素进行插入排序了,过程和最后结果如下:

A B E D H

A B D E H

放上相关的gif动图更有助于理解,如下:

algorithm/insertion_sort/insertion_sort_demo

你可以直接进入旧金山大学的David Galles教授做的站点–用HTML5实现的各种排序算法的动画比较进行查看更加详细的演示。

代码实现

插入排序的核心代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
function insertionSort(arr){
var temp , inner; // temp存中转元素值,inner存内嵌元素的下标
for(var outer = 1 ; outer <= arr.length-1 ; outer++){
temp = arr[outer];
inner = outer;
while(inner > 0 && arr[inner-1] >= temp){
arr[inner] = arr[inner-1];
inner--;
}
arr[inner] = temp;
}
}

更加详细的代码请戳demos/algorithm/insertion_sort.js

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)