数据结构-第十章-排序(严蔚敏).ppt

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

1、数据结构第十章内部排序第十章内部排序知识点排序的基本概念三种简单的排序方法：冒泡排序、直接选择排序、简单插入排序堆排序快速排序归并排序基数排序难点堆排序快速排序归并排序基数排序第十章排序要求熟练掌握以下内容：熟悉各种内部排序方法的基本思想和特点各种排序方法的优缺点、时、空性能和适用场合熟悉并掌握三种简单排序算法、快速排序算法和堆排序算法了解以下内容：二路归并排序算法基数排序算法第十章排序第十章目录10.1排序的基本概念10.2三种简单排序方法10.3堆排序10.4快速排序10.5归并排序10.6基数排序10.7应用实例及分析小结习题与练习第十章排序10.

2、1排序的基本概念将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序(sort)。对一批记录的排序，应该指定是根据记录中哪个域的数据进行排列。这个作为排序依据的数据域我们称之为关键字(key)。本章讨论的排序均为按递增顺序排序，并假定要排序的记录均已存储在一个一维数组中。第十章排序该一维数组定义如下：#defineMAXITEM100structrecord{KeyTypekey;/*关键字*/ElemTypedata;/*其他域*/}sqlist[MAXITEM];第十章排序大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排

3、序。如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。返回第十章排序10.2.1简单选择排序简单选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。在每一趟扫描数据时，用一个整型变量跟踪当前最小数据的位置，然后，第i趟

4、扫描只需将该位置的数据与第i个数据交换即可。这样扫描n-1次，处理数据的个数从n每次逐渐减1，每次扫描结束时才可能有一次交换数据的操作。第十章排序图10.1简单选择排序第十章排序简单选择排序分析简单选择排序在(n-1)趟扫描中共需进行n(n-1)/2次比较，最坏情况下的互换次数为(n-1)，整个算法的时间复杂性为O(n2)。简单选择排序简单并且容易实现，适宜于n较小的情况。简单选择排序是不稳定的排序算法。第十章排序简单选择排序算法voidselectsort(sqlistr,intn){inti,j,min;for(i=1;i<=n-1;i++){min

5、=i;/*用min指出每一趟在无序区范围内的最小元素*/第十章排序简单选择排序算法续for(j=i+1;j<=n-1;j++)if(r[j].key

6、个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。第十章排序图10.2冒泡排序过程第十章排序需扫描的趟数视原始数据最初的排列次序的不同而不同，最坏的情况要进行（n-1）趟扫描，一般常常少于(n-1)趟即可完成。可以设置一个标志flag用来指示扫描中有没有进行数据交换，每趟扫描开始前将其置1。当这趟扫描至少出现一次互换时，将其置0。如某趟扫描后flag仍为1，说明此趟扫描已无数据互换，则排序结束，不必再继续扫描了。第十章排序冒泡排序算法voidbubblesort(sqlistr,intn){inti,j,flag;for(i=1;

7、i<=n-1;i++){flag=1;for(j=i;j<=n-1;j++)if(r[j+1].key

8、其数量级均为O(n2)。对于有相同关键字记录的情况，冒泡排序是稳定的。第十章排序