算法思想
數組排序任務可以如下完成:
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和主存的速度,是以快速排序的性能将會得到巨大的提升,是以快速排序的性能最優。