沈阳农业大学信息与电气工程学院数据结构课件 第九章.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]; 大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排序。 如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。 一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。 内部排序方法分类 按所用策略不同，可分五类：插入排序、交换排序、选择排序、归并排序和基数排序。 按所需工作量，可分为三类：简单排序O(n2)、先进排序O(nlogn)、基数排序O(d*n)。 内部排序两种基本操作：1. 比较两个关键字的大小；2 .将记录从一个位置移动到另一个位置。 10.2 直接插入排序 直接插入排序的基本思想是：从数组的第二个单元开始，依次从原始数据中取出数据，并将其插入到数组中该单元之前的已排好序的序列中合适的位置处。 直接插入算法需要经过（n-1）趟插入过程。如果数据恰好应插入到序列的最后端，则不需移动数据，可节省时间，所以若原始数据大体有序，此算法可以有较快的运算速度。动画演示 直接插入排序图 直接插入排序算法 void insertsort (sqlist r, int n) { int i,j; for( i=2; i=n; i++) { r[0]=r[i]; /* r[0]用于暂时存放待插入的元素*/ j= i-1; /* j为待比较元素下标，初始时指向待插入元素前一个单元*/ 直接插入排序算法续 while (r[0].keyr[j].key) { r[j+1]=r[j]; j--; } r[j+1]=r[0]; /* 在j+1位置插入r[0]*/ } } 简单插入排序的时间复杂性是O(n2)(平均约为n2 /4)。 对于有相同关键字记录的情况，此算法是稳定的。 其他插入排序 折半插入排序：在有序表中进行查找和插入，从而查找操作可利用折半查找来实现，由此进行的插入排序称为折半插入排序。 希尔排序：对直接插入排序进行改进得到的一种插入排序方法。基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 冒泡排序 冒泡排序是一种简单而且容易理解的排序方法，它和气泡从水中不断往上冒的情况有些类似。 其基本思想是对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟（pass）。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。动画演示 冒泡排序过程图 需扫描的趟数视原始数据最初的排列次序的不同而不同，最坏的情况要进行（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;j=n-1;j++) if (r[j+1].key r[j].key) 冒泡排序算法