插入排序( Insert Sorting) 基本思想每步将一个待排序的对象按其排 序码大小,插入到前面已经排好序的一组对象 的适当位置上,直到对象全部插入为止 直接插入排序( (Insert sort) 基本思想当插入第i(≥1)个对象时,前面的 VI0,V[1l2…V[i-已经排好序。这时,用 V[i的排序码与Vi-1,Vi-2l,的排序码顺 序进行比较找到插入位置即将Ⅴ[插入,原 来位置上的对象向后顺移
插入排序 (Insert Sorting) ◼ 基本思想 当插入第i (i 1) 个对象时, 前面的 V[0], V[1], …, V[i-1]已经排好序。这时, 用 V[i]的排序码与V[i-1], V[i-2], …的排序码顺 序进行比较, 找到插入位置即将V[i]插入, 原 来位置上的对象向后顺移。 基本思想 每步将一个待排序的对象, 按其排 序码大小, 插入到前面已经排好序的一组对象 的适当位置上, 直到对象全部插入为止。 直接插入排序 (Insert Sort)
直接插入排序过程 23 5 temp 3 5 temp 49)②5(16)(08 21)(25)(49 08 i=2 25)(49)②25 08 3②66@ 2因 08
直接插入排序过程 i = 1 0 1 2 3 4 5 temp i = 2 0 1 2 3 4 5 temp 21 25 49 25* 16 08 21 25 49 25* 16 08 25 21 25 49 25* 16 08 21 25 49 25* 16 08 49 21 25 49 25* 16 08 i = 3 21 25 49 25* 16 08 25* 21 25 25* 49 16 08
21)(25)(25(49) 16 i=5 0((22(9
i = 4 i = 5 21 25 25* 49 16 08 16 16 21 25 25* 49 08 16 21 25 25* 49 08 08 16 21 25 25* 49 08
直接插入排序的算法 typedef int SortData; void InsertSort( SortData VIl int n)t /按非递减顺序对表进行排序 SortData temp; int i, j; for(i=l; i< n; i++)i temp=V; for(j=i;j>0;j--)/从后向前顺序比较 if temp<vj-l)vi=Vj-1; else breaks VI=temp
直接插入排序的算法 typedef int SortData; void InsertSort ( SortData V[ ], int n ) { //按非递减顺序对表进行排序 SortData temp; int i, j; for ( i = 1; i < n; i++ ) { temp = V[i]; for ( j = i; j > 0; j-- ) //从后向前顺序比较 if ( temp < V[j-1] ) V[j] = V[j-1]; else break; V[j] = temp; } }
算法分析 设待排序对象个数为n,则该算法的主程序执行 n-1趟。 排序码比较次数和对象移动次数与对象排序码的 初始排列有关。 最好情况下,排序前对象已按排序码从小到大有 序,每趟只需与前面有序对象序列的最后一个对 象比较1次,移动次对象,总的排序码比较次数 为n-1,对象移动次数为2(n-1)
算法分析 ◼ 设待排序对象个数为 n, 则该算法的主程序执行 n-1趟。 ◼ 排序码比较次数和对象移动次数与对象排序码的 初始排列有关。 ◼ 最好情况下, 排序前对象已按排序码从小到大有 序, 每趟只需与前面有序对象序列的最后一个对 象比较1次, 移动2次对象, 总的排序 码比较次数 为 n-1, 对象移动次数为 2(n-1)