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

数据结构 第十章 内部排序 第十章 内部排序 知 识 点 排序的基本概念 三种简单的排序方法：冒泡排序、直接选择排序、简单插入排序 堆排序 快速排序 归并排序 基数排序 难 点 堆排序 快速排序 归并排序 基数排序 要 求 熟练掌握以下内容： 熟悉各种内部排序方法的基本思想和特点 各种排序方法的优缺点、时、空性能和适用场合 熟悉并掌握三种简单排序算法、快速排序算法和堆排序算法 了解以下内容： 二路归并排序算法 基数排序算法 第十章目录 10.1 排序的基本概念 10.2 三种简单排序方法 10.3 堆排序 10.4 快速排序 10.5 归并排序 10.6 基数排序 10.7 应用实例及分析 小 结 习题与练习 10.1 排序的基本概念 将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序(sort)。 对一批记录的排序，应该指定是根据记录中哪个域的数据进行排列。这个作为排序依据的数据域我们称之为关键字(key)。 本章讨论的排序均为按递增顺序排序，并假定要排序的记录均已存储在一个一维数组中。 该一维数组定义如下： #define MAXITEM 100 struct record { KeyType key; /*关键字*/ ElemType data; /*其他域*/ }sqlist[MAXITEM]; 大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排序。 如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。 一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。 10.2.1 简单选择排序 简单选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。 在每一趟扫描数据时，用一个整型变量跟踪当前最小数据的位置，然后，第i趟扫描只需将该位置的数据与第i个数据交换即可。这样扫描n-1次，处理数据的个数从n每次逐渐减1，每次扫描结束时才可能有一次交换数据的操作。 图10.1 简单选择排序 简单选择排序分析 简单选择排序在(n-1)趟扫描中共需进行n(n-1)/2次比较，最坏情况下的互换次数为(n-1)，整个算法的时间复杂性为O(n2)。 简单选择排序简单并且容易实现，适宜于n较小的情况。 简单选择排序是不稳定的排序算法。 简单选择排序算法 void selectsort (sqlist r, int n) { int i, j, min; for (i=1;i=n-1;i++) { min=i; /*用min指出每一趟在无序区范围内的最小元素*/ 简单选择排序算法续 for (j=i+1;j=n-1;j++) if (r[j].key r[min].key) min=j; r[0] = r[i]; /* r[0]用于暂时存放元素*/ r[i] = r[min]; r[min] =r[0]; } } 10.2.2 冒泡排序 冒泡排序是一种简单而且容易理解的排序方法，它和气泡从水中不断往上冒的情况有些类似。 其基本思想是对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟（pass）。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。 图10.2 冒泡排序过程 需扫描的趟数视原始数据最初的排列次序的不同而不同，最坏的情况要进行（n-1）趟扫描，一般常常少于(n-1)趟即可完成。 可以设置一个标志flag用来指示扫描中有没有进行数据交换，每趟扫描开始前将其置1。当这趟扫描至少出现一次互换时，将其置0。如某趟扫描后flag仍为1，说明此趟扫描已无数据互换，则排序结束，不必再继续扫描了。 冒泡排序算法 void bubblesort(sqlist r, int n) { int i,j,flag; for(i=1;i=n-1;i++) { flag=1; for( j=i