各种排序的实现与效率分析

1、各种排序的实现与效率分析一、排序原理（1）直接插入排序基本原理：这是最简单的一种排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录增1的有序表。效率分析：该排序算法简洁，易于实现。从空间来看，他只需要一个记录的辅助空间，即空间复杂度为（1）从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。当待排序列中记录按关键字非递减有序排列（即正序）时，所需进行关键字间的比较次数达最小值n,1记录不需移动；反之，当待排序列中记录按关键字非递增有序排列（即逆序）时，总的比较次数达最大值（n+2）（n1），记录移动也达到最大值（n+）（n2）由于待排记录是随机的，可取最

2、大值与最小值的平均值，约为*则直接插入排序的时间复杂度为（/）由此可知，直接插入排序的元素个数n越小越好，源序列排序度越高越好（正序时时间复杂度可提高至（n）。插入排序算法对于大数组，这种算法非常慢。但是对于小数组，它比其他算法快。其他算法因为待的数组元素很少，反而使得效率降低。插入排序还有一个优点就是排序稳定。（2）折半插入排序基本原理：折半插入是在直接插入排序的基础上实现的，不同的是折半插入排序在将数据插入一个有序表时，采用效率更高的“折半查找”来确定插入位置。效率分析：由上可知该排序所需存储空间和直接插入排序相同。从时间上比较，折半插入排序仅减少了关键字间的比较次数，为（nl。而记录的移

3、动次数不变。因此，折半查找排序的时间复杂度为（nln）+O）（n2）o排序稳定。（3）希尔排序基本原理：希尔排序也一种插入排序类的方法，由于直接插入排序序列越短越好，源序列的排序度越好效率越高。Shell根据这两点分析结果进行了改进，将待排记录序列以一定的增量间隔dk分割成多个子序列，对每个子序列分别进行一趟直接插入排序，然后逐步减小分组的步长dk,对于每一个步长dk下的各个子序列进行同样方法的排序，直到步长为1时再进行一次整体排序。因为不管记录序列多么庞大，关键字多么混乱，在先前较大的分组步长dk下每个子序列的规模都不大，用直接插入排序效率都较高。尽管在随后的步长dk递减分组中子序列越来越大

4、，但由于整个序列的有序性也越来越明显，则排序效率依然较高。这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。效率分析：希尔排序有以下几个关键特性：（1）希尔排序的核心是以某个增量dk为步长跳跃分组进行插入排序，由于分组的步长dk逐步缩小，所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列才能使得希尔方法的时间效率最高；（2）待排序列记录的个数n、跳跃分组步长逐步减小直到为1时所进行的扫描次数T、增量的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔算法的时间复杂度：其中记录关键字比较的次数是重要因素，它主要取决于分组步长序列的选择；（3）

5、希尔方法是一种不稳定排序算法，因为其排序过程中各趟的步长不同，在第k遍用dk作为步长排序之后，第k+1遍排序时可能会遇到多个逆序存在，影响排序的稳定性。3）冒泡排序基本原理：冒泡排序分为若干趟进行，每一趟排序从前往后比较每两个相邻的元素的大小（因此一趟排序要比较对位置相邻的数）并在每次发现前面的那个数比紧接它后的数大时交换位置；进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作（最坏情况下要跑趟，这种情况在最小的数位于给定数列的最后面时发生）。事实上，在第一趟冒泡结束后，最后面那个数肯定是最大的了，于是第二次只需要对前面个数排序，这又将把这个数中最大的数放到整个数列的倒数第二个位置。这

6、样下去，冒泡排序第趟结束后后面个数都已经到位了，第趟实际上只考虑前个数（需要的比较次数比前面所说的要小）。效率分析：冒泡排序在给出的序列为正序排列时是最好的情况，这时每一次比较都不需要要进行交换操作。因此冒泡排序最好情况下需要交换0次。给出的序列逆序排列是最坏的情况，这时每一次比较都要进行交换操作。一次交换操作需要3次赋值实现，因此冒泡排序最坏情况下需要赋值次。比较次数方面，无论数据如何，每次排序均要比较次。（4）快速排序基本原理：快速排序是对冒泡排序的一种改进，它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继

