快速排序(QuickSort)一
时间:2016-12-14作者:华清远见
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法。 分治法的基本思想是:将原问题分解为若干个规模更小但结果与原问题相似的子问题。递归地解决这些子问题,然后将这些子问题的解结合为原问题的解。 假设当前待排序的无序序列为R,利用分治法可将快速排序的基本思路描述为: 1) 分解: 在R中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间,并使左边子区间中所有记录均小于等于基准记录,右边的子区间中所有记录大于等于pivot,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。 注意: 划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos]): R[ i ] ≤R[pivotpos]≤R[ j ] 其中i ≤pivotpos≤ j。 2) 求解 通过递归调用快速排序对左、右子区间R[ i]~R[pivotpos-1]和R[pivotpos+1]~R[j]快速排序。 3) 组合 因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步骤无须做什么,可看作是空操作。 使用C语言实现为: void QuickSort(SeqList R,int low,int high) 注意: 为排序整个文件,只须调用QuickSort(R,1,n)即可完成对R[1]~R[n]的排序. 3、划分算法Partition 第一步:(初始化)设置两个指针i和j,它们的初值分别为区间的下界和上界,即i=low,i=high;选取无序区的第一个记录R[i](即R[low])作为基准记录,并将它保存在变量pivot中; 第二步:令j自high起向左扫描,直到找到第1个小于pivot的记录R[j],将R[j])移至i所指的位置上,这相当于R[j]和基准R[i](即pivot)进行了交换,使小于基准pivot的记录移到了基准的左边,交换后R[j]中相当于是pivot;然后,令i指针自i+1位置开始向右扫描,直至找到第1个大于pivot的记录R[i],将R[i]移到i所指的位置上,这相当于交换了R[i]和基准R[j],使大于基准的记录移到了基准的右边,交换后R[i]中又相当于存放了pivot;接着令指针j自位置j-1开始向左扫描,如此交替改变扫描方向,从两端各自往中间靠拢,直至i=j时,i便是基准pivot终的位置,将pivot放在此位置上就完成了一次划分。 划分算法: int Partition(SeqList R,int i,int j)
发表评论
|