排序的实现与效率分析

只看该作者 · 2011-10-23 22:22

本帖最后由粉色壁纸于 2011-10-23 22:23 编辑

一、排序原理
（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²）。排序稳定。

只看该作者 · 2011-10-23 22:22

（3333）希尔排序
基本原理：希尔排序也一种插入排序类的方法，由于直接插入排序序列越短越好，源
序列的排序度越好效率越高。Shell  根据这两点分析结果进行了改进，将待排记录序列以一
定的增量间隔 dk  分割成多个子序列，对每个子序列分别进行一趟直接插入排序,  然后逐步
减小分组的步长 dk，对于每一个步长 dk  下的各个子序列进行同样方法的排序,直到步长为
1  时再进行一次整体排序。因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组
步长 dk 下每个子序列的规模都不大，用直接插入排序效率都较高。尽管在随后的步长 dk  递
减分组中子序列越来越大，但由于整个序列的有序性也越来越明显，则排序效率依然较高。
这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。
效率分析：希尔排序有以下几个关键特性：
(1)  希尔排序的核心是以某个增量 dk  为步长跳跃分组进行插入排序，由于分组的步长 dk
逐步缩小，所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列才能使
得希尔方法的时间效率最高；
(2)  待排序列记录的个数 n  、跳跃分组步长逐步减小直到为 1 时所进行的扫描次数 T、增量
的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔
算法的时间复杂度：其中记录关键字比较的次数是重要因素，它主要取决于分组步长序列的
选择；
(3)  希尔方法是一种不稳定排序算法，因为其排序过程中各趟的步长不同，在第 k  遍用 dk
作为步长排序之后，第 k  +1  遍排序时可能会遇到多个逆序存在，影响排序的稳定性。

只看该作者 · 2011-10-23 22:22

（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）根据中枢元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，
对左边的，右边的分别递归调用快速排序算法即可。

只看该作者 · 2011-10-23 22:22

这里的重点与难点在于第二步，这一步的方法是以第一个元素为中枢元素，刚开始时
使用低指针指向中枢元素。当中枢元素在低指针位置时，此时我们判断高指针指向的元素是
否小于中枢元素，如果大于中枢元素则高指针继续向头移动，如果小于则与中枢元素交换，
此时中枢元素被移到了高指针位置；当中枢元素在高指针位置时，我们此时判断低指针指向
的元素是否大于中枢元素，如果小于中枢元素则低指针继续向尾移动，如果大于则与中枢元
素交换，此时中枢元素又回到了低指针位置；这时是拿高还是低指针所指向的元素与中枢比
较时根据前面逻辑来处理，直到高低指针指向同一位置则完成一轮排序，然后再对中枢元素
两边的序列进行同样的操作直到排序完成
效率分析：快速排序的平均时间为 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]到最后一个元素中最小

只看该作者 · 2011-10-23 22:22

的元素就换到了 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],第二步就是
将分解的数组两两合并，合并后的数组是有序的，直到合并成一个数组为止，合并过程中会
用到一个临时数组，用来存储合并后的结果。每次合并后，将数组的数据传给原数组对应的
位置。
二、测试数据