舞动的排序算法 – 直接插入排序

插入排序的基本思想：每次将一个待排序的记录，按照其关键字大小插入到前面已经排好序的子数组中的适当位置，直到全部记录插入完成为止。

属于插入排序的排序算法有直接插入排序、希尔（Shell）排序。

下面就来看下直接插入排序的舞蹈吧（乘着广告时间，抓紧回顾一下插入排序的基本思想吧~）

看完视频了，接下来看看关于直接插入排序算法的文字说明吧。

直接插入排序算法原理

直接插入排序算法假定待排序的记录存放在数组a[0...n]中，一共n+1个元素。

初始时，a[0]自成一个有序区，无序区为a[1...n]

从i=1开始到i=n结束，依次将a[i]插入到当前的有序区a[0...i-1]，直到生成含n+1个记录的有序区。

在上面的直接插入排序舞蹈当中，采用查找比较操作和记录移动操作交替进行的方法，

首先从无序区取第一个元素a[i]，将a[i]按照从右到左的顺序依次与有序区a[j]（j=i-1,i-2,…,0）中的元素进行比较

如果a[i]<a[j]，则将a[j]后移一位，j减1后，继续比较a[i]和a[j]，直到查找过程结束

如果a[i]>=a[j]，则查找过程结束，j+1即为a[i]插入的位置

3 0 1 8 7 2 5 4 9 6
原创文章请注明转载于知蚁博客，本文地址：http://www.letuknowit.com/archives/insert-sort-dance

相关文章