天天看點

分治之快速排序以及快速排序為何最快

算法思想

數組排序任務可以如下完成:

1)設k=a[0],将k挪到适當位置,使得比k小的元素都在k的左邊,比k大的元素都在k的右邊,和k相等的,不關心在k左右出現均可(O(n)時間完成)

2)把k左邊的部分快速排序

3)把k右邊的部分快速排序

(假設運氣比較好,每次基準元素被移動到中間,這樣的話時間複雜度為O(nlogn))

如何在O(n)的時間内将數組分成兩半,一般在小于基準值,一般大于基準值?

程式代碼

#include<iostream>
using namespace std;
int a[100];
//交換a,b的值 
void swap(int &a,int &b){
	int temp=a;
	a=b;
	b=temp;
}
void quickSort(int start,int end){
	if(start<end){
		//将數組首元素設為基準值
		int temp=a[start];
		//定義兩個指針i,j分别指向數組的頭部和尾部			 
		int i=start,j=end;			
		while(i<j){
			//偶數次交換之後,就不停的讓a[j]和temp相比,此時temp是a[i] 
			while((i<j)&&(a[j]>=temp)){
				j--;
			}
			//當i=j或者a[j]<temp的時候,就進行交換 
			swap(a[j],a[i]);
			//奇數次交換之後,就不停的讓a[i]和temp相比,此時temp是a[j] 
			while((i<j)&&(a[i]<=temp)){
				i++;
			}
			//當i=j或者a[i]>temp的時候,就進行交換 
			swap(a[j],a[i]);
		}
		//處理完後,a[i]=k
		//劃分完成後,對i左邊的和右邊的分别進行快速排序,但是a[i] 一定不參與排序
		quickSort(start,i-1);
		quickSort(i+1,end); 
	}
}

int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	} 
	quickSort(0,n-1);
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	} 

	return 0;
}

           

時間複雜度分析

當每次劃分元素的時候,左右兩邊的元素的個數相等,這個時候,是快速排序最好的一種情況,其時間複雜度為O(nlogn),與歸并排序類似

當每次劃分元素的時候,一邊的元素個數為0,這個時候,是快速排序最壞的一種情況,其時間複雜度為O(n2),此時,序列通常為有序。

一般情況下,快速排序的時間複雜度是O(nlogn)

快速排序具有廣泛的應用,通常認為是性能最高的排序算法,在c++的algorithm檔案中的sort函數所用到的正是快速排序。

知識拓展:快速排序為何最快

我們都知道,歸并排序,堆排序的時間複雜度均為O(nlogn),為何快速排序就最快了呢,因為快速排序每次都會與一個基準值做比較,如果我們把這個基準值放在寄存器裡,由于寄存器的速度遠遠大于cache和主存的速度,是以快速排序的性能将會得到巨大的提升,是以快速排序的性能最優。

繼續閱讀