数据结构 教学课件 作者 宗大华 陈吉人 09排序.ppt

《数据结构 教学课件 作者 宗大华 陈吉人 09排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第9章排序9.1排序的基本概念9.2插入排序9.3交换排序9.4选择排序排序，能使杂乱的无序数据变为有序。在将数据按某种规则排列有序后，就能大大提高对其查找和处理的效率。本章主要介绍以下几个方面的内容：排序的基本概念；基本的插入排序（直接插入排序、折半插入排序、表插入排序）算法；基本的交换排序（冒泡排序、快速排序）算法；基本的选择排序（直接选择排序、堆排序）算法。9.1排序的基本概念给定一组记录：r1、r2、…、rn，对应的关键字分别为：k1、k2、…、kn。将这些记录重新排列成顺序为：rs1、rs2、…、rsn，使得对应的关键字满足：ks1≤ks2≤…≤ksn的升序条件。这种重排一

2、组记录、使其关键字值具有非递减顺序的过程，就称为“排序”。让关键字排序后表现出一种非递增关系也是可以的，也是排序让关键字排序后表现出一种非递增关系也是可以的，也是排序。假定待排序记录中存在有相同关键字。若经某种排序之后，那些有相同关键字值的记录间的相对位置保持不变，那么称这种排序方法是“稳定的”，否则就是“不稳定的”。所谓“内排序”，是指待排记录序列全部存放在内存，整个排序过程也都在内存里完成；所谓“外排序”，是指内存中容纳不下所有待排记录序列，排序过程中需要不断地与外存进行数据交换。本章只介绍有关内排序的算法。9.2插入排序插入排序的基本思想是：一趟一个地将待排记录按照关键字大小，插入到已

3、经排好序的部分记录的适当位置中，使其成为一个新的有序序列，直到所有待排记录全部插入完毕。直接插入排序的基本思想是：初始时认可第1个记录已排好序，从第2个记录开始，总是用第i(2≤i≤n)个记录与前面排好序的i−1个记录的子序列进行顺序比较，插入到它的相应位置，得到i个排好序的子序列。这一过程直进行到最后一个记录时结束。9.2.1直接插入排序例9-1已知待排序记录的关键字为：77，44，99，66，33，55，88，22利用直接插入排序完成对它们的排序，给出最终的排序结果。解：把所有待排记录存放在一个一维数组A里，如图9-1的“初始状态”所示。图9-1直接插入排序的过程图9-2数据元素的存储结

4、构一维数组元素的存储结构应该如图9-2所示：算法9-1直接插入排序算法。已知有n个记录的待排序列存放在一维数组Ar里，该数组元素的存储结构如图9-2所示，要求对其进行直接插入排序。算法名为Ins_Sort()，参数为Ar、n。直接插入排序是一种稳定排序算法。Ins_Sort(Ar,n){for(i=2;i<=n;i++)/*总共要进行n−1次扫描*/{temp=Ar[i];/*每次扫描总是把被考察关键字存入临时单元*/j=i-1;/*j规定了这次比较范围的上界*/while((temp.key=1)){Ar[j+1]=Ar[j];j--;}Ar[j+1]=te

5、mp;/*完成插入*/}}图9-3直接插入排序过程的局部例9-2有待排序的关键字序列如下：138，219，365，513，491，412，953，276，977，738以图示的方法完成对它的直接插入排序。图9-4直接插入排序图示例9-3有待排记录关键字序列：49，66，35，76，25，85，76，32利用直接插入排序算法进行排序，考察它的稳定性。图9-5直接插入排序算法的稳定性折半插入排序在确定插入位置时，采用的比较方法是折半查找法（因为已排好序的子序列是一个有序表，可以对它实施折半查找），有时也称为“二分法插入排序”。9.2.2折半插入排序算法9-2折半插入排序算法。已知有n个记录的待排

6、序列存放在一个一维数组Ar里，该数组元素的存储结构如图9-2所示，要求对其进行折半插入排序。算法名为Bin_Sort()，参数为Ar、n。Bin_Sort(Ar,n){for(i=2;i<=n;i++){temp=Ar[i];low=1;high=i-1;while(low<=high){mid=(low+high)/2;if(temp.key>Ar[mid].key)low=mid+1;elsehigh=mid-1;}for(j=i-1;j>=high+1;j--)Ar[j+1]=Ar[j];Ar[high+1]=temp;}}待排序的7个记录的关键字为：55、23、72、68、36、84

7、、41，现在前6个关键字已经排好序。使用折半插入排序算法，来观察第7个关键字41的插入排序过程。折半插入排序算法只适用于顺序存储，它是一种稳定的排序方法。图9-6折半插入排序的局部过程表插入排序的基本思想，仍是不断地用被考察关键字与已排好序的子序列（比较范围）进行比较。只是是在记录的存储结构里增加了一个指针域，通过指针域的链接，让记录按照关键字的大小加以排列，使得排序中没有了记录的移动。9.2.3表插入排序例