i=3 司目园丽同 25/49 2 252549 目同 01234 5 temp i=5 1621 2525*49 5 temp
21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 i = 4 08 0 1 2 3 4 5 temp 21 25 49 16 25* 08 i = 5 i = 3 25* 16 08
完成 08]162112525149 0 23 i=4时的排序过程 j=3 21 2525/46 0 1 23 4 5 temp j=221 2525* 49 2 4 5 temp
16 49 16 16 21 25 49 16 25* 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 08 i = 4 时的排序过程 0 1 2 3 4 5 temp 21 25 25* 49 完成 16 08 16 i = 4 j = 3 i = 4 j = 2
j=121125 252 49 08 16 0 2 j=021 2525 49 08 网 3 temp i=4 j=-1 j园园 2549 08 6 0 2 3 5 temp
25 25* 16 16 21 25 49 25* 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 49 25* 08 0 1 2 3 4 5 temp 21 25 25* 49 16 08 16 16 25 21 i = 4 j = 1 i = 4 j = 0 i = 4 j = -1 16
直接插入排序的算法 template <class Type> void dataList <Type>: Insertsort(i ∥按排序码Key非递减顺序对表进行排序 Element<Type> temp; int i,j; for(i=l; i< CurrentSize; 1++i temp= Vector[i]; for(j=i;j>0;j-)1后向前顺序比较 if(temp< Vector[j-1) Vector[i= Vector[j-1; else breaks Vector[il=temp;
直接插入排序的算法 template <class Type> void dataList <Type> :: InsertSort ( ) { //按排序码 Key 非递减顺序对表进行排序 Element<Type> temp; int i, j; for ( i = 1; i < CurrentSize; i++ ) { temp = Vector[i]; for ( j = i; j > 0; j-- ) //从后向前顺序比较 if ( temp < Vector[j-1] ) Vector[j] = Vector[j-1]; else break; Vector[j] = temp;
算法分析 设待排序对象个数为 currentsize=n,则该算 法的主程序执行n-1趟。 排序码比较次数和对象移动次数与对泉排序 码的初始排列有关。 最好情况下,排序前对象已按排序码从小到 大有序,每趟只需与前面有序对象序列的最 后一个对象比较次,移动次对象,总的排序 码比较次数为n-1,对象移动次数为2(n-1)
算法分析 ◼ 设待排序对象个数为currentSize = n, 则该算 法的主程序执行n-1趟。 ◼ 排序码比较次数和对象移动次数与对象排序 码的初始排列有关。 ◼ 最好情况下, 排序前对象已按排序码从小到 大有序, 每趟只需与前面有序对象序列的最 后一个对象比较1次, 移动2次对象, 总的排序 码比较次数为 n-1, 对象移动次数为 2(n-1)。 } }