快速排序
簡介
快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort），一種排序算法，最早由東尼·霍爾提出。
快速排序也屬于比較排序中的一種，用到了分治的思想，綜合來看快速排序是最常用的一種排序算法，速度快，效率高。
快速排序的描述
下面以對數(shù)組A[p...r]進行排序，來描述快速排序是如何利用分治思想進行快速排序的。
- 分解：數(shù)組A[p...r]被劃分為兩個(可能為空)的子數(shù)組A[p...q-1]和A[q+1,r]使得A[p..q-1]中每一個元素均小于或等于A[q] 而A[q+1...r]中每一個元素均大于等于A[q]. 劃分的過程確定A[q]也是劃分過程比較重要的部分，這里一般是選擇最后一個元素為基準元素，然后遍歷一遍數(shù)組，遍歷過程中將每個元素與基準元素進行大小比較通過交換元素位置，最終在遍歷完成時實現(xiàn)數(shù)組中基準元素左側(cè)均小于它而它右側(cè)的元素均大于它。(該過程可以結(jié)合看后面的偽代碼以及代碼實現(xiàn)能夠更好的理解，基準元素也像一個哨兵的作用類似)
- 解決： 通過遞歸調(diào)用快速排序，對數(shù)組A[p...q-1]和A[q+1...r]進行排序 (該過程就是對劃分的子數(shù)組再遞歸進行劃分最終子數(shù)組為空或只有一個元素為止)
- 合并 因為子數(shù)組都是原址排序的，所以不需要合并操作 數(shù)組A[p...r]已經(jīng)是有序的了(由于通過遞歸劃分子數(shù)組，最終的每個子數(shù)組都是一個元素或為空，另外通過劃分過程我們知道 相鄰數(shù)組之間的元素是有序的比如左邊數(shù)組的所有元素 均不大于右邊數(shù)組里的元素 因此最終整個數(shù)組是有序的就完成了排序過程)
快速排序偽代碼
QUICKSORT(A,p,r)
- if(p<r)
- q = PARTITION(A,p,r)
- QUICKSORT(A,p,q-1)
- QUICKSORT(A,q+1,r)
PARTITION(A,p,r)
- x = A[r]
- i = p-1
- for(j = p to r-1)
- if(A[j] <= x)
- i++;
- exchange(A[i],A[j])
- exchange(A[i+1], A[r]
- return i+1;
快速排序算法時間復雜度以及空間復雜度分析
空間復雜度
由以上快排描述以及偽代碼可知，除了定義了想x,i,j三個臨時變量用來遍歷調(diào)整交換原數(shù)組的元素位置以達到劃分。因此空間復雜度很簡單就是O(1).時間復雜度
由以上的偽代碼可知快速排序 主要是遍歷劃分 和遞歸。先看看最差的情況假設選取的基準比較元素就是最小的那么每次劃分的兩個子數(shù)組 一個為空一個為剩余的元素 這樣相當于要遞歸 遍歷n次因此快速排序性能最差的情況下時間復雜度為O(n2), 最理想以及一般情況在遞歸劃分時兩個子數(shù)組劃分均勻時 快排時間復雜度為O(nlgn)。在實際場景中 快速排序的時間復雜度接近O(nlgn).
End Talk Is Cheap Show You Mine Code
void quickSort(int *array, int start, int end) {
if (arraySize == 0) {
arraySize = end + 1;
}
if(start >= end){
return;
}
logoutArray(array);
int i = partition(array,start,end);
quickSort(array,start, i-1);
quickSort(array,i+1,end);
}
int partition(int * array, int start , int end){
int i , j ,tmp;
i = start;
j = end;
while(i != j){
while(array[j] >= array[start] && i < j){
j--;
}
while(array[i] <= array[start] && i < j){
i++;
}
if(i < j){
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
}
tmp = array[start];
array[start] = array[i];
array[i] = tmp;
return i;
}
