基本思路
- 分治，將數(shù)組分為兩半琢感，以k為界限丢间，小于k的在左邊，大于k的在右邊驹针。
實(shí)現(xiàn)
有數(shù)組A
- 選A[i]的數(shù)值為k
- A[j]與k對(duì)比
-
如果A[j]>=k,j--;
- 如果A[j]<k,A[i]與A[j]交換位置,此時(shí)k變?yōu)榱薃[j],發(fā)生了1次交換
-
- 發(fā)生奇數(shù)次交換時(shí)烘挫，A[i]與k作比較(此時(shí)的k是A[j])
-
如果A[i]<=k,i++
-
如果A[i]>k，A[i]與A[j]交換位置柬甥，此時(shí)k變?yōu)榱薃[i]饮六，發(fā)生了2次交換
-
-
此時(shí)變?yōu)榱伺紨?shù)次交換圖片.png
-
交換的最終目的，是使得大于k的數(shù)在k的右邊苛蒲，小于k的數(shù)字k的左邊卤橄。
此時(shí)整個(gè)數(shù)組掃了一遍，時(shí)間復(fù)雜度為O(n)
代碼實(shí)現(xiàn)
void swap(int &a[i],int &a[j]){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
void QuickSort(a[],int s,int e){
//如果只有一個(gè)元素了臂外，就不排序了
if(s >= e)
return;
int k = a[s];
int i = s,j =e;
while(i!=j){
while(j>i && a[j]>=k)
j--;
swap(a[i],a[j]);
while(j>i && a[i]<=k)
i++;
swap(a[i],a[j]);
} // 處理結(jié)束之后窟扑，a[i] = k (循環(huán)里兩次交換)
QuickSort(a,s,i-1);
QuickSort(a,i+1,e);
}
復(fù)雜度分析
- 一般情況下
- 每次將數(shù)據(jù)分為兩部分的復(fù)雜度為n
- 對(duì)兩部分進(jìn)行排序的復(fù)雜度為logn
- 所以一般情況下復(fù)雜度為nlogn
- 但是無(wú)法保證每一次的k都能將數(shù)組分為兩半
- 那么最壞的情況下，復(fù)雜度將為n^2(數(shù)組本身就是有序的)
- 一般來(lái)說(shuō)復(fù)雜度都為nlogn漏健，如果擔(dān)心出現(xiàn)數(shù)組本身有序的情況嚎货，可以先將數(shù)組打亂再排序，當(dāng)然打亂程序的復(fù)雜度需要是O(n)或者O(nlogn)蔫浆。
