《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第八章 排序》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第八章 排序（94页珍藏版）》请在金锄头文库上搜索。
1、第八章 排序,数据结构,第八章 排序,第八章 排序,知 识 点 排序的基本概念 三种简单的排序方法：冒泡排序、直接选择排序、直接插入排序 堆排序 快速排序 归并排序 基数排序 难 点 堆排序 快速排序 归并排序 基数排序,要 求 熟练掌握以下内容： 熟悉各种内部排序方法的基本思想和特点 各种排序方法的优缺点、时、空性能和适用场合 熟悉并掌握三种简单排序算法、快速排序算法和堆排序算法 了解以下内容： 二路归并排序算法 基数排序算法,第八章目录,8.1 排序的基本概念 8.2 三种简单排序方法 8.3 堆排序 8.4 快速排序 8.5 归并排序 8.6 基数排序 8.7 应用实例及分析 小 结 习
2、题与练习,8.1 排序的基本概念,将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序(sort)。 对一批记录的排序，应该指定是根据记录中哪个域的数据进行排列。这个作为排序依据的数据域我们称之为关键字(key)。 本章讨论的排序均为按递增顺序排序，并假定要排序的记录均已存储在一个一维数组中。,该一维数组定义如下： #define MAXITEM 100 struct record KeyType key; /*关键字*/ ElemType data; /*其他域*/ sqlistMAXITEM;,大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排序。 如果在排序过
3、程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。 一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。,返回,8.2.1 简单选择排序,简单选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。 在每一趟扫描数据时，用一个整型变量跟踪当前最小数据的位置，然后，第i趟扫描只需将该位置的数据与第i个数据交换即可。这样扫描n-
4、1次，处理数据的个数从n每次逐渐减1，每次扫描结束时才可能有一次交换数据的操作。,图8.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
5、+1;j=n-1;j+) if (rj.key rmin.key) min=j; r0 = ri; /* r0用于暂时存放元素*/ ri = rmin; rmin =r0; ,8.2.2 冒泡排序,冒泡排序是一种简单而且容易理解的排序方法，它和气泡从水中不断往上冒的情况有些类似。 其基本思想是对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟（pass）。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，即将这两个数据进行互换。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。,图8.2 冒泡排序过程,需扫描的趟数视原始数据最初的排列次序的不同而不同，最坏的情
6、况要进行（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 (rj+1.key rj.key),冒泡排序算法续, flag=0; r0=rj; /* r0用于暂时存放元素*/ rj=rj
7、+1; rj+1=r0; if (flag=1) return; ,冒泡排序算法分析,冒泡排序算法的优点是比较容易理解，且当原始数据大体符合要求的次序时，运算速度较快。 但它不是高效率的算法，在最坏的情况下，如果输入数据的次序与排序要求的次序完全相反，冒泡排序需要进行n(n-1)/2次比较和n(n-1)3/2次移动，其数量级均为O(n2)。 对于有相同关键字记录的情况，冒泡排序是稳定的。,8.2.3 直接插入排序,直接插入排序的基本思想是：从数组的第二个单元开始，依次从原始数据中取出数据，并将其插入到数组中该单元之前的已排好序的序列中合适的位置处。 直接插入算法需要经过（n-1）趟插入过程。如
8、果数据恰好应插入到序列的最后端，则不需移动数据，可节省时间，所以若原始数据大体有序，此算法可以有较快的运算速度。,图8.3 简单插入排序,简单插入排序算法,void insertsort (sqlist r, int n) int i,j; for( i=2; i=n; i+) r0=ri; /* r0用于暂时存放待插入的元素*/ j= i-1; /* j为待比较元素下标，初始时指向待插入元素前一个单元*/,简单插入排序算法续,while (r0.keyrj.key) rj+1=rj; j-; rj+1=r0; /* 在j+1位置插入r0*/ 简单插入排序的时间复杂性是O(n2)。 对于有相同
9、关键字记录的情况，此算法是稳定的。,返回,8.3.1 堆的概念,堆排序（Heap Sort）是利用二叉树的一种排序方法。 堆（Heap）是与二叉排序树不同的一种二叉树，它的定义为：一个完全二叉树，它的每个结点对应于原始数据的一个元素，且规定如果一个结点有儿子结点，此结点数据必须大于或等于其儿子结点数据。 由于堆是完全二叉树，采用将结点顺序编号存入一维数组中的表示法比链接表示法节省存储空间，也便于计算。,设某堆的结点数共有n个，顺序将它们存入一维数组r中。根据顺序表示二叉树的特点，除下标为1的结点是整棵树的根结点而没有父结点以外，其余下标为j的结点（2jn）都有父结点，父结点的下标为i= 。 故
10、堆的条件可以表示成： rirj 当2jn且i=,图8.4 堆及其顺序存储结构,堆排序,由堆的定义可知，其根结点（即在数组中下标为1的结点）具有最大的数字，堆排序就是利用这一特点进行的。 实现堆排序需要解决二个问题： 1. 对一组待排序的数据，先将它们构建成一个堆，输出堆顶的最大数据； 2. 将余下的n-1个数据再构建堆，输出具有次小值的数据；如此反复进行下去，直至全部数据都输出，就可以得到排好序的元素序列。,8.3.2 构建堆,一般构建堆是采用一种称为筛选（sift）的算法。这种方法是将一个无序数据序列的构建堆的过程看作一个反复“筛选”的过程。 设原始数据为7，10，13，15，4，20，19
11、，8（数据个数n=8）。 首先把这些数据按任意次序置入完全二叉树的各结点中，由于原始数据的次序是任意的，此树一般不符合堆的条件，需要用筛选运算进行调整。,筛选运算是从最末尾结点的父结点开始，向前逐结点进行，直至筛选完根结点即形成此堆。 筛每个结点时，将其数值与其两个儿子结点中数值较大者进行比较，如小于该儿子结点数值，则与之进行交换，互换后又将它看成父结点，再与下一层的儿子结点进行比较，如此做下去，直至不小于其儿子结点的数值，或已筛到叶结点而不再有儿子结点了，此数据的筛选运算即完成。,图8.5 用筛选算法构建堆,筛选算法,设共有n个结点，置于一维数组r中，则筛选第v号结点的函数如下： void
12、sift (sqlist r, int v, int n) int i,j; i=v; j=2*i; /* j为i的左儿子结点下标*/ r0=ri; /* 将待筛数据暂存于r0中*/ while (j=n) if (jn & rj.keyrj+1.key),筛选算法续,j+; /* 如右儿子数据较左儿子大，将j改为右儿子下标*/ if (r0.keyrj.key) ri=rj; i=j; j=2*i;/*如待筛数据小于其儿子数据，则与其儿子数据互换*/ else j=n+1; /*筛选完成，令j=n+1，以便终止循环*/,筛选算法续, ri=r0; /*被筛结点数据放入最终位置*/ 令待筛结点
13、下标v由 逐次减小到1，反复调用函数sift，就可以得到符合条件的堆。,8.3.3 利用堆排序,利用堆进行排序的方法是从根结点逐个取出数据，每次将新的再提到根结点，如此反复进行，直到堆只剩下一个结点为止。 为了节约存储空间，要求排序得到的有序数据序列仍存放于原数组中，故将从根结点取出的数据由数组的末端起逐单元存放。每存放一个数据，同时将原来在该单元的数据换到根结点。但这样互换后一般会破坏堆的条件，因此需要对根结点再做依次筛选运算，即令v=1再调用一次函数sift，就又可形成新的满足条件的堆。,随着数组末端存放的由堆中取出的数据越来越多，堆的结点数逐渐减少，到取出了(n-1)个数据，堆中只剩下一
14、个结点，这个数据一定是全部数据中最小的一个，堆排序即全部结束。 图8.6所示是利用堆进行排序的前几步，排序前的初始情况如图8.5所示的已构建好的堆。图中虚线以下为已从根结点逐个取出的有序数据，以上则为剩下的完全二叉树的结点。,图8.6 堆排序,堆排序算法,void heapsort (sqlist r, int n) int i; for (i=n/2; i=1; i-) sift (r, i, n); /* 初始建堆*/ for (i=n; i=2; i-) /*进行n-1次循环，完成堆排序*/ r0=ri; /*将第1个元素同当前区间内最后一个元素互换*/ ri=r1; r1=r0; si
15、ft (r, 1, i-1); /*筛选r1结点，得到(n-1)个结点的堆*/ ,堆排序算法分析,整个堆排序过程的时间复杂性是n与h的乘积数量级，考虑到h与n的关系，其复杂性为O(nlogn)。 堆排序适合于待排序的数据较多的情况，对于存在相同关键字的记录的情况，堆排序是不稳定的。,返回,8.4 快速排序,快速排序是由冒泡排序改进而得到的，又称为分区交换排序，是目前内部排序中速度较快的方法。 基本思想：在待排序的n个数据中任取一个数据（通常取第一个数据），把该数据放入合适的位置，使得数据序列被此数据分割成两部分，所有比该数据小的放置在前一部分，所有比它大的放置在后一部分，即该数据排在这两部分的中间。此数据在进一步的运算过程中不必再动，以后的排序运算只需在划分成的每部分里进行，两部分之间也不会再有数据交换。,第一次划分以后，再用相同的算法对划成的两部分分别进行类似的运算，即从每一部分中任选一个数据将其划分成更小的两部分。依此递归地做下去，直至每个小部分中的数据个数为一个，排序过程就结束了。 图8.7所示为一个快速排序的例子，图中的方括号表示待排序部分，下面有横线的数据则是某次进行划分时所选的数据。,图8.7 快速排序,一趟快速排序采用从两头向中间扫描的办法。 假设原始数据已存于一个一维数组r中，具体的做法是：设两个指示器i和j，初始时i指向数组中的第一个数据，j指向最
