数据结构排序.pptx

《数据结构排序.pptx》由会员分享，可在线阅读，更多相关《数据结构排序.pptx（36页珍藏版）》请在优知文库上搜索。

1、测绘计算机软件软件基础测绘计算机软件软件基础第第1010章章 排序排序第第3页页第第 4 页页（1）什么是排序？）什么是排序？ 将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来。顺次排列起来。（2）排序的目的是什么？）排序的目的是什么？存放在数据表中存放在数据表中按关键字排序按关键字排序（3）排序算法的好坏如何衡量？）排序算法的好坏如何衡量？排序速度排序速度（比较次数（比较次数+移动次数）移动次数）占内存辅助空间的大小占内存辅助空间的大小若两个记录若两个记录A和和B的关键字值相等，但排序后的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。的

2、先后次序保持不变，则称这种排序算法是稳定的。 便于查找！便于查找！第第 5 页页（4） 什么叫内部排序？什么叫外部排序？什么叫内部排序？什么叫外部排序？ 若待排序记录都在内存中，称为内部排序；若待排序记录都在内存中，称为内部排序； 若待排序记录一部分在内存，一部分在外存，则称若待排序记录一部分在内存，一部分在外存，则称为外部排序。为外部排序。注：外部排序时，要将数据分批调入内存来排序，中间结果注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。还要及时放入外存，显然外部排序要复杂得多。 （5） 内部排序的算法有哪些？内部排序的算法有哪些？按排序的规则不

3、同，可分为按排序的规则不同，可分为3大类：大类：v 插入排序插入排序v 线性插入排序、对半插入排序线性插入排序、对半插入排序v 交换排序交换排序v 冒泡排序、快速排序冒泡排序、快速排序v 选择选择排序排序v 简单选择排序、堆简单选择排序、堆排序排序# define MAXSIZE 20 / 顺序表的最大长度顺序表的最大长度Typedef int KeyType / 关键字数据类型为整型关键字数据类型为整型Typedef struct RedTypeKeyType key; / 关键字项关键字项InfoType otherinfo; / 其它数据项其它数据项 / 记录类型记录类型Typedef

4、struct SqlistRedType RMAXSIZE+1; / r0用作哨兵用作哨兵int length; / 表长表长 / 顺序表类型顺序表类型第第 6 页页第第 7 页页插入排序有多种具体实现算法：插入排序有多种具体实现算法： 1) 线性插入排序线性插入排序 2) 对半插入排序对半插入排序 每步将一个待排序的对象，每步将一个待排序的对象，按其关键码大小，插入到前面按其关键码大小，插入到前面已经排好序已经排好序的一组对的一组对象的适当位置上，直到对象全部插入为止。象的适当位置上，直到对象全部插入为止。简言之，边插入边排序。简言之，边插入边排序。第第 8 页页新元素插入到哪里？新元素插入

5、到哪里？例例1：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），）， 请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。R0 r1 r2 r3 r4 r5 r6 r7 r8 6 【13】 6 3 31 9 27 5 11 3 【6 13】 3 31 9 27 5 11 31 【3 6 13】31 9 27 5 11 9 【3 6 13 31】 9 27 5 11 27 【3 6 9 13 31】 27 5 11 5 【3 6 9 13 27 31】 5 11 11 【3 5 6 9 13 27 31】 11 【3 5 6 9 11 13 27 31 】 在

6、已形成的在已形成的有序表中有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后顺移。适当位置插入，把原来位置上的元素向后顺移。最简单的排序法！最简单的排序法！第第 9 页页void InsertSort(Sqlist &L) int i, j ;for (i=2; i=L.length; i+) L.R0=L.Ri; j=i-1; /* 设置哨兵设置哨兵 */while( LT(L.R0.key, L.Rj.key) ) L.Rj+1=L.Rj; j-; /* 查找插入位置查找插入位置 */L.Rj+1=L.R0; /* 插入到相应位置插入到相应位置 */算法的实现：算法的

7、实现：第第 10 页页例例1：关键字序列关键字序列T= （21，25，49，25*，16，08），），请写出直接插入排序的具体实现过程。请写出直接插入排序的具体实现过程。i=10 1 2 3 4 5 6i=2i=3i=5i=4i=6252525* * *161616080808解：解：假设该序列已存入一维数假设该序列已存入一维数组组R7中，中，将将R0作为哨兵作为哨兵（Temp）。则程序执行过程为：）。则程序执行过程为：初态：初态：因为在最坏情况下，所有元素的比较次数总和为因为在最坏情况下，所有元素的比较次数总和为（01n-1)O(n2)。其他情况下也要考虑。其他情况下也要考虑移动元素的次数。

8、移动元素的次数。 故时间复杂度为故时间复杂度为O(n2) 仅占用仅占用1个缓冲单元个缓冲单元O(1)因为因为25*排序后仍然在排序后仍然在25的后面的后面稳定稳定第第 11 页页比较次数大大减少，全部元素比较次数仅为比较次数大大减少，全部元素比较次数仅为O(nlog2n)。虽然比较次数大大减少，可惜移动次数并未减少，虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为所以排序效率仍为O(n2) 。仍为仍为 O(1) 稳定稳定一个想得到的改进方法：一个想得到的改进方法： 既然子表有序且为顺序存储结构，既然子表有序且为顺序存储结构，则插入时采用则插入时采用对分查找对分查找定可加速。定可加

