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

各种排序的实现与效率分析一、排序原理（1111）直接插入排序基本原理：这是最简单的一种排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录增1的有序表。效率分析：该排序算法简洁，易于实现。从空间来看，他只需要一个记录的辅助空间，即空间复杂度为O（1）.从时间来看，排序的基本操作为：比较两个关键字的大小和移动记录。当待排序列中记录按关键字非递减有序排列（即正序）时，所需进行关键字间的比较次数达最小值n-1，记录不需移动；反之，当待排序列中记录按关键字非递增有序排列（即逆序）时，总的比较次数达最大值（n+2）(n-1)/2，记录移动也达到最大值（n+4）(n-2)/2.由于待排记录是随机的，可取最大值与最小值的平均值，约为n²/4.则直接插入排序的时间复杂度为O（n²）.由此可知，直接插入排序的元素个数n越小越好，源序列排序度越高越好（正序时时间复杂度可提高至O（n））。插入排序算法对于大数组，这种算法非常慢。但是对于小数组，它比其他算法快。其他算法因为待的数组元素很少，反而使得效率降低。插入排序还有一个优点就是排序稳定。（2222）折半插入排序基本原理：折半插入是在直接插入排序的基础上实现的，不同的是折半插入排序在将数据插入一个有序表时，采用效率更高的“折半查找”来确定插入位置。效率分析：由上可知该排序所需存储空间和直接插入排序相同。从时间上比较，折半插入排序仅减少了关键字间的比较次数，为O(nlogn)。而记录的移动次数不变。因此，折半查找排序的时间复杂度为O(nlogn)+O（n²）=O（n²）。排序稳定。（3333）希尔排序基本原理：希尔排序也一种插入排序类的方法，由于直接插入排序序列越短越好，源序列的排序度越好效率越高。Shell根据这两点分析结果进行了改进，将待排记录序列以一定的增量间隔dk分割成多个子序列，对每个子序列分别进行一趟直接插入排序,然后逐步减小分组的步长dk，对于每一个步长dk下的各个子序列进行同样方法的排序,直到步长为1时再进行一次整体排序。因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长dk下每个子序列的规模都不大，用直接插入排序效率都较高。尽管在随后的步长dk递减分组中子序列越来越大，但由于整个序列的有序性也越来越明显，则排序效率依然较高。这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。效率分析：希尔排序有以下几个关键特性：(1)希尔排序的核心是以某个增量dk为步长跳跃分组进行插入排序，由于分组的步长dk逐步缩小，所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列才能使得希尔方法的时间效率最高；(2)待排序列记录的个数n、跳跃分组步长逐步减小直到为1时所进行的扫描次数T、增量的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔算法的时间复杂度：其中记录关键字比较的次数是重要因素，它主要取决于分组步长序列的选择；(3)希尔方法是一种不稳定排序算法，因为其排序过程中各趟的步长不同，在第k遍用dk作为步长排序之后，第k+1遍排序时可能会遇到多个逆序存在，影响排序的稳定性。（3333）冒泡排序基本原理：冒泡排序分为若干趟进行，每一趟排序从前往后比较每两个相邻的元素的大小（因此一趟排序要比较n-1对位置相邻的数）并在每次发现前面的那个数比紧接它后的数大时交换位置；进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作（最坏情况下要跑n-1趟，这种情况在最小的数位于给定数列的最后面时发生）。事实上，在第一趟冒泡结束后，最后面那个数肯定是最大的了，于是第二次只需要对前面n-1个数排序，这又将把这n-1个数中最大的数放到整个数列的倒数第二个位置。这样下去，冒泡排序第i趟结束后后面i个数都已经到位了，第i+1趟实际上只考虑前n-i个数（需要的比较次数比前面所说的n-1要小）。效率分析：冒泡排序在给出的序列为正序排列时是最好的情况，这时每一次比较都不需要要进行交换操作。因此冒泡排序最好情况下需要交换0次。给出的序列逆序排列是最坏的情况，这时每一次比较都要进行交换操作。一次交换操作需要3次赋值实现，因此冒泡排序最坏情况下需要赋值3n(n-1)/2次。比较次数方面，无论数据如何，每次排序均要比较n(n-1)/2次。（4444）快速排序基本原理：快速排序是对冒泡排序的一种改进，它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序采用了分治法的思想，把大的问题分解为同类型的小问题。一般分如下步骤：（1）选择一个中枢元素（有很多选法，我的实现里使用第一个元素为中枢的简单方法）（2）以该中枢元素为基准点，将小于中枢的元素放在中枢后集合的前部分，比它大的在集合后部分，待集合基本排序完成后（此时前部分元素小于后部分元素），把中枢元素放在合适的位置。（3）根据中枢元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序算法即可。这里的重点与难点在于第二步，这一步的方法是以第一个元素为中枢元素，刚开始时使用低指针指向中枢元素。当中枢元素在低指针位置时，此时我们判断高指针指向的元素是否小于中枢元素，如果大于中枢元素则高指针继续向头移动，如果小于则与中枢元素交换，此时中枢元素被移到了高指针位置；当中枢元素在高指针位置时，我们此时判断低指针指向的元素是否大于中枢元素，如果小于中枢元素则低指针继续向尾移动，如果大于则与中枢元素交换，此时中枢元素又回到了低指针位置；这时是拿高还是低指针所指向的元素与中枢比较时根据前面逻辑来处理，直到高低指针指向同一位置则完成一轮排序，然后再对中枢元素两边的序列进行同样的操作直到排序完成效率分析：快速排序的平均时间为knlnlnlnln(n),其中n为待排时间中记录的个数，k为某个常数，经验证明，在所有同数量级的此类排序方法中，快速排序的常数因子k最小。因此，就平均时间而言，快速排序时最好的一种内部排序。快速排序在最好的情况时是正序，比较次数和移动次数均为O（nlnlnlnln(n)），最坏状况下，比较次数和移动次数均为n(n-1)/2次。（5555）简单选择排序基本原理：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（i=1）先从array[i]开始逐个检查，看哪个数最小就记下该数所在的位置于min中，等一轮扫描完毕，如果找到比array[i-1]更小的元素，则把array[min]和a[i-1]对调，这时array[i]到最后一个元素中最小的元素就换到了array[i-1]的位置。如此反复进行第二轮、第三轮…直到循环至最后一元素效率分析：选择排序在第i次选择时赋值和比较都需要n-i次（在n-i+1个数中选一个出来作为当前最小值，其余n-i个数与当前最小值比较并不断更新当前最小值），然后需要一次赋值操作。总共需要n(n-1)/2次比较。交换次数与序列的初始排列有关。交换在最好状况下是待排数据为正序，交换为0次。最坏情况是每一趟都要进行交换，总的对象移动次数为3(n-1)直接选择排序是一种不稳定的排序方法。（6666）堆排序基本原理：堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节第一步：从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的从树中去掉，并从数组最后往前存放。第二步：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。效率分析：堆排序对n较大的文件还是有效的，对记录较少的文件效率较低。因为堆排序其主要运行时间都耗费在建初始对和调整建新堆时进行的反复筛选上。对深度为k的对，筛选中关键字比较次数最多为2（n-1）次，则在建含n个元素、深度为h的堆时，总进行的关键字比较次数不超过4n。由此，堆排序在最坏的情况下，其时间复杂度为O（nlnlnlnln(n)）。（7777）归并排序基本原理：归并排序分两步操作：第一步将数组分解成更小的数组，直到数组只有一个元素为止，每次划分点为（len–1）/2=mid,将数组分成[from,mid]和[mid+1,to],第二步就是将分解的数组两两合并，合并后的数组是有序的，直到合并成一个数组为止，合并过程中会用到一个临时数组，用来存储合并后的结果。每次合并后，将数组的数据传给原数组对应的位置。二、测试数据（1）当n=10时的一组随机数据的测试结果：（2）当n=100时的一组随机数据的测试结果：（3）当n=200时的一组随机数据的测试结果：（4）当n=500时的一组随机数据的测试结果：（5）具体有序数据的(数组元素为1~10)的测试结果：三、分析前面所述的各种方法各有优点适用场合也不同。通常选择排序方法的是考虑的因素有如下4点：（1）待排序的记录数目n的大小（2）记录本身数据量的大小，即记录中除关键字外其他信息量的大小（3）关键字结构及其分布情况（4）堆排序的稳定性要求从以上实验结果可观察的结论如下：（1）如果待排记录的个数n较小，则可采用直接插入排序或折半插入排序（2）如果待排记录的个数n较大，应该选择时间复杂度为O（nlnlnlnln(n)）的排序方法，如快速排序，堆排序或归并排序。1快速排序是处理大量数据的最好方法。当待排序序列的关键字是随机分布时，快速排序的平均时间复杂度最优，但是在待排序序列基本有序时，将蜕化为冒泡排序，其时间性能将不如堆排序或归并排序。2堆排序所需的辅助空间少于快速排序，并且在最坏的情况下时间复杂度不会变化。3归并排序所需的时间比堆排序省，但是它所需的辅助存储空间最多（3）快速排序、堆排序、希尔排序和直接选择排序都是不稳定的排序法，直接插入排序法、冒泡排序法、归并排序法都是稳定的排序法。（4）如果待排序列记录的厨师状态已按关键字基本有序，则选择直接插入排序或冒泡排序。实验总结：排序算法的性能分析和选择是一个复杂而又实际的问题,文中讨论的仅仅是这6种排序算法的平均时间性能.在实际应用中,应根据经验和实际情况合理选择算法.例如,从平均时间性能而言,快速排序无疑是最优的,其所需时间最省,但快速排序在最坏情况下的时性能却不如堆排序和归并排序.又比如,在插入排序、冒泡排序和选择排序中,以直接插入排为最简单,当序列中的记录“基本有序”或问题规模n较小时,它是最佳的排序方法.因此常将它和其他的排序方法,诸如快速排序、归并排序等结合在一起使用.