数据结构中的内部排序算法及性能分析.docx

数据结构中的排序算法及性能分析 一、引言 排序（sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。为了查找方便通常希望计算机中的表是按关键字有序的。因为有序的顺序表可以使用查找效率较高的折半查找法。在此首先明确排序算法的定义：假设n个记录的序列为 ， （1）关键字的序列为： ，需要确定1，2，n的一种排列：，使（1）式的序列成为一个按关键字有序的序列：上述定义中的关键字Ki可以是记录Ri（i=1,2，n）的主关键字，也可以是记录的次关键字，甚至是若干数据项的组合。若在序列中有关键字相等的情况下，即存在=（），且在排序前的序列中领先于。若在排序后的序列中Ri仍领先于，则称所用的排序方法是稳定的；反之若可能使排序后的序列中领先于，则称所用的排序方法是不稳定的。一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法的时间与算法中语句执行次数成正比，那个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),称O(f(n) 为算法的渐进时间复杂度，简称时间复杂度。通常，在排序的过程中须进行下列两种基本操作:(1)比较两个关键字的大小；（2）将记录从一个位置移动到另一个位置。前一个操作对大多数排序方法来说都是必要的，而后一个操作可以通过改变记录的存储方式来予以避免。待排记录有三种存储方式：（1）待排的一组记录存储在地址连续的一组存储单元上；（2）待排记录存储在静态链表中；（3）待排记录存储在地址连续的存储空间内，但同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”。在此我们讨论待排序00的记录存储在一组地址连续的存储单元的情况。在这种存储方式中，记录之间的次序关系由其存储位置决定，子序列中相邻的两个记录它们的存储位置也相邻，实现排序必须移动记录。在以后的讨论中这记录的关键字均为整数二、插入排序 2.1直接插入排序 直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已经排好序的有序列表中，从而得到一个新的、记录曾数1的有序表。 例如，已知待排序的一组记录的初始排列如下所示：R(49),R(38),R(65),R(97),R(76),R(13)R(27)R() （2-1）设在排序过程中，前4个记录已按关键字递增的次序重新排列，构成含4个记录的有序序列 R(38)R(49)R(65)R(97) (2-2) 现要将式（2-1）中的关键字为76的记录插入到上述序列，以得到一个新的含5个记录的有序序列，则首先要在式（2-2）中查找以确定R（76）所应插入的位置，然后进行插入。假设从R(97)开始从左向右比较，由于6576maxL.rj.key (1jL.r2.key），则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟冒泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后对前n-1个记录进行同样的操作。一般地，第i趟冒泡排序是从L.r1到L.rn-i+1依次比较相邻两个记录的关键字，并在逆序时交换相邻记录。整个排序过程需进行k（1kn）趟冒泡排序，判别冒泡排序结束的条件是“在一趟排序过程中没有进行过交换记录的操作”。以下是冒泡排序的过程示意图：初始关键字： 49 38 65 97 76 13 27 第一趟排序后： 38 49 65 76 13 27 97第二趟排序后： 38 49 65 13 27 76 97第三趟排序后： 38 49 13 27 65 76 97第四趟排序后： 38 13 27 49 65 76 97第五趟排序后： 13 27 38 49 65 76 97 第六趟排序后： 13 27 38 49 65 76 97 3.2快速排序快序排序（Quick Sort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分的纪录继续进行排序，以达到整个序列有序。假设待排序的序列为L.rs,L.rs+1,，L.rr，们首先任意选取一个记录作为支点，然后按照以下原则重新排列其余记录：将所有关键字教它小的记录都安置在它的位置之前，将所有关键字教它大的记录都放在它的位置之后。由此可将以上序列分割成两个子序列L.s,L.rs+1,，L.ri-1和L.ri+1,L.ri+2,，L.rt。这个过程称作一趟快速排序。一趟快速排序的具体算法是：设置两个指针low和high，它们的初始值分别是low和high，设支点记录的关键字为pointkey，首先从high所指位置向前搜索找到第一个关键字小于pointkey的记录和支点交换，然后从low所指位置起向后搜索，找到第一个关键字大于pointkey的记录和支点交换，重复这两部直至low=high为止。但是在排序过程中对支点记记录的赋值是不必要的，因为只有在一趟排序结束时low=high的位置才是pointkey的最后位置，所以先将pointkey的值赋给r0,一趟排序结束时在赋给相应位置整个快速排序可以递归进行，子进行一趟快速排序之后再分别对得到的两组子序列进行快速排序。其过程如下图： Pivotkey初始关键字 49 38 65 97 76 13 27 第一次交换后 27 38 65 97 76 13 （49） Low high第二次交换后 27 38 （49） 97 76 13 65 Low high 第三次交换后 27 38 13 97 76 （49） 65 Low high第四次交换后 27 38 13 （49） 76 97 65 Low high第五次交换后 27 38 13 （49） 76 97 65 Low=high完成第一趟排序 27 38 13 （49） 76 97 65 一次划分之后 27 38 13 49 76 97 65 分别进行排序 13 38 27 97 65 76 low high low high 13 27 38 76 65 97 low high low high 13 27 38 65 76 97 low=high low high 65 76 97 low=high有序序列 13 27 38 49 65 76 97四、选择排序 4.1直接选择排序选择排序（Selection Sort）的基恩思想是：每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录。其中最简单的就是直接选择排序（Straight Selection sort）。具体过程是第1次从R0到Rn-1中选取最小值，与R0交换，第二次从R1到Rn-1中选取最小值，与R1交换，.，第i次从Ri-1Rn-1中选取最小值，与Ri-1交换，.，第n-1次从Rn-2到Rn-1中选取最小值，与Rn-2交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。设有6个数的排序为例：初始状态 687354 6 - 3 第一次 387654 8 - 4 第二次 347658 7 -5 第三次 345678 排序完成 4.2堆排序堆排序（Heap Sort）堆排序是利用堆的性质进行的一种选择排序。在讨论堆排序之前首先了解一下堆。堆的定义如下：n个元素的序列k1,k2,kn当且仅当满足以下关系时，称之为堆kik2i，kik2i+1或kik2i，kik2i+1i为整数且小于n/2。用一维数组作此序列的存储结构则可将这个一维数组看成是一个完全二叉树，且堆的含义表明，完全二叉树中所有非终端节点的值均不大于（或不小于）其左右孩子节点的值。由此，序列k1，k2，kn是堆，则堆顶元素（即完全二叉树的根）必为列中的最大值或最小值例如下列两个堆，对应得完全二叉树如图所示：96,83,27,38,11,091212,36,24,85,47,30,53,9196243627 835385473009113891 以上的图左为的大顶堆右图为小顶堆。堆排序的思想是：利用大顶堆(小顶堆)（根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆,又称最大堆）堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。排序的基本方法是（以大顶堆为例）：（1）先将初始序列按照关键字R1，R2，Rn排列为大顶堆，这就是初始的无序区；（2）将堆顶元素和序列中的最后一个元素交换，这时形成了新的无序堆R1,R2,Rn-1和新的有序堆Rn；（3）将新的无序堆排列成有序堆并重复第二步。下面以（2-1）中的待排序列为例说明堆排序的过程：初始记录为R49,R38,R65,R97,R76,R13,R27,R49首先将初始待排序列建为大顶堆：4965382713769749原始待排序列4965972713763849第一次交换（97大于38所以交换之）4965972713764938第二次交换（38换下后导致49和38不符合规则故换之）9765492713764938第三次交换（38和97换后导致97和49不符合规则故换之）9765762713494938第四次交换（97和49交换之后导致49和76不符合规则故交换之）自此原始待排序列已成为一个大顶堆。下面就将这个大顶堆排列成为按关键字非递减有序序列。76384965657627133849271349499797第一次交换（将97与38交换） （将交换后剩余的堆排为大顶堆）65274927654976133849761338499797第二次交换（将76与27交换） （将交换后剩余的堆排为大顶堆）49134927274976653813766538499797第三次交换（将65与13交换） （将交换之后的堆排为大顶堆）49383827274976654913766549139797第四次交换（将49与38交换） （将交换之后的堆排为大顶堆）38131327273876654949766549499797第五次交换（将49和13交换） （将交换之后的堆排为大顶堆）2727133838137665494944449766549499797第六次交换（将38和27交换） （将交换之后的堆排为大顶堆）13132738382776654949766549499797第七次交换（将27和13交换） （将交换之后的堆排为大顶堆并将13并入有序序列）至此，已经用堆排序的方法将（2-1）中的待排序序列排为了按关键字非递减的有序序列。五、归并排序 5.1归并排序归并排序（Merge Sort）的含义是将两个或两个以上的有序表组合成一个新的有序表，即把待排子列分成若干个子列，将每一个子列分别排序，再把子序列合成整个序列。利用归并的分治法很容易实现排序。假设初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为一，然后两两归并，再两两归并，如此重复直到得到一个长度为n的有序序列位置，这种方法称为2-路归并排序。2-路归并操作中的核心操作是将一位数组中前后相邻的两个有序序列归并为一个有序序列。下面以R49,R39,R65,R97,R76,R13,R27为例说明归并排序的过程：初始关键字 49 38 65 97 76 13 27一趟归并之后 38 49 65 97 13 76 27二趟归并之后 38 49 36 97 13 27 69三趟归并之后 13 27 38 49 65 76 97至此就用归并排序将以上所示的待排序列排为了按关键字有序序列。六、各种排序方法的比较讨6.1稳定性（1）插入排序 插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。(2)希尔排序 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。 （3）冒泡排序冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。(4)快速排序 快速排序有两个方向，左边的i下标一直往右走，当ai acenter_index。如果i和j都走不动了，i j。 交换aj和acenter_index，完成一趟快速排序。在中枢元素和aj交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和aj交换的时刻。 (5)选择排序选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。(6)堆排序 我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, .1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。(7)归并排序 归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。综上，得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序是稳定的排序算法。6.2时间复杂度（1）插入排序直接插入排序算法必须进行n-1趟。最好情况下，即初始序列有序，执行n-1趟，但每一趟只比较一次，移动元素两次，总的比较次数是(n-1)，移动元素次数是2(n-1)。因此最好情况下的时间复杂度就是O ()。最坏情况(非递增)下，最多比较i次，因此需要的比较次数是：所以，时间复杂度为O()。(2)希尔排序希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O()好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。所以希尔排序是不稳定的，其时间复杂度为O()。（3）冒泡排序当原始数据正向有序时，冒泡排序出现最好情况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O ()。当原始数据反向有序时，冒泡排序出现最坏情况。此时，需进行n-1趟排序，第i趟作(n-i)次关键字间的比较，并且需执行(n -i)次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为O()。（4）快速排序如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O()；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O()。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况