《小白学数据结构》课件——第八章 排序.pptxVIP

主讲教师：

直接插入排序

算法思想算法演示算法实现性能分析

算法思想

算法思想第一步将序列中的第1个记录看成是一个有序的子序列第二步第2个记录起逐个进行插入，直至整个序列变成按关键字有序的序列为止。

算法思想进行比较后移记录插入适当位置从第二个记录逐个进行插入，到第n个记录共需n-1趟。

算法思想举例来理解算法思想例如无序序列14，7，4，32，10，28，6，12第一步：【14】，7，4，32，10，28，6，12【7，14】，4，32，10，28，6，12【4，7，14】，32，10，28，6，12【4，7，14，32】，10，28，6，12【4，7，10，14，32】，28，6，12【4，7，10，14，28，32】，6，12【4，6，7，10，14，28，32】，12【4，6，7，10，12，14，28，32】（递增的有序序列）

算法演示

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录0123456暂1709初态：22

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录0123456暂170922i=22626i=35050i=426*26*

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录0123456暂170922i=22626i=35050i=426*26*

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录0123456暂存222650170922i=22626i=3i=426*5026*i=5

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录0123456222650170922i=22626i=3i=426*5026*i=51717

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录01234562226501709i=226i=3i=4i=5171722265026*2217i=60909

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录01234562226501709i=226i=3i=4i=51722265026*17i=60909

算法演示无序序列22，26，50，26*，17，09*表示后面一个26将该序列存入顺序表L中，将L.r[0]作为监视哨用来暂存记录01234562226501709i=226i=3i=4i=517i=6090922265026*1709完成！

算法实现1.在R[1...i-1]里边查找R[i]的插入位置2.将R[j+1...i-1]中的所有记录均后移一个位置3.将R[i]插入到R[j+1]的位置上

voidinsert_sort(SqListL){inti,j;for(i=2;i=L.length;++i)if(L.r[i].keyL.r[i-1].key)//将L.r[i]插入有序子表{L.r[0]=L.r[i];//复制为哨兵L.r[i]=L.r[i-1];for(j=i-2;L.r[0].keyL.r[j].key;--j)L.r[j+1