C++实现快速排序(递归)
快速排序是一种平均性能很好的算法，它的期望运行时间是O(nlgn),且其中隐藏的常数因子非常小。但是它的最坏运行时间是O(n^2)。最后我会对其进行分析。快速排序关键部分分为两部分：
1.数组划分过程：
将一个数组以其最后一个元素作为主元，并且围绕它来划分数组，使得在此元素之前的数组元素均小于它，在其后的数组元素均大于它，划分过程如下：
实现代码如下：
int Partition(int a[],int low,int high){ //传递参数为数组、数组上界和下界
int x = a[high],i = low-1;
for(int j = low;j <= high-1;++j){
if(a[j] <= x){
++i;
swap(a[i],a[j]);//交换元素位置
}
}
swap(a[i+1],a[high]);
return i+1;
}
下面是元素交换函数：
void swap(int& first , int& second){
int tem = 0;
tem = first;
first = second;
second = tem;
}
2.快速排序递归实现：
void quickSort(int a[],int low,int high){
if(low < high){//递归终止条件
int q = Partition(a,low,high); //找到主元位置
quickSort(a,low,q-1);//对主元位置之前的数组进行快速排序
quickSort(a,q+1,high);//对主元位置之后的数组进行快速排序
}
}
3.算法最坏情况分析：
算法的最坏情况就是划分过程中两个区域分别包含1个和n-1个元素的时候，比如数组元素已经排好序，但是划分数组时却仍会使比主元小的数组元素进行自我交换。最坏情况下算法时间复杂度为O(n^2)。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
