算法思想
取待排序元素的區間端點作為作為界值,然後通過交換使得待排序元素中所有大于界值的元素位于界值的一側,
所有小于界值的元素位于界值的另一側,然後在對界值左右兩側的待排序元素使用同樣的方法進行排序,直到下一
次待排序區間隻有一個元素時,則表示所有的元素排序完成,可以看出這種排序方式使用了分而治之的思想,個人
感覺快速排序是一種"折半排序";
下面以升序排序{4,5,8,2,3,9,7,1}這個待排序序列,圖示如何根據界值進行劃分:
開始狀态如下:
劃分過程如下:
元素5比元素4大是以不需要交換,j指向下一個元素,此時狀态如下:
元素8比元素4大所有不需要交換,j指向下一個元素,此時狀态如下:
2比4小,是以需要和下标為i+1的元素進行交換,也就是和下标為1的元素交換,然後j指向下一個元素,
此時狀态如下:
3比4小,是以需要和下标為i+1的元素進行交換,也就是和下标為2的元素交換,然後j指向下一個元素,
接着是9比4大,無需交換,然後j指向下一個元素,此時狀态如下:
接着是7比4大,無需交換,然後j指向下一個元素,此時狀态如下:
1比4小,是以需要和下标為i+1的元素進行交換,也就是和下标為3的元素交換,然後j指向下一個元素,
此時j指向數組尾部,數組的元素分為兩部分,一部分是比4大的,一部分是比4小的,将界值4和目前i所指元素進行
交換即可使,界值左側的元素都小于4，,右側元素都大于4:
對界值4左右兩側的元素分别進行上述操作,知道最後一次劃分時,待排序區間隻有一個元素時,此時整體已經是有
序的了
代碼實作
int Partition(int * pPartOfUnSort, const int nStart, const int nEnd)
{
int iIndex = nStart;
int jIndex = nStart + 1;
int nTemp = 0;
for (; jIndex <= nEnd; jIndex++)
{
if (pPartOfUnSort[jIndex] < pPartOfUnSort[nStart])
{
iIndex++;
nTemp = pPartOfUnSort[iIndex];
pPartOfUnSort[iIndex] = pPartOfUnSort[jIndex];
pPartOfUnSort[jIndex] = nTemp;
}
}
nTemp = pPartOfUnSort[nStart];
pPartOfUnSort[nStart] = pPartOfUnSort[iIndex];
pPartOfUnSort[iIndex] = nTemp;
return iIndex;
}
void QuickSort(int * pUnSortAry, const int nStart, const int nEnd)
{
if (nStart > nEnd)
{
return;
}
int nIndexOfPivot = 0;
nIndexOfPivot = Partition(pUnSortAry, nStart, nEnd);
QuickSort(pUnSortAry, nStart, nIndexOfPivot - 1);
QuickSort(pUnSortAry, nIndexOfPivot + 1, nEnd);
}
時空複雜度分析
-
最差情況下的時間複雜度
當選取的界值是待排序中最大或者最小的數值時,那麼這次的劃分将會比較低效,因為所有元素都排在了界值的一
側,如果待排序元素已經是有序的,或者是逆序的,或是差不多有序的,或者是差不多逆序的時,每次進行劃分時,界
值隻有一側有資料,這種情況下快速排序效率較低,Partition函數的整體時間複雜度為Θ(n),QuickSort是一個遞
歸函數,在這種最差情況下,所有遊元素都排在了界值的一側,是以QuickSort内部的兩個遞歸函數隻有一個進行了
Partition函數中的for循環,另一個遞歸調用直接就傳回了,是以其時間複雜度為T(0),是以在這種糟糕情況下,
QuickSort整體時間複雜度為:
T(n)=T(0)+T(n-1)+Θ(n)=T(n-1)+O(n)=O(n^2)
-
最好情況下的時間複雜度
當選取的界值劃分後,界值左右兩側的元素個數差不多時,快速排序效率較高,此時QuickSort内部的兩個遞歸函數
調用的時間複雜度均為T(n/2),此時快速排序的時間複雜度為:
T(n)=2T(n/2)+Θ(n)=nlgn
穩定性
因為快速排序的一次劃分的過程中,最後一次是将界值和界值所在區間的另一端的元素交換,可能會造成相同元素
的相對位置發生改變是以,快速排序是不穩定的