圖解Java經(jīng)典算法快速排序的原理與實現(xiàn)

第圖解Java經(jīng)典算法快速排序的原理與實現(xiàn)目錄快速排序算法原理圖解Java代碼實現(xiàn)算法分析

快速排序

通過一趟排序?qū)⒋旁胤殖瑟毩⒌膬刹糠?，其中一部分為比基?zhǔn)數(shù)小的元素，另一部分則是比基準(zhǔn)數(shù)大的元素。然后對這兩部分元素再按照前面的算法進(jìn)行排序，直到每一部分的元素都只剩下一個。

本質(zhì)上來看，快速排序應(yīng)該算是在冒泡排序基礎(chǔ)上的遞歸分治法。

算法原理

從數(shù)列中挑出一個元素作為基準(zhǔn)點重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面然后基準(zhǔn)值左右兩邊，重復(fù)上述步驟通過遞歸把基準(zhǔn)值元素左右兩側(cè)的數(shù)組排序，排完之后，整個數(shù)組就排序完成了

圖解

問題描述：

給定一個無序排列的數(shù)組nums，使其能夠按照有序輸出

示例：

輸入:nums=[4，3，1，2，9，6],

輸出:nums=[1，2，3，4，6，9]

圖解如下：

Java代碼實現(xiàn)

核心代碼

publicclassQuickSort{

//比較v是否小于w

publicstaticbooleanless(Comparablev,Comparablew){

returnpareTo(w)

//數(shù)組元素交換位置

privatestaticvoidswap(Comparable[]a,inti,intj){

Comparabletemp;

temp=a[i];

a[i]=a[j];

a[j]=temp;

//排序

publicstaticvoidsort(Comparable[]a){

intl=0;

inth=a.length-1;

sort(a,l,h);

privatestaticvoidsort(Comparable[]a,intl,inth){

if(h=l)return;

//對數(shù)組進(jìn)行分組(左右兩個數(shù)組)

//i表示分組之后基準(zhǔn)值的索引

inti=partition(a,l,h);

//讓左邊的數(shù)組有序

sort(a,l,i-1);

//讓有邊的數(shù)組有序

sort(a,i+1,h);

publicstaticintpartition(Comparable[]a,intl,inth){

//確定基準(zhǔn)值

Comparablekey=a[l];

//定義兩個指針

intleft=l;

intright=h+1;

//切分

while(true){

//從右向左掃描，移動right指針找一個比基準(zhǔn)值小的元素，找到就停止

while(less(key,a[--right])){

if(right==l)

break;

//從左向右掃描，移動left指針找一個比基準(zhǔn)值大的元素，找到就停止

while(less(a[++left],key)){

if(left==h)

break;

if(left=right){

break;

}else{

swap(a,left,right);

//交換基準(zhǔn)值

swap(a,l,right);

returnright;

}

publicclassQuickSortTest{

publicstaticvoidmain(String[]args){

Integer[]arr={3,1,2,4,9,6};

QuickSort.sort(arr);

System.out.println(Arrays.toString(arr));

//排序前：{3,1,2,4,9,6}

//排序后：{1,2,3,4,6,9}

運行結(jié)果：

算法分析

時間復(fù)雜度

快速排序的最佳情況就是每一次取到的元素都剛好平分整個數(shù)組，由于快速排序用到了遞歸調(diào)用，因此計算其時間復(fù)雜度也需要用到遞歸算法來計算。T[n]=2T[n/2]+f(n)；此時時間復(fù)雜度是O(nlogn)。最壞的情況，則和冒泡排序一樣，每次比較都需要交換元素，此時時間復(fù)雜度是O(n^2)。

因此，快速排序的時間復(fù)雜度為：O(nlogn)。

空間復(fù)雜度

空間復(fù)雜度主要是遞歸造成