程序员面试必考题(三):各种排序算法原理及其比较 下载本文

www.accppx.com

一般地,选择序列的第一个元素作为枢轴。若含n个元素的序列元素随机分布,则枢轴将序列划分为元素个数大致相等的两个子序列,再继续划分为四个子序列,…,划分的次数不多于O(log2n),每趟划分时最多对n个元素进行甄别,故时间复杂度为O(nlog2n)。但若序列已有序,每次选择的枢轴都是本序列中的最小值或是最大值,划分后的两个子序列中有一个为空,另外一个包含其余所有元素。此种情况下达到快速排序的最坏情形,时间复杂度为O(n2)。 6.堆排序

堆(Heap)是一棵完全二叉树,其中每个元素都大于等于它的所有孩子。二叉树根称为堆顶,它是堆中最大元素。这样的堆称为最大堆或大根堆。堆中任一棵子树也满足堆的定义。类似地,可以定义最小堆或小根堆,即每个元素都小于等于它的所有孩子。以下讨论以最大堆为例。

堆的逻辑结构是一棵完全二叉树,可以用数组保存。元素A[i]若有左子结点,则保存在A[2*i+1]中,若有右子结点,则保存在A[2*i+2]中。利用堆结构实现的排序过程称为堆排序(Heap Sort)。 对数组A[0],A[1],…,A[n-1]进行堆排序的第一步是采用递归思想建初始堆。将分别以A[(n-1)/2],A[(n-1)/2-1],…,A[0]为根的二叉树依次调整为子堆。

www.accppx.com

若当前调整以A[i]为根的子树,将A[i]与其两个子结点(若存在)中的较大者进行比较,若A[i]较大,则调整完成;若A[i]较小,则交换A[i]与其较大子结点,然后继续调整以A[i]为根的子树。直到A[i]大于它的所有子结点或是已经到达叶结点时为止。

当调整以A[i]为根的子树时,它的各子树已经满足堆的定义。若没有发生A[i]与其较大子结点之间的交换,表明以A[i]为根的子树已满足堆的定义;若发生交换,A[i]交换到其子结点的位置,这棵子树可能不再满足堆的定义,还需要继续调整。

当以A[0]为根的子树调整完毕,表明初始堆已经建成。这个过程的时间复杂度为O(n)。

初始堆建成后,将堆顶元素A[0]与堆中最后一个元素A[n-1]互换(实际上是将最大值输出到A[n-1]中保存)。调整以A[0]为根的子树为堆(注意,此时堆中元素个数为n-1),A[0],A[1],…,A[n-2]又成为最大堆。这称为一趟堆排序。再将堆顶元素A[0]与堆中最后一个元素A[n-2]互换,剩余元素重新整理为堆。继续这个过程。直到堆中只有一个元素A[0]时为止,堆排序完成。此时数组中保存的是已有序序列。

每次从堆中选择最大值时只需O(1),调整堆的过程中,将新的堆顶放置到合适的位置,比较与交换的次数不超过二叉树的高。故时间复杂度为O(nlog2n)。

www.accppx.com

向堆中添加一个新元素的过程是,将元素添加为新的叶结点,同时保持树形是完全树。然后将该元素向根的方向移动:若新元素比父结点大,则交换两个结点,继续与新的父结点比较并进行必要的交换,直到其中的元素大小关系满足要求时为止。 7.二路归并排序

归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法。与快速排序算法一样,归并排序算法也采用了分治法的思想。 归并排序使用递归来实现: 如果数组中有多于1个元素 (1)将数组分为两半; (2)归并排序左半段; (3)归并排序右半段;

(4)将两个子数组归并为一个有序数组。

假定数组A[0],A[1],…,A[n-1]满足:A[0],…,A[m]升序排列,且A[m+1],…,A[n-1]也升序排序,归并操作可将两个有序子段合并为一个有序段。设i=0,j=m+1,k=1,比较A[i]与A[j],不妨设较小者为A[i],则B[k]=A[i],i++,k++。继续这个过程,直到两个有序序列中

www.accppx.com

的一个为空,将另一个有序序列中的全部剩余元素拷贝到数组B中。归并完成。

归并排序过程中,为了保存每趟归并的结果,需要与原始待排序数组等大的临时数组。归并排序的空间复杂度为O(n)。 8.基数排序

若数组A[0],A[1],…,A[n-1]中均保存两位十进制整数。设置10个盒子,编号为0到9。现对数组中各元素按个位数分类,个位数为r(0≤r≤9)的元素依次放入编号为r的盒子中。这称为第一趟分配。之后按盒子编号从0到9,每个盒子中按数据放入的次序将数据收集起来。这称为第一趟收集。将收集的数据再按十位数分类,十位数为

r(0≤r≤9)的元素依次放入编号为r的盒子中。这称为第二趟分配。

之后是第二趟收集。结果为有序序列。

扩展上述排序思想,基数排序可以对任何数制的元素进行排序。若进制为r,则盒子数为r个。位数为k时,分配与收集的趟数为k。从权值低到权值高依次进行。

基数排序还可以应用到多关键字的排序中。 9.外部排序

如果一组记录数量太大而无法同时保存到主存中时,那么只能将其中一些记录先从磁盘中读出来进行排序,然后再把这些记录写回磁盘。

www.accppx.com

这个过程不断重复下去,直到对整个文件进行了排序。这个过程中,每个记录可能被读出多次。

文件读取方式是顺序读取,采用归并的思想可以实现对文件中有序子序列的归并操作。若一个文件有n条记录,对这个文件进行外部排序需要log2n趟扫描,即对每条记录log2n次磁盘读写。

以上内容由北大青鸟佳音校区老师于网络整理,学计算机课程选择北大青鸟佳音校区!