第9章内部排序下载_PPT模板_39

nullnull第9章内部排序基本概念插入排序快速排序选择排序归并排序基数排序null9.1 基本概念设含有n个记录的文件{R1,R2,...,Rn}，其相应的关键字为{K1,K2,...,Kn}，将记录按关键字值非递减(或非递增)顺序排列的过程，称为排序。如以学号为关键字对下面的学生成绩表进行排序。注：表中的一行在数据结构里我们把它叫做数据元素，在非面向对象的软件分析或设计中称为一个记录，在面向对象的软件分析和设计中称为一个对象。 null关键码：要排序的对象集合可能有多个域（数据项），关键码是当前排序时进行比较以确定各个对象位置的域。主关键字：在对象集合中，不同的对象其关键字值一定不相同的关键字称为主关键码；次关键码：不同的对象其关键码值有可能相同的关键码。主码次关键码null对所有的Ki=Kj (i≠j),若排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称该排序方法是稳定的，反之，称为不稳定的。稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置（即领先关系）是否变化。主要是针对以次关键码为关键字进行排序的情况。 null 内部排序：待排序文件的全部记录存放在内存进行的排序，称为内部排序。外部排序：排序过程中需要进行内外存数据交换的排序，称为外部排序。排序算法好坏的性能描述： 1）时间复杂度 2）空间复杂度 3）稳定性null内排序分类按排序过程依据的原则分为：插入排序交换排序选择排序归并排序基数排序按排序过程所需的工作量分：简单排序 O(n2) 先进排序 O(nlogn) 基数排序 O(d．n)null 一. 直接插入排序 (最简单的排序方法） ⒈ 基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置(有序子文件记录数增1) 例如：已有待排序文件为：64,5,7,89,6,24,6# 首先将文件的第一个记录，视为有序文件，然后从第二个记录开始，直到最后一个记录，依次将他们插入到有序文件的合适位置。null直接插入排序算法 void insertsort(datatype a[],int n) { int i,j; datatype temp; for(i=0;i-1&&temp.key-1&&temp.key<=s[j].key) {s[j+span]=a[j]; j=j-span; } s[j+span]=temp;}}}}null4．希尔排序的特点 ⑴ 子文件（子序列）的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子文件。 ⑵ 增量序列应是递减，且最后一个必须为1。 ⑶ 希尔排序法是不稳定的。希儿排序算法P281null二、选择排序选择排序的基本思想：不断从待排序的对象集合中选择关键码最小的对象放到已经排序对象的集合后面，直到集合中所有对象都选取完为止。 1）直接选择排序算法思想：从待排序的对象集合中选取关键码最小的对象并将它与原始对象集合中的第一个对象交换位置；然后从不包括第一个位置上对象集合中选取关键码最小的对象并将它与原始对象集合中的第二个对象交换位置，如此重复，直到对象集合中只剩下一个对象为止。null void SelectSort(DataType a[],int n) { int i ,j,small; DataType temp; for(i=0;inext; while( ) { ( );q=p->next; while( ) ( if(q->datadata) ( ) ;q=q->next;} if( ) {temp=p->data;p->data=minp->data;minp->data=temp;} ( ) } }pminp=pqminp=qminp!=pp=p->nextnull四、归并排序归并排序是将原始序列划分为两个子序列，然后分别对每个子序列递归排序，最后再将排好序的子序列合并，侧重于归并过程。将两个有序的子序列合成一个有序序列称为归并。nullnullnull void merge(Datatype a[],Datatype swap[],int k) {//对有序表a进行一次二路归并排序，每个子表的长度为k，归并//好后放在swap数组中。 int m=0,u1,l2,i,j,u2; int l1=0; //给出第一个有序子表下界 while(l1+k

                    本文档为【第9章 内部排序】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

第9章 内部排序

你可能还喜欢

第9章内部排序