《查找和排序》PPT课件.ppt

第4章 查 找 和 排 序,4.1 线性表查找 4.1.1 顺序查找4.1.2 折半查找4.1.3 分块查找4.2 二叉排序树的查找 4.3 哈希查找 4.3.1 哈希表的建立4.3.2 处理冲突的方法4.3.3 哈希查找4.4 排序 4.4.1 直接插入排序4.4.2 简单选择排序4.4.3 冒泡排序4.4.4 快速排序4.4.5 归并排序习题,4.1 线性表查找,查找(Searching)，也称检索，亦即查表，就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作，如查寻电话号码、查字典、查图书目录卡片等。为确切定义查找，先引入几个概念。查找表：由同一类型的数据元素(或记录)构成的集合。,关键字(key)：数据元素中可以惟一标识一个数据元素的数据项。如学生的学号，居民身份证号等。查找就是根据给定的关键字值，在查找表中确定一个关键字等于给定值的记录或数据元素。若存在这样的数据元素，则称查找是成功的，否则称查找不成功。决定查找操作的是关键字，因此这里讨论时，只关注记录中的关键字域，而一概忽略记录中其它诸域的信息。,查找是许多重要的计算机程序中最耗费时间的部分，查找算法的优劣密切关系着查找操作的速度，因此对查找算法应认真研究。关于查找，目前主要研究两方面的问题：(1)查找的方法。因为查找某个数据元素依赖于该数据元素在一组数据中所处的位置，即该组数据的组织方式，故应按照数据元素的组织方式决定采用的查找方法；反过来，为了提高查找方法的效率，要求数据元素采用某些特殊的组织方式。,(2)查找算法的评价。衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。就查找算法而言，通常只需要很少的辅助空间，因此更关心的是它的时间复杂度。在查找算法中，基本运算是给定值与关键字的比较，所以算法的主要时间是花费在“比较”上。下面给出一个称为平均查找长度的概念，作为评价查找算法好坏的依据。对于含有n个数据元素的查找表，查找成功时的平均查找长度为,ASL=,其中，Pi为查找第i个数据元素的概率；Ci为查到第i个数据元素时，需与关键字进行比较的次数。,4.1.1 顺序查找 顺序查找是最简单、常用的查找技术。其基本思想是：从表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值(常用1表示)。,顺序查找方法既适用于以顺序存储结构组织的查找表的查找，也适用于以链式存储结构组织的查找表的查找。在本章的有关查找和排序算法中，假设线性表均采用顺序存储结构，其类型说明为：,#define MAXLEN n/*n为查找表中元素个数的最大可能值*/struct elementint key;/*设关键字的类型为整型*/int otherterm;/*为说明起见，除关键字外只有一个整型数据项*/;typedef struct element DATATYPE;DATATYPE tableMAXLEN;,算法4-1 顺序查找算法。int seqsearch1(DATATYPE A,int k)int i;i=0;while(Ai.key!=k)if(Ai.key=k),return i;/*查找成功，返回被查元素在表中的相对位置*/elsereturn 1;/*查找失败，返回1*/若对此算法进行一些改进，在表尾增加一个关键字为指定值K的记录，可避免每“比较”一次，就要判别查找是否结束。当n很大时，大约可节省一半的时间。,算法4-2 改进的顺序查找算法。#define MAXLEN n+1int seqsearch2(DATATYPE A,int k)int i;i=0;AMAXLEN1.key=k;,while(Ai.key!=k)i+;if(iMAXLEN1)return i;/*查找成功，返回被查元素在表中的相对位置*/elsereturn 1;/*查找失败，返回1*/,将AMAXLEN1称作监视哨，这个增加的记录起到了边界标识的作用。下面对改进后的算法进行一下性能分析，计算它的平均查找长度。对含有n个记录的表，查找成功时的平均查找长度为,ASL=,从顺序查找的过程看，Ci取决于所查元素在表中的位置，对于第一个记录只要比较一次，对第n个记录，需要比较n次，查找记录Ai时，比较i次。设每个记录的查找概率相等，则Pi=1/n。故此算法在等概率情况下查找成功的平均查找长度为,ASL=,4.1.2 折半查找 如果查找表中的记录按关键字有序，则可以采用一种高效率的查找方法折半查找，也称二分查找。折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到找到或者查找范围为空而查不到为止。,折半查找的过程实际上是先确定待查元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。算法中需要用到三个变量,low表示区域下界,high表示上界,中间位置mid=(low+high)DIV 2。由于折半查找要求数据元素的组织方式应具有随机存取的特性，所以它只适用于以顺序存储结构组织的有序表。,算法4-3 折半查找算法。#define MAXLEN nint binsearch(DATATYPE A,int k)int low,mid,high;low=0;high=MAXLEN1;while(low=high)mid=(low+high)/2;,if(k=Amid.key)return mid;/*查找成功，返回被查元素在表中的相对位置*/else if(kAmid.key)low=mid+1;elsehigh=mid1;return 1;/*查找失败，返回1*/,折半查找成功的平均查找长度为 ASLbslb(n+1)1(求解过程从略)折半查找的优点是比较次数少，查找速度快，但只能对有序表进行查找。它适用于一经建立就很少变动而又经常需进行查找的有序表。,例4-1 一有序表的关键字序列为(5，12，18，20，35，50，64，72，80，88，95)，表长为11，采用折半查找求其在等概率情况下查找成功时的平均查找长度。解：按照折半查找算法，对序列中11个元素的查找过程如下：(1)mid=(1+11)DIV 2 查到第6个元素50，比较1次；(2)mid=(1+5)DIV 2 查到第3个元素18，比较2次；,或mid=(7+11)DIV 2 查到第9个元素80，比较2次；(3)依次类推，查到第1、4、7和第10个元素需比较3次；查到第2、5、8和第11个元素需比较4次。,这个查找过程可用图4-1(a)的二叉树表示。若树中每个结点表示一个记录，结点中的值为该记录在表中的位置，通常这个描述查找过程的二叉树为判定树，如图4-1(b)所示。从判定树上看，查找20的过程恰好是走了一条从根到结点4的路径，比较次数为该路径上的结点数，或结点4在判定树上的层次数。因此，折半查找在查找成功时进行比较的次数最多不超过树的深度。,图4-1 描述折半查找过程的二叉树及判定树(a)描述折半查找的二叉树；(b)描述折半查找的判定树,从判定树上可知 ASLsucc=(1+2+2+3+3+3+3+4+4+4+4)=3 从该例可看出，折半查找成功的平均查找长度与序列中的具体元素无关，只取决于序列中元素的数目。,4.1.3 分块查找 分块查找又称索引顺序查找，这是顺序查找的另一种改进方法。前面介绍的顺序查找速度慢；而折半查找虽速度快，但为换取快速查找所付出的代价是要将线性表按关键字排序，而且表必须采取顺序存储。在顺序结构里执行插入、删除操作都很困难。如果要处理的线性表既希望较快的检索又需要存储结构灵活，可以采用分块查找。分块查找是顺序查找和折半查找的折衷方案，特别适用于索引存储结构。,分块查找的特点是按照表内记录的某种属性把表分成n(n1)个块(子表)，每一块中记录的存放是任意的，但是块与块之间是有序的，即所谓“分块有序”。假如按关键字递增顺序进行分块排列，就是指第j块的所有记录的关键字均大于第j1块的所有记录的关键字(j=2,3,n)，并建立一个索引表。把每块中的最大关键字值及每块的第一个记录在表中的位置存放在索引项中。整个查找过程分两步进行：(1)确定待查记录所在的块。(2)在块内查找。,例4-2 设给定值K=32，在图4-2所示的索引顺序表中查找关键字等于K的记录。,图4-2 表及其索引表,解：在图4-2的表中有18个记录，分成了三个子表(R1，R2，R6)，(R7，R8，R12)，(R13，R14，R18)。先将K依次和索引表中各最大关键字进行比较，因为25K45，则关键字为32的记录若存在，必定在第二个子表(块)中。然后从第二块的第一个记录，即表中的第7个记录起进行顺序查找，直到r12.key=K为止。假如此块中没有关键字等于K的记录，则查找不成功。由于索引项的组成按关键字有序，则确定块的查找可以用顺序查找，亦可以用折半查找。而块中记录是任意排列的，则在块中只能是顺序查找。,分块查找的优点是在表中插入或删除一个元素时，只要找到该元素所属的块，然后在块内进行插入和删除。因为块内元素的存放是任意的，所以插入和删除时不需移动大量元素。所付出的代价是增加了存放索引表的辅助空间。分块查找也是常用的一种查找方法。,4.2 二叉排序树的查找,前一节我们介绍了三种基本的查找方法：顺序查找、折半查找和分块查找。其中折半查找的效率最高，但折半查找要求查找表中的数据元素按关键字有序，且不能用链表作存储结构。当对查找表中的数据元素进行插入和删除操作时，为了保持查找表的有序性，势必要移动很多记录，造成新的时间开销。当插入和删除频繁进行时，这种额外开销就会抵消折半查找的优点。,若我们对查找表只作查找运算，则称该表为静态查找表。若对查找表既允许进行查找运算，又允许进行插入和删除运算，则称该表为动态查找表。前一节介绍的查找方法主要适用于静态查找表的查找，所以可称其为静态查找算法。对于动态查找表，为了能在其上方便地进行插入和删除操作，应寻求相应的动态查找算法。动态查找算法又常称为符号表算法，因为编译程序、汇编程序和其它系统子程序都广泛使用这种算法去监视和记录用户所定义的符号。为满足这种要求，需采用树表，包括二叉排序树、二叉平衡树、B树、B+树、键树，这里我们只介绍二叉排序树的查找。,1二叉排序树的查找 二叉排序树(binary sort tree)或者是一棵空树；或者是具有下列性质的二叉树。(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2)若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；(3)它的左、右子树也分别为二叉排序树。图4-3所示为两棵二叉排序树。,对二叉排序树进行中序遍历，可得到一个有序序列。故用这种方式存储表，可以把顺序表中折半查找速度快的优点与链式结构中插入、删除方便的优点结合起来，使查找表既具有顺序表那样高的检索效率，又具有链表那样插入、删除运算的灵活性。,图4-3 二叉排序树示例,二叉排序树查找的思想是：(1)当二叉排序树不空时，首先将给定值K与根结点的关键字进行比较，若相等则查找成功；(2)若给定值K小于根结点的值，则继续在根的左子树中查找；若给定值K大于根结点的值，则继续在根的右子树中查找。显然这是一个递归查找过程。其查找算法见算法4-4。,算法4-4 二叉排序树的查找。struct treenodeint key;int otherterm;struct treenode*lchild,*rchild;typedef struct treenode TREENODE;TREENODE*bstsearch(TREENODE*root,int k),if(root=NULL)return NULL;else if(root-key=k)return root;/*查找成功*/else if(root-keyk)return bstsearch(root-lchild,k);/*查找左子树*/elsereturn bstsearch(root-rchild,k);/*查找右子树*/,由于此递归算法的递归调用属于末尾递归(即递归调用语句是函数中最后一条可执行语句)的调用，每次递归调用后返回给函数的各值也是重复的，同时每次递归调用后返回的退栈信息也是没有用的，所以为了减少花费在进出栈上无效的时间和空间，可编写出相应的非递归算法，见算法4-5。,算法4-5 二叉排序树的查找。struct treenodeint key;int otherterm;struct treenode*lchild,*rchild;typedef struct treenode TREENODE;TREENODE*bstsearch(TREENODE*root,int k)TREENODE*p;p=root;,while(p!=NULL)if(p-key=k)return p;/*查找成功，返回非空指针*/else if(p-keyk)p=p-lchild;elsep=p-rchild;return p;/*查找失败，返回空指针*/,2二叉排序树的生成 对一组数据序列K1，K2，Kn，先设一棵空二叉树，然后依次将序列中的元素生成结点后逐个插入到已生成的二叉排序树中。步骤如下：(1)K1是二叉排序树的根；(2)若K2K1，则K2所在的结点应插入到K1的左子树上；否则插入到K1的右子树上；,(3)读Ki，若Ki K1(根)，则插入到根的左子树上，否则Ki插入到根的右子树上；(4)若in，则继续执行步骤(3)，否则结束。设有一组关键字序列为(48，24，53，20，35，90)，这一组数据按二叉排序树组织时，其二叉排序树的构造过程如图4-4所示。从图4-4中可看出，二叉排序树的生成过程就是在二叉排序树上插入结点的过程。设有n个数据元素序列存放在一维数组An中，二叉排序树采用二叉链表存储结构，根结点指针为bst，生成二叉排序树的算法如算法4-6所示。,图4-4 二叉排序树的构造过程,算法4-6 二叉排序树的生成算法。#define N n/*n为二叉排序树中结点个数的最大可能值*/struct tnode int data;struct tnode*lchild,*rchild;typedef struct tnode TNODE;int An;TNODE*create_binary_sort_tree(),int i;TNODE*head,*s,*p,*q;head=NULL;for(i=0;idata=Ai;s-lchild=NULL;s-rchild=NULL;if(head=NULL),head=s;elsep=head;while(p!=NULL)q=p;if(s-datadata)p=p-lchild;elsep=p-rchild;,if(s-datadata)q-lchild=s;elseq-rchild=s;return head;,从二叉排序树的建立过程可以看出，一个无序序列通过构造一棵二叉排序树而变成一从二叉排序树的建立过程可以看出，一个无序序列通过构造一棵二叉排序树而变成一个有序序列(中序遍历二叉排序树可得一个关键字的有序序列)，构造二叉树的过程即为对无序序列进行排序的过程。而且从插入过程还可以看到，每次插入的新结点都是二叉排序树上新的叶子结点，则在进行插入操作时，不必移动其它结点，仅需改动指针。,3二叉排序树的查找分析 例4-3 对图4-4(g)所示的二叉排序树进行查找，如要查找的关键字K=35，则K先与根结点比较，因3548，查找左子树；因3524，故在根的左子树的右子树上查找；因以结点24为根的右子树的根正好为35，故查找成功。,由上例可以看出，在二叉排序树中查找成功时走了一条从根结点到所查结点的路径。因此二叉排序树的平均查找长度取决于二叉排序树的深度。这与折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是惟一的，而含有n个结点的二叉排序树却不惟一。所以，二叉排序树查找成功的平均查找长度取决于二叉排序树的形状，而二叉排序树的形状既与结点数目有关，更取决于建立二叉排序树时结点的插入顺序。,例4-4 已知长度为6的线性表是(45，24，53，13，30，85)，若按表中元素的顺序依次插入，得到二叉排序树如图4-5(a)所示；若依次序13,24,30,45，53，85插入，得到二叉排序树为图4-5(b)所示，试分别求出在等概率情况下二叉排序树查找成功的平均查找长度。解：因是6个记录等概率查找，所以Pi=。则(a)树的平均查找长度为 ASL(a)=1+2+2+3+3+3=则(b)树的平均查找长度为 ASL(b)=1+2+3+4+5+6=,二叉排序树查找的平均比较次数取决于二叉树的深度。在最好情况下，所生成的二叉排序树中，任一结点的左、右子树的深度相差都不超过1，即二叉排序树是一棵平衡二叉树时，二叉排序树查找的平均比较次数与折半查找相同，其查找效率最高。而在最坏情况下，即当二叉排序树蜕化为单支树时，其平均比较次数就和顺序查找相同了。,图4-5 例4-4构造的二叉排序树(a)二叉排序树；(b)单支树,4.3 哈 希 查 找,无论是顺序查找、折半查找、分块查找，还是二叉排序树查找，都需进行一系列和关键字的比较才能确定被查元素在查找表中的位置，查找的效率依赖于查找过程中所进行的比较次数。而哈希查找的思想与前面四种方法完全不同，哈希查找方法是利用关键字进行某种运算后直接确定元素的存储位置，所以哈希查找方法是用关键字进行计算元素存储位置的查找方法。,在讨论哈希查找之前，先讨论适用于哈希查找的查找表的组织方式哈希表。在一块连续的内存空间采用哈希法建立起来的符号表就称为哈希表。,4.3.1 哈希表的建立 哈希表的建立：以线性表中的每个元素的关键字K为自变量，通过一种函数H(K)计算出函数值，然后将该元素存入H(K)所指定的相应的存储单元。查找时，只要根据要查找的关键字用同样的函数计算出地址H(K)，然后直接到相应的单元中去取所要找的元素。称函数H(K)为哈希(Hash)函数，按这个思想建立的表为哈希表。,细心的读者可能会发现这样一个问题：对于某个哈希函数H(K)和两个关键字K1和K2，如果K1K2，而H(K1)=H(K2)，这种现象称为冲突。在构造哈希函数时应避免冲突。但没有冲突的函数是很不好找的，因为通常哈希函数是一个压缩映象，即关键字集合大，地址集合小。一般只能尽可能地避免冲突的发生。例如，一个符号表其标识符至多由5个英文字母组成，则不同的标识符可能有 265+264+263+262+26=12 356 630(个),如果一个标识符对应一个存储地址，就不会发生冲突了，但这是不可能也没有必要的。因为存储空间难以满足，而且任何一个源程序也不会有这么多的标识符。由于哈希法用哈希函数转换记录关键字得到存储地址，把各记录散列到相应的存储单元里去，所以也称之为散列地址法或关键字转换法。,对于哈希法，主要考虑两个问题：(1)构造一个合适的哈希函数。分析数据元素的关键字集合之特点，找出适当的函数H(K)，使计算出的存储地址尽可能均匀地分布在哈希表中；同时也希望函数H(K)尽量简单，便于快速计算；哈希函数H(K)一般应是一个压缩映象函数，它应具有较大的压缩性，以节省存储空间。,常用的构造哈希函数的方法有：数字分析法；平方取中法；折叠法；除留余数法；直接定址法；随机数法。,(2)如何解决冲突。哈希函数应具有较好的散列性，冲突是不可避免的，但应尽量减少。若已知哈希函数及冲突处理方法，哈希表的建立步骤如下：Step1：取出一个数据元素的关键字Key，计算其在哈希表中的存储地址D=H(Key)。若存储地址为D的存储空间还没有被占用，则将该数据元素存入；否则发生冲突，执行Step2。Step2：根据规定的冲突处理方法，计算关键字为Key的数据元素的下一个存储地址。,若该存储地址的存储空间没有被占用，则存入；否则继续执行Step2，直到找出一个存储空间没有被占用的存储地址为止。Step3：重复Step1和Step2，直到所有的数据元素都被存储为止。,4.3.2 处理冲突的方法 哈希法中不可避免地会出现冲突现象，所以关键的问题是如何解决冲突。处理冲突的方法多种多样，常用的方法有：开放定址法、链地址法、再哈希法和公共溢出区法。这里只介绍前两种方法。,假设哈希表的地址集为0n1，冲突是指H(K)的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列Hi(i=1，2，k)，Hi0，n1。即在处理冲突时，若得到的另一个哈希地址H1仍然发生冲突，则再求下一个地址H2，若H2仍冲突，再求H3，依次类推，直至Hk不发生冲突为止，则Hk为记录在表中的地址。,1开放定址法 Hi=(H(key)+di)MOD m i=1，2，k(km1)这里，m为哈希表表长；di为增量序列。按照增量序列的不同取法，开放定址法又分为线性探测再散列和二次探测再散列。(1)线性探测再散列 di=1，2，3，m1(2)二次探测再散列 di=12，12，22，22，32，K2，K2(Km/2),例如，在长度为10的哈希表中已填有关键字21，52，73的记录，哈希函数为H(key)=key MOD 10，现有第四个记录，其关键字为82，由哈希函数得到的哈希地址为2，产生冲突。若用线性探测再散列处理冲突，得到的下一个地址为3，仍冲突；再求下一个地址为4，此地址为空，将82存入。处理冲突过程结束，如图4-6(b)所示。若用二次探测再散列，则应该填入序号为6的位置。如图4-6(c)所示。,图4-6 用开放定址法处理冲突时，关键字82插入前后的哈希表(a)插入前；(b)线性探测再散列；(c)二次探测再散列,2链地址法 将所有具有相同哈希地址的记录存储在同一个单链表中。即H(K1)=H(K2)=H(K3)，称K1，K2和K3为同义词，链地址法就是将所有关键字为同义词的记录链在一起。这一点与邻接表的思想非常类似。例如将上例中处理冲突的方法改为链地址法，插入82和72后的情况如图4-7所示。,图4-7 用链地址法处理冲突产生的哈希表,4.3.3 哈希查找 在哈希表上查找的过程和构造哈希表的过程基本一致。给定K值，根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字。若和给定值相等，则查找成功；否则根据造表时设定的处理冲突的方法找“下一地址”，直至哈希表中某个位置为“空”或者表中所填记录的关键字等于给定值时为止。,从哈希表的查找过程可知，尽管可直接由关键字K计算出存储地址H(K)，但由于“冲突”的产生，使得在哈希表的查找过程中仍然需要用给定值K与元素的关键字进行比较，所以平均查找长度仍然可以作为评价哈希查找效率的标准。值得注意的是，在采用开放定址法解决冲突所产生的哈希表中，若要删除表中的一个记录，不能简单地直接删除，因为这样将截断其它具有相同哈希地址的元素的查找地址，所以应设定一个特殊的标志以表明该元素已被删除。,例4-5 设哈希函数H(K)=k MOD 7，哈希表的地址空间为06，对关键字序列(19，14，23，2，68，16，4)，按下述几种解决冲突的方法分别构造哈希表，线性探测再散列；二次探测再散列；链地址法；并分别计算哈希查找成功时在等概率情况下的平均查找长度。,解：(1)按照线性探测再散列法处理冲突构造哈希表。19 MOD 7=5 存入地址空间514 MOD 7=0 存入地址空间023 MOD 7=2 存入地址空间22 MOD 7=2 发生冲突下一个存储地址是(2+1)MOD 7=3 存入地址空间368 MOD 7=5 发生冲突下一个存储地址是(5+1)MOD 7=6 存入地址空间616 MOD 7=2 发生冲突,下一个存储地址是(2+1)MOD 7=3 发生冲突下一个存储地址是(2+2)MOD 7=4 存入地址空间44 MOD 7=4 发生冲突下一个存储地址是(4+1)MOD 7=5 发生冲突下一个存储地址是(4+2)MOD 7=6 发生冲突下一个存储地址是(4+3)MOD 7=0 发生冲突下一个存储地址是(4+4)MOD 7=1 存入地址空间1所得哈希表如图4-8所示。,根据哈希表的构造过程可知：查找19、14、23仅需比较1次；查找2、68因有一次冲突，需比较2次；查找16因有两次冲突，需比较3次；查找4因有四次冲突，需比较5次。故 ASL成功=,图4-8 用线性探测再散列法处理冲突产生的哈希表,图4-9 用二次探测再散列法处理冲突产生的哈希表,(2)按照二次探测再散列法处理冲突产生的哈希表如图4-9所示。ASL成功=(3)按照链地址法处理冲突产生的哈希表如图4-10所示。ASL成功=,图4-10 用链地址法处理冲突产生的哈希表,4.4 排 序,排序是计算机程序设计中的一种重要运算，它的功能是将一个数据元素的无序序列调整为一个有序序列。经排序的数据若按由大到小的顺序排列，称为下降序；反之，若按由小到大的顺序排列，称为上升序。,对数据进行查找或其它操作时，有序数据和无序数据的执行速度差别很大。如对有序表可采用折半查找等，而对无序表只能用顺序查找。排序在实际中应用很广，据统计，计算机处理的25%的机时是用于排序的。因此，研究高效率的排序方法是数据结构的一个重要内容。然而，目的不是参与具体的排序工作，而是研究分析排序算法中所运用的大量基本的和重要的排序技术。,排序的分类：根据排序中所涉及的存储器，可将排序分为内部排序和外部排序两大类。排序过程中，所有记录都放在内存中处理的称为内部排序；当待排序的记录很多，排序时不仅要使用内存，而且还要使用外部存储器的排序方法称为外部排序。本节只讨论内部排序。如果待排序的记录中，存在多个关键字相同的记录，经排序后这些记录的相对次序仍然保持不变，则称相应的排序方法是稳定的，否则称为不稳定的。,不同的排序方法有其不同的特点，排序方法的选择只有根据所排序记录的特点，才能找出合适的排序方法。评价排序算法优劣的标准主要是时间复杂度，对内部排序而言，时间的主要开销花在记录的比较和移动上，所以时间复杂度主要通过记录的比较次数和移动次数来反映。为简单起见，采用顺序存储结构存放所排序的记录序列。其C语言描述如下：,#define N nstruct record int key;int otheritem;typedef struct record RECORD;RECORD fileN+1;其中n为待排序的记录数目。,4.4.1 直接插入排序 插入排序的基本思想是把记录逐一按其关键字的大小插入到已经排好次序的记录序列中的适当位置，直到全部插入完为止。这很象打扑克牌时，一边抓牌，一边理牌的过程，每抓一张牌就把它插到适当的位置上去。,设有n个记录(R1，R2，Rn)，已划分为已排序部分和未排序部分，即插入Ri时，(R1，R2，Ri1)是已排好序的部分，(Ri，Ri+1，Rn)属于未排序部分。用Ri依次与Ri1，Ri2，R1进行比较，找出Ri在有序子文件中的插入位置，将Ri插入，原位置上的记录至Ri1均顺序后移一位。,例4-6 设待排序记录的关键字序列为(20，15，8，23，55，25)，写出直接插入排序每一趟执行后的序列状态。解：直接插入排序过程如图4-11所示。,图4-11 直接插入排序示例,算法4-7 直接插入排序算法。void insertsort(RECORD R,int n)/*注意设待排记录放在R1到Rn中*/int i,j;for(i=2;i=n;i+)R0=Ri;j=i1;/*j总是指向有序序列的最后一个记录*/while(R0.keyRj.key),Rj+1=Rj;/*后移一位，设结构体变量可以整体赋值*/j;Rj+1=R0;/*插入R0元素到有序序列中*/直接插入排序是稳定的，其时间复杂度为O(n2)。,4.4.2 简单选择排序 简单选择排序的方法是在所有的记录中选出关键字最小的记录，把它与第一个记录交换存储位置，然后再在余下的记录中选出次小的关键字对应的记录，把它与第二个记录交换，依此类推，直至排序完成。例4-7 待排序的记录关键字序列为(20，15，8，40，55，25)，写出简单选择排序每一趟执行后的序列状态。解：简单选择排序过程如图4-12所示。,图4-12 简单选择排序示例,算法4-8 简单选择排序。void selectsort(RECORD R,int n)/*注意待排记录放在R1到Rn中*/int i,j,k;RECORD temp;for(i=1;in;i+)k=i;for(j=i+1;j=n;j+)if(Rj.keyRk.key),k=j;if(i!=k)temp=Rk;/*交换元素，设结构体变量可以整体赋值*/Rk=Ri;Ri=temp;简单选择排序是不稳定的，其时间复杂度是O(n2)。,4.4.3 冒泡排序 冒泡排序的基本思想为：从R1开始，两两比较相邻记录的关键字，即比较Ri和Ri+1(i=1，2，n1)的关键字大小，若逆序(如KiKi+1)，则交换Ri和Ri+1的位置，如此经过一趟排序，关键字最大的记录被安置在最后一个位置(Rn)上。然后再对前n1个记录进行同样的操作，则具有次大关键字的记录被安置在第n1个位置(Rn1)上。如此反复，进行n1趟冒泡排序后所有待排序的n个记录已经按关键字由小到大有序。,若把各记录看作按纵向排列，那么在这个排序过程中，关键字小的好比水中的气泡往上漂浮(冒)，关键字大的好比水中的石块沉入水底，故形象地取名为冒泡排序。例4-8 待排序的记录关键字序列为(20，15，8，40，55，25)，写出冒泡排序每一趟执行后的序列状态。解：冒泡排序过程如图4-13所示，其中，横线以下为已排好序的记录。,图4-13 冒泡排序示例,算法4-9 冒泡排序算法。void bubblesort(RECORD R,int n)/*注意待排记录放在R1到Rn中*/int i,j;RECORD temp;for(i=1;in;i+)for(j=1;j=ni;j+),if(Rj.keyRj+1.key)temp=Rj;/*交换元素，设结构体变量可以整体赋值*/Rj=Rj+1;Rj+1=temp;,按照算法4-9给出的冒泡排序算法，对具有n个记录的待排序序列要执行n1趟冒泡排序。但从例4-8中我们可以发现，在进行第三趟冒泡排序过程时，已没有记录进行过交换，表明此时记录序列已经“正序”(有序)，后面的3趟冒泡“空跑”没有发生交换。因此应该对算法4-9加以改进：使之能“记住”每趟冒泡排序过程中是否发生了“交换”，若某一趟冒泡未发生“交换”，表示此时记录序列已经有序，应结束排序过程。,算法4-10 改进后的冒泡排序算法。void bubblesort_m(RECORD R,int n)int i,j,flag;RECORD temp;i=1;doflag=0;/*在进行每一趟冒泡之前置flag为0，表示无交换*/for(j=1;j=ni;j+),if(Rj.keyRj+1.key)temp=Rj;Rj=Rj+1;Rj+1=temp;flag=1;i+;while(in),分析冒泡排序的效率，很容易看出，若初始序列为“正序”，则只需一趟排序。反之，若初始序列为“逆序”，则需要进行n1趟排序。冒泡排序方法是稳定的，其在最坏情况下的时间复杂度为O(n2)。但由于冒泡排序能“判别”记录的状态，所以当待排序序列是基本有序的序列时，采用冒泡排序方法的效率是很高的。,4.4.4 快速排序 快速排序也称作划分交换排序，和冒泡排序同属于交换排序类型。它是目前内部排序中速度最快的排序方法，故称为快速排序，其平均时间复杂度为O(nlogn)，它偏爱无次序的记录序列。它的基本思想是：在待排序的n个记录中任取一个记录R(通常为第一个)，以该记录的关键字K为准，将所有剩下的n1个记录划分为两个子序列，第一个子序列中所有记录的关键字均小于或等于K；第二个子序列中所有记录的关键字均大于K。,然后将K所对应的记录R放在第一个子序列之后及第二个子序列之前，使得待排序记录序列成为R，完成快速排序的第一趟排序。然后分别对子序列1和子序列2重复上述划分，直到每个子序列中只有一个记录时为止。那么如何实现这个划分呢？需设两个指针i、j，初始时分别指向第一个和最后一个记录，即令i=1，j=n，并将第一个记录的关键字暂存于k(先用第一个记录的关键字k进行划分，称这个记录为控制记录或支点)。,当ij时，重复以下操作：(1)若kRj.key，则j=j1，即再比较j的前一个记录关键字；否则Rj与Ri交换。(2)比较k与i指向的记录的关键字，若kRi.key，则与i的后一个记录关键字比较(i=i+1)；否则将Ri与Rj交换。(3)重复上述过程，直至i=j时，划分结束，i所指示的位置就是控制记录应有的位置。下面看一个快速排序的例子。,例4-9 一组待排序的记录关键字序列为(46，55，13，42，94，05，17，70)，试给出第一趟快速排序过程中记录的交换示意图。解：一趟快速排序过程如图4-14所示。上例给出了一趟快速排序的过程，整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排序。结合上述例题，给出快速排序的全过程，如图4-15所示。,图4-14 一趟快速排序示例,图4-15 快速排序的全过程,下面给出快速排序的划分算法及快速排序的完整算法。算法4-11 快速排序中序列的划分算法。int qpass(RECORD R,int low,int high)/*待排记录放在Rlow到Rhigh中*/int i,j,k;RECORD x;i=low;,j=high;x=Rlow;k=Rlow.key;while(i=k)j;Ri=Rj;While(ij)&(Ri.key=k),i+;Rj=Ri;Ri=x;return i;根据快速排序方法的基本思想，快速排序算法可写成如下递归过程。,算法4-12 快速排序的递归算法。void quicksort(RECORD R,int low,int high)/*待排记录放在Rlow到Rhigh中*/int i;if(lowhigh)i=qpass(R,low,high);,quicksort(R,low,i1);quicksort(R,i+1,high);快速排序的运算时间，在待排序记录已经有序的情况下为最长，其平均比较次数为n(n1)/2，记为O(n2)；如果选择的划分点元素恰好是序列的中央，则所划分的前后两个子序列元素数目近乎相等，这时排序速度最快。快速排序的平均比较次数是O(nlbn)。,4.4.5 归并排序 归并(merging)就是将两个(或两个以上)的有序表合并成一个新的有序表的操作。若是对2个有序表进行的归并则称为2路归并。对于一个无序表来说，归并排序把它看成是由n个只包含一个记录的有序表组成的表，然后进行两两归并，最后形成包含n个记录的有序文件。,2路归并排序的思想：设初始文件含有n个记录，则可看成n个有序的子文件，每个子文件长度为1，然后两两归并，得到n/2个长度为2或1的子文件，再两两归并，如此重复，直到得到一个长度为n的有序子文件为止。例如：关键字序列为(49，38，65，97，76，13，27)。归并排序时，先将这7个记录看成长度为1的7个有序子序列，然后逐步两两归并，排序过程如图4-16所示。,图4-16 2路归并排序示例,从上例可看出，2路归并排序算法中需先解决两个问题：(1)两个有序子序列的归并问题；(2)2路归并排序进行一趟的算法。算法4-13 归并两个有序序列的算法。设两个有序序列存储在一维数组R中，有序子序列1为(Rl，Rl+1，Rm)，有序子序列2为(Rm+1，Rm+2，Rn)，本算法将它们归并为一个有序序