C++快速排序
m78星云杰克 人气:0一、问题描述
[问题] 应用快速排序方法对一个记录序列进行升序排列。快速排序(quick sort)的分治策略如下。
(1)划分:选定一个记录作为轴值,以轴值为基准将整个序列划分为两个子序列r(1)… r(i-1))和r(i+1)…r(n),轴值的位置i在划分的过程中确定,并且前一个子序列中的记录均小于或等于轴值,后一个子序列中的记录均大于或等于轴值;
(2)求解子问题:分别对划分后的每一个子序列造归处理;
(3)合并:由于子序列排序是就地进行的,所以合并不需要任何操作。
二、想法
[想法] 首先对待 排序记录序列进行划分,划分的轴值应该遵循平衡子问题的原则,使划分后的两个子序列的长度尽量相等,这是决定快速排序算法时间性能的关键。轴值的选择有很多方法,例如,可以随机选出一个记录作为轴值,从而期望划分是较平衡的。
第一次划分过程:
后续排序结果:
三、算法实现
int Partition(int r[],int start,int end) { int i=start,j=end; while(i<j) { while (i<j&&r[i]<=r[j]) //对右侧扫描,即r[i] 与右侧的r[j...i+1]比较,升序排序,如果有小于r[i]的值,即右小于左则跳出循环,还有i>=j也跳出循环,即比较完,没有比它小的,必须两个条件同时满足。 j--; if(i<j) { //在i<j的情况下满足r[j]<r[i] r[i]=r[i]^r[j]; //交换值 r[j]=r[i]^r[j]; //注意:如果位置一样不可以使用异或交换值,即r[1]不能异或r[1]; r[i]=r[i]^r[j]; //也可以定义中间值,进行交换 i++; } } while (i<j&&r[i]<=r[j])//对左侧扫描,即r[j] 与左侧的r[i...j-1]比较,升序排序,如果有大于r[j]的值,即左侧值大于右侧值则跳出循环,还有i>=j也跳出循环,即比较完,没有比它大的,必须两个条件同时满足。 i++; if(i<j) { //在i<j的情况下满足r[i]>r[j] r[i]=r[i]^r[j]; r[j]=r[i]^r[j]; r[i]=r[i]^r[j]; j--; } return i; //返回轴值 } void Quicksort(int r[],int start ,int end) { //快速排序 int pivot; //记录轴值 if(start<end) { //界限值 pivot=Partition(r,start,end); //排序并获得轴值 Quicksort(r,start,pivot-1); //对轴值左侧递归 Quicksort(r,pivot+1,end); //对轴值右侧递归 } }
总结
快速排序是众多排序方法中,较为重要的一种,它在排序算法中具有排序速度快,而且是就地排序等优点,使得在许多编程语言的内部元素排序实现中采用的就是快速排序,很多面试题中也经常遇到。
加载全部内容