7、续进行排序，以达到整个序列有序。快速排序采用了分治法的思想，把大的问题分解为同类型的小问题。一般分如下步骤：（，）选择一个中枢元素（有很多选法，我的实现里使用第一个元素为中枢的简单方法）（2）以该中枢元素为基准点，将小于中枢的元素放在中枢后集合的前部分，比它大的在集合后部分，待集合基本排序完成后（此时前部分元素小于后部分元素），把中枢元素放在合适的位置。（3）根据中枢元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。这里的重点与难点在于第二步，这一步的方法是以第一个元素为中枢元素，刚开始时使用低指针指向中枢元素。当中枢元素在低指针

8、位置时，此时我们判断高指针指向的元素是否小于中枢元素，如果大于中枢元素则高指针继续向头移动，如果小于则与中枢元素交换，此时中枢元素被移到了高指针位置；当中枢元素在高指针位置时，我们此时判断低指针指向的元素是否大于中枢元素，如果小于中枢元素则低指针继续向尾移动，如果大于则与中枢元素交换，此时中枢元素又回到了低指针位置；这时是拿高还是低指针所指向的元素与中枢比较时根据前面逻辑来处理，直到高低指针指向同一位置则完成一轮排序，然后再对中枢元素两边的序列进行同样的操作直到排序完成效率分析：快速排序的平均时间为其中为待排时间中记录的个数，为某个常数，经验证明，在所有同数量级的此类排序方法中，快速排序的常数

9、因子最小。因此，就平均时间而言，快速排序时最好的一种内部排序。快速排序在最好的情况时是正序，比较次数和移动次数均为（），最坏状况下，比较次数和移动次数均为次。（5）简单选择排序基本原理：每一趟从待排序的数据元素中选出最小（或最大，的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（）先从开始逐个检查，看哪个数最小就记下该数所在的位置于中，等一轮扫描完毕，如果找到比更小的元素，则把和对调，这时到最后一个元素中最小的元素就换到了的位置-1如此反复进行第二轮、第三轮直到循环至最后一元素效率分析：选择排序在第次选择时赋值和比较

10、都需要n-次（在n-个数中选一个出来作为当前最小值，其余n-个数与当前最小值比较并不断更新当前最小值），然后需要一次赋值操作。总共需要n（n-1）次比较。交换次数与序列的初始排列有关。交换在最好状况下是待排数据为正序，交换为次。最坏情况是每一趟都要进行交换，总的对象移动次数为3（n-1）直接选择排序是一种不稳定的排序方法-（6）堆排序基本原理：堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字-堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节第一步：从最后一个非叶子节点为开始向前循环每个会支节点，

11、比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成-当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的从树中去掉，并从数组最后往前存放-第二步：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点-交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止-效率分

12、析：堆排序对n较大的文件还是有效的，对记录较少的文件效率较低。因为堆排序其主要运行时间都耗费在建初始对和调整建新堆时进行的反复筛选上。对深度为的对，筛选中关键字比较次数最多为（n-1）次，则在建含n个元素、深度为的堆时，总进行的关键字比较次数不超过n由此，堆排序在最坏的情况下，其时间复杂度为（n伍）。（7）归并排序基本原理：归并排序分两步操作：第一步将数组分解成更小的数组，直到数组只有一个元素为止，每次划分点为（n1）将数组分成和第二步就是将分解的数组两两合并，合并后的数组是有序的，直到合并成一个数组为止，合并过程中会用到一个临时数组，用来存储合并后的结果-每次合并后，将数组的数据传给原数组对