9、速。 void BInsertSort(Sqlist &L) int i, j, low, high, mid ;for (i=2; i=L.length; i+) L.R0=L.Ri; /* 设置哨兵设置哨兵 */low=1 ; high=i-1 ; while (low=high+1; j-)L.Rj+1=L.Rj; L.Rhigh+1=L.R0; /* 插入到相应位置插入到相应位置 */第第 12 页页第第 13 页页 根据序列中两个结点关键字根据序列中两个结点关键字的比较结果，来对换在序列中的位置。算法是将关的比较结果，来对换在序列中的位置。算法是将关键字较大的结点向序列的尾部移动，关

10、键字较小的键字较大的结点向序列的尾部移动，关键字较小的结点向序列的前部移动，其不同点是它们各按特定结点向序列的前部移动，其不同点是它们各按特定的顺序来选择序列中比较的结点。的顺序来选择序列中比较的结点。交换排序有多种具体实现算法：交换排序有多种具体实现算法：（1）冒泡排序冒泡排序（2）快速排序）快速排序 第第 14 页页每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。每趟结束时，不仅能挤出一个最大值到最后面位置，每趟结束时，不仅能挤出一个最大值到最后面位置，还能还能同时部分理顺其他元素同时部分理顺其他元素；一旦下趟

11、没有交换发生，；一旦下趟没有交换发生，还可以还可以提前结束排序提前结束排序。顺序存储结构顺序存储结构 例：例：关键字序列关键字序列 T=(21，25，49，25*，16，08），请写出），请写出冒泡排序的具体实现过程。冒泡排序的具体实现过程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初初 态态第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第 15 页页#define FALSE 0#

12、define TRUE 1void BubbleSort(Sqlist &L) int j ,k , flag ;for (j=1; jL.length; j+) /* 共有共有n-1趟排序趟排序 */ flag=TRUE ;for (k=1; kL.length-j; k+) /* 一趟排序一趟排序 */ if (LT(L.Rk+1.key, L.Rk.key ) ) flag=FALSE ; L.R0=L.Rk ; L.Rk=L.Rk+1 ; L.Rk+1=L.R0 ; /* 若为逆序则将两个记录交换若为逆序则将两个记录交换 */if (flag=TRUE) break ;第第 16 页页

13、最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n- -1 次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i 趟趟(1 i n) 做了做了n- i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。次对象交换。此时的比较总次数此时的比较总次数KCN和记录移动次数和记录移动次数RMN为：为：11111233121nininninRMNnninKCN)()()()(O(n2) 考虑最坏情况下考虑最坏情况下O(1) 只在交换时用到一个缓冲单元

14、只在交换时用到一个缓冲单元稳定稳定25和和25*在排序前后的次序未改变在排序前后的次序未改变第第 17 页页通过一趟排序将一个无序区分割成两个独立的无通过一趟排序将一个无序区分割成两个独立的无序子区，其中前一部分子区中所有元素关键字均不大于后序子区，其中前一部分子区中所有元素关键字均不大于后一部分子区中元素关键字，然后对每一子区再进行分割，一部分子区中元素关键字，然后对每一子区再进行分割，直到整个线性表有序为止。直到整个线性表有序为止。线性表的分割过程：线性表的分割过程：选取表中一个选取表中一个元素元素Rk（一般选表中第一个元素），令（一般选表中第一个元素），令x=Rk称为控制关键字。称为控制

15、关键字。设置两个指示器设置两个指示器i, j，分别表示线性表第一个和最后一个元，分别表示线性表第一个和最后一个元素位置。素位置。将将j逐渐减小，逐次逐渐减小，逐次比较比较Rj与与x，直到出现一，直到出现一个个Rjx ，然后，然后将将Ri移移到到Rj位置。位置。如此反复进行，直到如此反复进行，直到ij为止，最后将为止，最后将x移移到到Rj位置，完位置，完成一趟排序。此时线性表以成一趟排序。此时线性表以x为界分割成两个子区间。为界分割成两个子区间。继续对子区间进行分割直到序列有序为止。继续对子区间进行分割直到序列有序为止。第第 18 页页例：例：关键字序列关键字序列 T=(21，25，49，25*

16、，16，08），请写出），请写出快速排序的具体实现过程。快速排序的具体实现过程。初初 态，态，21xRjx移动移动j，i=j，xRj 一趟排序结束一趟排序结束21，25，49， 25*，16， 0808，25，49，25*， 16 ， 0808，25， 49， 25* ，16，2508，16， 49 ，25*， 16，2508，16， 49 ，25*， 49，2508，16， 49， 25*， 49，2508，16， 21 , 25 * ，49，25ijjiijjiijijijint Patition(Sqlist &L , int low, int high) L.R0=L.Rlow ; /* R0作为临时单元和哨兵作为临时单元和哨兵 */Pivotkey= L.Rlow.key; /* 枢轴记录枢轴记录 */while (lowhigh) /* i=j时退出扫描时退出扫描 */ while (low=pivotkey)-high; L.Rlow=L.Rhigh; while (lowhigh & L.Rlow.key=pivotkey)+low; L.Rhigh=L.Rlow;L.