快速排序的pivot优化

66 阅读 0 评论 44 点赞

我是靠谱客的博主落后冰棍，最近开发中收集的这篇文章主要介绍快速排序的pivot优化，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

算法课的笔记，内容是快排的pivot优化
快速排序算法的性能主要受partition执行效果的影响，通俗的说，选择的基准元素越接近中位数，快排的性能越好，反之越差，当输入数组严格递增或递减时，快排的最坏时间复杂度为O(n²)
pivot优化旨在选择一个更接近中位数的基准元素
具体做法为：
对于坐标从p到r的序列进行快排，以前我们用r作为基准元素，现在我们用a[p],a[r],a[(p+r+1)/2]这三个数的中位数作为基准元素
注：后续了解到还有更好一些的方法，将序列分成n/5组，每组五个数，每组进行排序，选出中位数，然后这些中位数的中位数（还是用这个方法递归求解）就会更加接近真实的中位数
代码：

int choosepivot(int*a,int p,int r){
	int q=p+(r-p+1)/2;
	if((a[p]-a[q])*(a[p]-a[r])<=0) 
		return p;
	else if((a[q]-a[p])*(a[q]-a[r])<=0)
		return q;
	return r;
}

优化之后的时间复杂度能在最坏情况下也是O(nlogn)
完整代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int choosepivot(int*a,int p,int r){
	int q=p+(r-p+1)/2;
	if((a[p]-a[q])*(a[p]-a[r])<=0) 
		return p;
	else if((a[q]-a[p])*(a[q]-a[r])<=0)
		return q;
	return r;
} 
void swap(int* a,int* b){
	int x=*a;
	*a=*b;
	*b=x;
}
int partition(int*a,int p,int r){
	int pivot_index=choosepivot(a,p,r);
	if(pivot_index!=r)
		swap(a[pivot_index],a[r]);
	int pivot=a[r];
	int i=p-1;
	for(int j=p;j<=r-1;j++){
		if(a[j]<pivot) {
			i++;
			swap(a[i],a[j]);
		}
	}
	swap(a[i+1],a[r]);
	return i+1;
}
void quick_sort(int* a,int p,int r){
	if(p<r){
		int q=partition(a,p,r);
		quick_sort(a,p,q-1);
		quick_sort(a,q+1,r);
	}
}
int main(){
	int n;
	cin>>n;
	int* a=new int [n];
	for(int i=1;i<=n;i++)
		cin>>a[i];
	quick_sort(a,1,n);
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	return 0;
}