数据结构第八章-排序.ppt

《数据结构第八章-排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章排序第8章排序学习目的要求:掌握排序的概念和排序的种类。熟练掌握五类基本排序:插入排序、交换排序、选择排序、归并排序和基数排序的算法思想、算法实现和性能分析。8.1排序的基本概念8.2插入排序8.3选择排序8.4交换排序8.5归并排序8.6基数排序8.7几种排序方法的比较第8章排序8.1排序的基本概念将一组杂乱无序的数据元素（记录）按一定的规律顺次排列起来叫做排序(sort)。对一批记录的排序，应该指定是根据记录中哪个域的数据进行排列。这个作为排序依据的数据域我们称之为关键字(key)。排序方法：大多数的排序方法，数据是存储在内存中，并在内存中加以处理的，这种排序方

2、法叫内部排序。如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。内部排序方法插入排序选择排序交换排序归并排序直接插入排序折半插入排序……简单选择排序堆排序冒泡排序快速排序8.2插入排序插入排序（InsertionSort）的基本思想:每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的有序序列中的适当位置上，直到全部记录插入完成为止。根据具体插入方法的不同，插入排序可分为以下几种:直接插入排序----希尔排序折半插入排序----2ˉ路插入排序8.2.1直接插入排序直接插

3、入排序（StraightInsertionSort）是一种最简单的排序方法，它的基本操作是依次将记录序列中的每一个记录插入到有序序列中，使有序序列的长度不断地扩大。8.2插入排序其具体的排序过程可以描述如下:首先将待排序记录序列中的第一个记录作为一个有序序列，将待排序记录序列中的第二个记录插入到上述有序序列中形成由两个记录组成的有序序列，再将待排序记录序列中的第三个记录插入到这个有序序列中，形成由三个记录组成的有序序列，如此进行下去，直到最后一个记录也插入完成。简单插入排序例如:对如下序列按照关键字由小到大排序:(4220171328142315)[]2017132814

4、2315(1)42(2)[2042]171328142315(3)[172042]1328142315(4)[13172042]28142315(5)[1317202842]142315(6)[131417202842]2315(7)[13141720232842](8)[1314151720232820]15main(){inti,j;intr[9]={0,42,20,17,13,28,14,23,15};/*r[0]存放每次待插入的记录*/for(i=2;i<=8;++i)/*第一个数是有序的,为初始有序序列,i从2开始*/if(r[i]

5、需将r[i]插入到前面有序序列中,否则r[i]不需要插入,保持原来位置*/{r[0]=r[i];/*r[i]的值放入监视哨中*/for(j=i-1;r[0]

6、接插入排序算法的效率降低。但直接插入排序算法是一种稳定算法（如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。）8.2.2折半插入排序折半插入排序是对直接插入排序的改进算法，它是利用折半查找来实现插入位置的定位，因为折半查找的效率比较高，因此可以减少排序过程中的比较次数。适用于待排序的记录数量较大的情况。8.2插入排序一趟折半插入排序的步骤为:（1）初始化将待插入的记录存入r［0］中:r［0］←r［i］;给指定查找区间上下界指针赋值:low←1，high←i-1;（2）折半查找插入位置;（3）将插入位置后面的记录依次后移一个位置;（

7、4）将暂存在r［0］中的待插入记录放入找到的位置上。8.2插入排序main(){inti,j,low,high,m;/*low,high,m表示查找的上下界和中间位置*/intr[9]={0,42,20,17,13,28,14,23,15};for(i=2;i<=8;++i)/*r[1]是有序的,从r[2]开始排序*/{r[0]=r[i];/*将r[i]暂时存到r[0]*/low=1;high=i-1;/*置有序序列区间的初值*/while(low<=high)/*在r[low]到r[high]中折半查找插入位置*/{m=(l