数据结构第九章排序课件.ppt

《数据结构第九章排序课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九章内部排序9.1概述9.2插入排序9.3快速排序9.4堆排序9.5归并排序9.6各种排序方法的综合比较9.1概述一、排序的定义二、内部排序和外部排序三、内部排序方法的分类一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97二、内部排序和外部排序若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列

2、的排序过程不可能在内存中完成，则称此类排序问题为外部排序。三、排序方法的稳定性能1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。2.当对多关键字的记录序列进行排序时，必须采用稳定的排序方法。排序之前:{·····Ri(K)·····Rj(K)·····}排序之后:{·····Ri(K)Rj(K)··········}例如：排序前(56,34,47,23,66,18,82,47)若排序后得到结果(18,23,34,47,47,56,66,82)则称该排序方法是稳定的;若排序后得到结果(1

3、8,23,34,47,47,56,66,82)则称该排序方法是不稳定的。3.对于不稳定的排序方法，只要能举出一个实例说明即可。4.快速排序、堆排序和希尔排序是不稳定的排序方法。例如:对{4,3,4,2}进行快速排序，得到{2,3,4,4}四、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区ki基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：插入类交换类选择类归并类1.插入类将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度

4、。2.交换类通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。3.选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。4.归并类通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。9.2插入排序实现“一趟插入排序”可分三步进行：3．将R[i]插入(复制)到R[j+1]的位置上。2．将R[j+1..i-1]中的所有记录均后移一个位置；1．在R[1..i-1]中查找R[i]的插入位置，R[1

5、..j].keyR[i].key

6、的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；for(j=i-1;R[0].key

7、List&L){//对顺序表L作直接插入排序。for(i=2;i<=L.length;++i)if(L.r[i].key

8、序是一种稳定的排序方法。因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中