13、应的位置-1）当0时的一组随机数据的测试结果：1）当0时的一组随机数据的测试结果：柑2151se21515851邑屈循1000的一组随机数(382Q5J38S3d3d2ssX二.丄二.丄令.X二.丄二.丄令.X二.丄二.-M爭曲创爭曲创爭m学:Issnyy*旧那厌目曰隨谡样吕JnTl2g丄二.丄令.X二.丄二.丄令.X二.丄二.丄令-M-，-，-，-，-，-CL曲创爭曲创爭曲曲手:共wssTTyyu里旧?厌昌隨谡ffl样呂旨2_Lk.爱k:JG11533531曲0eios8J3553rfSrfSQ:JG6軒込：.墙痴卑斗-起薛湛吕型澤尤样芒加匸用怨业徘AFA土“AFA土“AFAa址蒔feTTv

14、-ytt舉旧体昌peffiw誹寻W2六寢W坝舉亘I%JAG338e3藝眞323HG33vei2G883523Q匚JLTLTJ5暮口FR土afa土afa土afa:爭剁爭爭剁爭爭剁二并：址8HV-V-WSW2sft坝臬旦IIEIM()当时的一组随机数据的测试结果:()当时的一组随机数据的测试结果:4)I占-适甘出即町T排轻圧止召取：集劇丫壷別田堰耻範EQ連銮9藝册sorfe门柑302it:5GGx当屈循5000的一组随机数据据的测丄二.丄令.X二.丄二.丄令.X二.丄二.丄令-M-，-，-，-，-CL曲创爭曲创爭曲曲手:址wftsTTyY*旧?厌昌隨谡ffl样呂旨2_Lk.爱kjsiaStItIS

15、jaaco5015jaecosaeiJ555jdieF臨御itmsoddesjoeJ0335册JSA1StItISjaaco3018J38553865J550aieHF啤離藝58632羽32&2结果：LLH旧申liiti|b包矩毎甘住启-vFfijbisperrii耙亲收丫评世圧世科星：徨舉丫崟御理田塩甄熱田更華9:2O0 x沖J謄隹矗斗+起詳卷旱/M莓$1権辽即於/忌艸iiiiiiii-XXX.-LLL.-LLL.-LLL.-LLL.-LLL.-LLL.-LLL.二芳盲2亲ei熾黠5S3823A3daJSrtLSOE33TtJSrteit233013L35rt3G83863ATtJ8JSrt

16、L20BJdTtJ5rtL02813838032Tt0LTt8882188JTtdl5806jlartee663823855rtasst滋M藝Tt3882L88Jddl5888jarfiSTted20Erf酣862838t矗张熱5)具体有序数据的(数组元素为11的0测)试结果：K6wlittwlittwlia-XXX.-Li-L.-i-i-i-XXX.-LLL.-i-i-i-XXX.r-rt出剁电出剁电出剁？I孙：9U址蒔ft渥鋼TTyytt舉共诅弼体盛peffiffi排68W2亲藤W.4壤是阜I%8J228528J4r4r4r35ttwlittwlittws电出剁电出对址矮feTTrg-2三

17、、分析:储転磐+起驛湛吕礙第尤桂蚤曲即能/翠bLLL前面所述的各种方法各有优点适用场合也不同。通常选择排序方法的是考虑的因素有如下4点：I八()待排序的记录数目的大小记录本身数据量的大小，即记录中除关键字外其他信息量的大小关键字结构及其分布情况堆排序的稳定性要求从以上实验结果可观察的结论如下：()如果待排记录的个数较小，则可采用直接插入排序或折半插入排序()如果待排记录的个数较大，应该选择时间复杂度为()的排序方法，如快速排序，堆排序或归并排序。速排序是处理大量数据的最好方法。当待排序序列的关键字是随机分布时，快速排序的平均时间复杂度最优，但是在待排序序列基本有序时，将蜕化为冒泡排序，其时间性能将不如堆排序或归并排序。排序所需的辅助空间少于快速排序，并且在最坏的情况下时间复杂度不会变化。并排序所需的时间比堆排序省，但是它所需的辅助存储空间最多快速排序、堆排序、希尔排序和直接选择排序都是不稳定的排序法，直接插入排序法、冒泡排序法、归并排序法都是稳定的排序