数据结构排序.pptx

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

1、测绘计算机软件软件基础,第10章 排序,数据结构研究的内容,第 4 页,（1）什么是排序？将一组杂乱无章的数据按一定的规律顺次排列起来。,（2）排序的目的是什么？,存放在数据表中,按关键字排序,（3）排序算法的好坏如何衡量？时间效率 排序速度（比较次数+移动次数）空间效率 占内存辅助空间的大小稳定性 若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。,便于查找！,基本概念,第 5 页,（4）什么叫内部排序？什么叫外部排序？,若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序。,注：外部排序时，要将数据分批调入内

2、存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。,（5）内部排序的算法有哪些？,按排序的规则不同，可分为3大类：插入排序线性插入排序、对半插入排序交换排序冒泡排序、快速排序选择排序简单选择排序、堆排序,待排序记录的数据类型,#define MAXSIZE 20/顺序表的最大长度Typedef int KeyType/关键字数据类型为整型Typedef struct RedTypeKeyType key;/关键字项InfoType otherinfo;/其它数据项/记录类型Typedef struct SqlistRedType RMAXSIZE+1;/r0用作哨兵int lengt

3、h;/表长/顺序表类型,第 6 页,第 7 页,1、插入排序,插入排序的基本思想是：,插入排序有多种具体实现算法：1)线性插入排序 2)对半插入排序,每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。,简言之，边插入边排序。,第 8 页,（1）线性插入排序,新元素插入到哪里？,例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

4、 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】,在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。,最简单的排序法！,第 9 页,void InsertSort(Sqlist/*插入到相应位置*/,线性插入排序算法的实现：,第 10 页,例1：关键字序列T=（21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。,i=1,21,i=2,i=3,i=5,i=4

5、,i=6,25,49,25*,49,16,16,08,49,解：假设该序列已存入一维数组R7中，将R0作为哨兵（Temp）。则程序执行过程为：,初态：,16,25,21,16,完成!,时间效率：因为在最坏情况下，所有元素的比较次数总和为（01n-1)O(n2)。其他情况下也要考虑移动元素的次数。故时间复杂度为O(n2)空间效率：仅占用1个缓冲单元O(1)算法的稳定性：因为25*排序后仍然在25的后面稳定,第 11 页,（2）对半插入排序,优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。时间效率：虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为O(n2)。空间效率：仍

