C++快速排序算法简明理解

  

一、问题描述

[问题] 应用快速排序方法对一个记录序列进行升序排列。快速排序(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);		//对轴值右侧递归
	}
}

总结

快速排序是众多排序方法中，较为重要的一种，它在排序算法中具有排序速度快，而且是就地排序等优点，使得在许多编程语言的内部元素排序实现中采用的就是快速排序，很多面试题中也经常遇到。

到此这篇关于C++快速排序算法简明理解的文章就介绍到这了,更多相关C++快速排序内容请搜索编程学习网以前的文章希望大家以后多多支持编程学习网！

相关文章
C/C++开发最新文章
热门教程