内容发布更新时间 : 2024/6/26 9:02:53星期一 下面是文章的全部内容请认真阅读。
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次磁盘读写。
以上内容由北大青鸟佳音校区老师于网络整理，学计算机课程选择北大青鸟佳音校区！