《DS课件数据结构9章节》由会员分享，可在线阅读，更多相关《DS课件数据结构9章节（24页珍藏版）》请在金锄头文库上搜索。
1、2019年6月13日,第九章 排 序,数据结构,2019年6月13日,9.1 排序的基本概念,什么是排序(Sorting)？ 简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来 (递增或递减)。排序是计算机中经常遇到的操作。 1.排序定义: 设R1 R2 R3 Rn 是n个记录，k1,k2, k3 kn为它们的关键字， 排序就是将记录按关键字递增（或递减）的次序排列起来。 2.分类 按记录的存放位置分类有 内排序：待排记录放在内存 外排序：待排记录放在外存 按排序原则分类（内排序） 插入排序 交换排序 选择排序 归并排序 基数排序 等等,2019年6月13日,3.稳性排序： 在待排记录
2、序列中，任何两个关键字相同的记录，用某种排序方法 排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。 例 设 49,38,65,97,76,13,27,49 是待排序列 排序后:13,27,38,49,49,65,76,97 稳定 排序后:13,27,38,49,49,65,76,97 不稳定 稳性排序的应用：,2019年6月13日,9.2 插 入 排 序,一、直接插入排序 依次将待排记录插入 到有序子表中，并使插入 子表后仍保持有序，直到 全部记录插入完毕；初始 时，有序子表中只有一个 元素。 插入排序的关键：如 何查找插入位置。直接插 入排序（也称为顺序插入 排序）是用顺序查
3、找法定 位插入位置。若采用二分 查找法定位插入位置则得 到另一种插入算法，二分插入排序。,待排元素序列：53 27 36 15 69 42 第一次排序： 27 53 36 15 69 42 第二次排序： 27 36 53 15 69 42 第三次排序： 15 27 36 53 69 42 第四次排序： 15 27 36 53 69 42 第五次排序： 15 27 36 42 53 69 直接插入排序示例,2019年6月13日,直接插入算法如下： 方法: Ki与Ki-1,K i-2,K1 依次比较，直到找到应插入的位置。 void insertsort(int r , int n) int i
4、,j; for(i=2; i=n; i+) r0=ri; /* 作为监视哨*/ j=i-1; while (r0rj) rj+1rj- -; /* 记录后移*/ rj+1=r0; /* 插入 */ ,2019年6月13日,二、希尔排序 1959年由D.L. Shell提出。 又称缩小增量排序(Diminishing-increment sort) 。 直接插入排序法简单，适用于记录较少，或待排记录基本有序的情 况，因为在直接插入排序中，只比较相邻的结点，一次比较最多把结点 移动一个位置。基于直接插入排序上是述特点，希尔提出了另一种插入 排序算法：对位置间隔较大距离的结点进行比较，使得结点在比较
5、以后 能够一次跨过较大的距离，这样就可以提高排序的速度。 基本思想： 1） 将待排序记录分为若干组，在各组内分别进行直接插入排序； 2） 作若干次使待排记录基本有序； 3） 对全部记录进行一次直接插入排序； 分组方法：选定一增量d，将间隔为d的记录作为一组。,2019年6月13日,例 待排记录 49 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 13 27 49 55 04 49 38 65 97 76 13 27 49 55 04 49 38 65 97 76 13 04 49 38 27 49 55 65 97 76 04
6、 13 27 38 49 49 55 65 76 97,2019年6月13日,9.3 交 换 排 序,交换排序的基本思想是两两比较待排序对象的关键码，如果发生逆 序(即排列顺序与排序后的次序正好相反)，则交换之，直到所有对象都 排好序为止。 9.3.1 冒泡排序（起泡排序） 思想：小的浮起，大的沉底。从左端开始比较。 第一趟：第1个与第2个比较，大则交换；第2个与第3个比较， 大则交换，关键字最大的记录交换到最后一个位置上； 第二趟：对前n-1个记录进行同样的操作，关键字次大的记录交换 到第n-1个位置上； 依次类推，则完成排序。,2019年6月13日,冒泡排序算法： void bubbles
7、ort( int r , int n ) int i, j=1, k=1, x; while ( j0 ) k=0; for ( i=0; in-j; i+) if ( ri+1 ri ) k+; x=ri; ri=ri+1; ri+1=x; j+; ,2019年6月13日,9.3.2 快速排序 基本思想 快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的 方法。其思想是取待排序的结点序列中某个结点的值作为控制值，采用 某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点 的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于 等于这个控制值。 快速排序的基本过程
8、1) 选定一记录R，将所有其他记录关键字k与该记录关键字k比较, 若 kk 则将记录换至R之后; 2) 继续对R前后两部分记录进行快速排序，直至排序范围为1。,2019年6月13日,2019年6月13日,27 38 13 49 76 97 65 49 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97,两趟快速排序结束,三趟快速排序结束,快速排序结束,2019年6月13日,快速排序算法 void qsort(int r,int left,int right) int i=left, j=right, k
9、, x; if (i=j) return; x=ri; do while (rj=x ,2019年6月13日,9.4 选 择 排 序,9.4.1 直接选择排序 基本思想： 首先从1n个元素中选出关键字最小的记录交换到第一个位置上。然 后再从第2 个到第n个元素中选出次小的记录交换到第二个位置上，依次 类推。 基本步骤: 1）从左至右扫描待排记录 Ri，Ri+1 ，Rn（初始 i=1），在已 扫描记录中选择关键字最小者，用 j 指示； 2） rj与ri交换； 3） 缩小范围 i=i+1； 重复1）2）3）直至i=n-1,2019年6月13日,直 接 选择 排序 示 例,49,38,65,97,7
10、6,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,2019年6月13日,直接选择排序的算法： void selectSort( int r , int n ) int i,j,x,min; for (i=1,in;+i） /*选择第i小的元素，并交换到位*/ min=i； for(j=i+1
11、;jn;+j) if ( rjrmin ) min=j; /*rmin 中存放的是第i小的元素*/ if(min!=i) x=ri ; ri=rmin; rmin=x ； /*交换*/ ,2019年6月13日,9.4.2 堆排序 (一)堆的描述：,2019年6月13日,3. 实现堆排序需解决两个问题： （1） 如何由一个无序序列建成一个堆？ （2） 输出堆顶元素后，如何将剩余元素调整成一个新的堆？,2019年6月13日,(三)筛选法 若已知结点Ri的左右子树已是堆，采用筛选法将以Ri为根的完 全二叉树也调整为堆？ 其基本思想是：因为Ri的左右子树已是堆，这两棵子树的根分别 是各自子树中关键字最
12、大(或最小)的结点，所以我们必须在Ri和它的 左右孩子中选取关键字最大(或最小)的结点放到Ri的位置上。若Ri 的关键字已是三者中的最大者(或最小) ，则无须做任何调整，以Ri为 根的子树已构成堆，否则必须将Ri和具有最大(或最小)关键字的左孩 子R2i或右孩子R2i+1进行交换。假定R2i的关键字最大(或最小) ， 将Ri和R2i交换位置，交换之后有可能导致R2i为根的子树不再是 堆，但由于R2i的左右子树仍然是堆，于是可以重复上述过程，将以 R2i为根的子树调整为堆，.，如此逐层递推下去，最多可能调整到 树叶。,2019年6月13日,(四) 算法 筛选算法 void sift(int r,
13、int n,int i) int j,x; x=ri; j=2*i; while (j=n) if (jn) ,2019年6月13日,堆排序算法 void heapsort( int r, int n ) int i,b; for (i=n/2;i0;i-) sift(r,n,i); for (i=n;i1;i-) b=R1; r1=ri; ri=b; sift(r,i-1,1); ,2019年6月13日,2019年6月13日,第四节 归 并 排 序,一 基本思想： 将两个或多个有序表归并成一个有序表 二 2 路归并 1） 设有n个待记录，初始时将它们分为n个长度为 1有序子表； 2） 两两归并相邻有序子表，得到若干个长度2为的有序子表； 3） 重复2）直至得到一个长度为n的有序表； 例：待排记录 49 38 65 97 76 13 27 49 38 49 65 97 13 76 27 49 38 49 65 97 13 27 76 49 13 27 38 49 49 65 76 97,2019年6月13日,