6、为 O(1)稳定性：稳定,一个想得到的改进方法：,既然子表有序且为顺序存储结构，则插入时采用对分查找定可加速。,对半插入排序算法实现 void BInsertSort(Sqlist/*插入到相应位置*/,第 12 页,第 13 页,根据序列中两个结点关键字的比较结果，来对换在序列中的位置。算法是将关键字较大的结点向序列的尾部移动，关键字较小的结点向序列的前部移动，其不同点是它们各按特定的顺序来选择序列中比较的结点。,2 交换排序,交换排序的基本思想是：,交换排序有多种具体实现算法：（1）冒泡排序（2）快速排序,第 14 页,（1）冒泡排序,基本思路：每趟不断将记录两两比较，并按“前小后大”（或

7、“前大后小”）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。前提：顺序存储结构,例：关键字序列 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#define TRUE 1

8、void BubbleSort(Sqlist,第 16 页,冒泡排序的算法分析,最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i 趟(1 i n)做了n-i 次关键码比较，执行了n-i 次对象交换。此时的比较总次数KCN和记录移动次数RMN为：,因此：时间效率：O(n2)考虑最坏情况下空间效率：O(1)只在交换时用到一个缓冲单元稳 定 性：稳定25和25*在排序前后的次序未改变,第 17 页,（2）快速排序,基本思路：通过一趟排序将一个无序区分割成两个独立的无序子区，其中前一部分子区中所有元素关键字均不大于后

9、一部分子区中元素关键字，然后对每一子区再进行分割，直到整个线性表有序为止。,线性表的分割过程：选取表中一个元素Rk（一般选表中第一个元素），令x=Rk称为控制关键字。设置两个指示器i,j，分别表示线性表第一个和最后一个元素位置。将j逐渐减小，逐次比较Rj与x，直到出现一个Rjx，然后将Ri移到Rj位置。如此反复进行，直到ij为止，最后将x移到Rj位置，完成一趟排序。此时线性表以x为界分割成两个子区间。继续对子区间进行分割直到序列有序为止。,第 18 页,例：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序的具体实现过程。,初 态，21xRjx移动j，i=j，xRj 一趟

10、排序结束,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，25,一趟快速排序算法的实现,int Patition(Sqlist/*返回枢轴位置*/,第 19 页,第 20 页,递归形式的快速排序算法,void QSort(Sqlist,时间效率：最坏情况下O(nlog2n)空间效率：最坏情况下栈的深度为n稳 定 性：不稳定,第 21 页,不断在待排序序列（无序区）中按记录关键字递增（或递减）次序选

11、择记录，放入有序区中，因此选择排序的过程是逐渐扩大有序区，直到整个记录区为有序区为止。,3、选择排序,选择排序的基本思想是：,选择排序有多种具体实现算法：（1）简单选择排序（2）堆排序,第 22 页,基本思想：每一趟在后面n-i个待排记录中选取关键字最小的记录作为有序序列中的第i 个记录。,思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。首先，在n个记录中选择最小者放到R1位置；然后，从剩余的n-1个记录中选择最小者放到R2位置；如此进行下去，直到全部有序为止。优点：实现简单缺点：每趟只能确定一个元素，表长为n时需要n-1趟前提：顺序存储结构,（1）简单选择排序,

12、第 23 页,例：关键字序列T=（21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。,原始序列：21，25，49，25*，16，08,第1趟第2趟第3趟第4趟第5趟,08，25，49，25*，16，2108，16,49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49,时间效率：O(n2)虽移动次数较少，但比较次数仍多。空间效率：O(1)仅用到1个辅助变量算法的稳定性：不稳定因为排序时，25*到了25的前面。,最小值 08 与r1交换位置,第 24 页,简单选择排序的算法,void Selec

13、tSort(Sqlist,在简单选择排序中,第一趟在n个关键字中选出最小值，需经过n1次比较，但没有把比较结果保留下来，以致第二趟需要重新在n1个关键字中进行比较，选出次小值，如此反复多次，增加了时间开销。,第 25 页,基本思想：将存放在向量中的数据看作是一棵完全二叉树，向量的下标即为完全二叉树的结点序号。它利用完全二叉树上下层结点之间的特殊关系，不断调整结点的位置，最终完成排序。,（2）堆排序,满/完全二叉树结点序号间的关系：下标值为i的双亲，其左孩子的下标值必为2i，其右孩子的下标值必为2i1。,96,83,27,38,11,09,第 26 页,设有序列k1,k2,kn若满足：或则称该序

14、列构成的完全二叉树是一个“堆”。其中二叉树的根结点（堆顶），是序列中的最大（或最小）元素。,堆排序的关键,如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？,什么是堆？,第 27 页,堆的调整-筛选,为构成以Hk为根结点的堆，将Hk的值与其左右子树根结点值进行比较，若不满足堆的条件，则将Hk与其左右子树根结点中大者进行交换，继续进行比较，直到所有子树均满足堆为止。,堆调整算法实现,void HeapAdjust(Sqlist,第 28 页,堆的建立,对于一个无序序列H1:n构成的完全二叉树，只要从它最后一个非叶子结点（第n/2个元素）开始直到根结点（第1个

15、元素）为止，逐步进行上述调整即可将此完全二叉树构成堆。,第 29 页,for(j=n/2;j=1;j-)HeapAdjust(H,j,n);,堆建立算法实现,第 30 页,第 31 页,堆排序算法实现,将堆顶元素与堆中最后一个元素交换，然后将最后一个元素从堆中删除，将余下的元素构成的完全二叉树重新调整为堆，反复进行直到堆空为止。,void HeapSort(Sqlist/*因根结点的左右子树均为堆，因此只需对根结点进行自上而下的调整即可。*/,第 32 页,第 33 页,例1：关键字序列T=（21，25，49，25*，16，08），请画出堆排序的具体实现过程。,输出49,建堆,输出25,建堆,

16、输出25*,建堆,输出21,输出16,生成完全二叉树,建堆,建堆,输出8,(8,16,21,25*,25 49),第 34 页,堆排序算法分析,时间效率：建堆过程中，最坏情况下比较次数约为2log2n+2.4n，移动次数约为log2n+1.7n；堆排序过程中，最坏情况下比较次数约为2nlog2n-2.9n，移动次数约为nlog2n+1.1n，因此最坏情况下的时间复杂度为O(nlog2n)空间效率：O(1)只需一个辅助空间用于交换记录算法的稳定性：不稳定,第 35 页,4、排序方法比较,若待排序的记录数n50，可采用插入排序或简单选择排序。若n较大，应采用快速排序或堆排序。若待排序记录按关键字基本有序，则宜采用插入排序或冒泡排序。当待排序记录经常要进行插入、删除时，为避免大量记录移动，宜采用动态存储结构，即二叉排序树形式。,思考题,1、从未排序序列中挑选元素，并将其依次放入到已排序序列中(初始时为空)的一端的方法是什么？2、在待排序的元素基本有序的前提下，效率最高的排序方法是什么?3、从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置方法是什么？4、设有1000个元素，希望采用最快的速度挑选出其中前10个最大的元素，最好的方法是什么?,第 36 页,