[计算机]各种排序的实现与效率分析.pdfVIP

各种排序的实现与效率分析 一、排序原理 1 1 （11）直接插入排序 基本原理：这是最简单的一种排序方法，它的基本操作是将一个记录插入到已排好的 有序表中，从而得到一个新的、记录增1的有序表。 效率分析：该排序算法简洁，易于实现。从空间来看，他只需要一个记录的辅助空间， 即空间复杂度为O（1）.从时间来看，排序的基本操作为：比较两个关键字的大小和移动记 录。当待排序列中记录按关键字非递减有序排列（即正序）时，所需进行关键字间的比较次 数达最小值n-1，记录不需移动；反之，当待排序列中记录按关键字非递增有序排列（即逆 序）时，总的比较次数达最大值（n+2）(n-1)/2，记录移动也达到最大值（n+4）(n-2)/2.由于 待排记录是随机的，可取最大值与最小值的平均值，约为n²/4.则直接插入排序的时间复杂 度为O（n²）. 由此可知，直接插入排序的元素个数n越小越好，源序列排序度越高越好 （正序时时间复杂度可提高至O（n））。插入排序算法对于大数组，这种算法非常慢。但是 对于小数组，它比其他算法快。其他算法因为待的数组元素很少，反而使得效率降低。插入 排序还有一个优点就是排序稳定。 2 2 （22）折半插入排序 基本原理：折半插入是在直接插入排序的基础上实现的，不同的是折半插入排序在将 数据插入一个有序表时，采用效率更高的“折半查找”来确定插入位置。 效率分析：由上可知该排序所需存储空间和直接插入排序相同。从时间上比较，折半 插入排序仅减少了关键字间的比较次数，为O(nlogn)。而记录的移动次数不变。因此，折半 查找排序的时间复杂度为O(nlogn)+O（n²） =O（n²）。排序稳定。 3 3 （33）希尔排序 基本原理：希尔排序也一种插入排序类的方法，由于直接插入排序序列越短越好，源 序列的排序度越好效率越高。Shell 根据这两点分析结果进行了改进，将待排记录序列以一 定的增量间隔dk 分割成多个子序列，对每个子序列分别进行一趟直接插入排序, 然后逐步 减小分组的步长dk，对于每一个步长dk 下的各个子序列进行同样方法的排序,直到步长为 1 时再进行一次整体排序。因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组 步长dk下每个子序列的规模都不大，用直接插入排序效率都较高。尽管在随后的步长dk 递 减分组中子序列越来越大，但由于整个序列的有序性也越来越明显，则排序效率依然较高。 这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。 效率分析 希尔排序有以下几个关键特性： ： (1) 希尔排序的核心是以某个增量dk 为步长跳跃分组进行插入排序，由于分组的步长dk 逐步缩小，所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列才能使 得希尔方法的时间效率最高； (2) 待排序列记录的个数n 、跳跃分组步长逐步减小直到为1时所进行的扫描次数T、增量 的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔 算法的时间复杂度：其中记录关键字比较的次数是重要因素，它主要取决于分组步长序列的 选择； (3) 希尔方法是一种不稳定排序算法，因为其排序过程中各趟的步长不同，在第k 遍用dk 作为步长排序之后，第k +1 遍排序时可能会遇到多个逆序存在，影响排序的稳定性。 3 3 （33）冒泡排序 基本原理：冒泡排序分为若干趟进行，每一趟排序从前往后比较每两个相邻的元素的 大小（因此一趟排序要比较n-1 对位置相邻的数）并在每次发现前面的那个数比紧接它 后 的数大时交换位置；进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作（最 坏情况下要跑n-1 趟，这种情况在最小的数位于给定数列的最后面时发生）。事实上，在第 一趟冒泡结束后，最后面那个数肯定是最大的了，于是第二次只需要对前面n-1个数排序， 这又将把这n-1 个数中最大的数放到整个数列的倒数第二个位置。这样下去，冒泡排序第i 趟结束后后面i 个数都已经到位了，第i+1 趟实际上只考虑前n-i 个数（需要的比较次数比 前面所说的n-1 要小）。 效率分析：冒泡排序在给出的序列为正序排列时是最好的情况，这时每一次比较都不 需要要进行交换操作。因此冒泡排序最好情况下需要交换0次。