直接插入排序.pptx

《直接插入排序.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章优化排序直接插入排序第10章优化排序插入排序插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录有序地插入到已排好序的记录子集中，直到将所有待排记录全部插入为止。打扑克牌时的抓牌就是插入排序一个很好的例子，每抓一张牌，插入到合适位置，直到抓完牌为止，即可得到一个有序序列。第10章优化排序直接插入排序直接插入排序是一种最基本的插入排序方法。其基本操作是将第i个记录插入到前面i-1个已排好序的记录中，具体过程为：将第i个记录的关键字Ki顺次与其前面记录的关键字Ki-1，Ki-2，…,K1进行比

2、较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于Ki的记录Kj，此时Kj后面必为空位置，将第i个记录插入空位置即可。完整的直接插入排序是从i=2开始的，也就是说，将第1个记录视为已排好序的单元素子集合，然后将第2个记录插入到单元素子集合中。i从2循环到n，即可实现完整的直接插入排序。第10章优化排序例设有一组关键字序列｛43，21，89，15，，28｝，这里n=6，即有6个记录。请将其按由小到大的顺序排序。第10章优化排序假设待排序记录存放在r[1..n]之中，为了提高效率，我们附设一个监视

3、哨r[0]，使得r[0]始终存放待插入的记录。监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界，具体算法描述如下：第10章优化排序voidInsertSort(RecordTyper[],intn){inti,j;for(i=2;i

4、j+1]=r[0]}//将待插入记录插入正确位置}第10章优化排序该算法的要点是：①使用监视哨r［0］临时保存待插入的记录；②从后往前查找应插入的位置；③查找与移动在同一循环中完成。第10章优化排序直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好，为此我们可以对直接插入排序做进一步的改进。在直接插入排序法的基础上，从减少“比较关键字”和“移动记录”两种操作的次数着手来进行改进。第10章优化排序从空间分析来看，它只需要一个记录的辅助空间，空间复杂度为O（1）。从

5、时间分析来看，外循环for执行了n-1次，每次循环的基本操作为:比较两个关键字的大小和移动记录。当原始记录的序列越接近有序，算法的执行效率就越高。第10章优化排序在算法中，由于待插入元素的比较是从后向前进行的，当遇到关键字小于或等于要插入记录的关键字就停止操作，从而保证了后面出现的关键字不可能插入与前面相同的关键字之前。所以，直接插入排序算法是稳定的。