快速排序基本思想超詳細一看就懂

快速排序基本思想超詳細一看就懂快速排序算法是一種非常高效的排序算法，它采用“分而治之”的思想，將大的拆分為小的，小的拆分為更小的。如果說，希爾排序是直接插入排序的升級（插入類），堆排序是簡單選擇排序的升級（選擇類），那么快速排序等于前面我們認為最慢的冒泡排序的升級（交換類）。快速排序算法是圖靈獲獎?wù)逿ony

Hoare

設(shè)計出來的，他在形式化方法理論以及ALGOL60編程語言發(fā)明中有卓越的貢獻，是上世紀(jì)最偉大的計算機科學(xué)家之一。而快速排序算法只是他眾多貢獻中的一個小發(fā)明而已。其原理如下：對于一組給定的記錄，通過一趟排序后，將原序列分為兩部分，其中前一部分的記錄均比后一部分的所有記錄小（有序）；然后再依次對前后兩部分的記錄進行快速排序，遞歸該過程，直到序列的所有記錄均有序為止。圖解快排算法思想結(jié)合圖例，快速排序的算法步驟大致如下：1、我們有一個數(shù)組：[2,1,7,9,5,8]2、分割1：按照快速排序的思想，首先把數(shù)組篩選成較小和較大的兩個子數(shù)組。選擇基準(zhǔn)值7，將原數(shù)組分割為兩個子數(shù)組：[2,1,5]和[7,9,8]3、分割2：針對兩個子數(shù)組：[2,1,5]和[7,9,8]，在較小的子數(shù)組里選2作為基準(zhǔn)值，在較大的子數(shù)組里選8作為基準(zhǔn)值，繼續(xù)分割子數(shù)組。基準(zhǔn)值2，[2,1,5]分割為：[1]和[2,5]基準(zhǔn)值8，[9,8]分割為：[8]和[9]4、分割3：繼續(xù)將元素個數(shù)大于1的子數(shù)組進行劃分，當(dāng)所有子數(shù)組里的元素個數(shù)都為1的時候，原始數(shù)組也被排好序了?；鶞?zhǔn)值2，[2,5]分割為：[2]和[5]基準(zhǔn)值8，[9,8]分割為：[8]和[9]5、分割結(jié)果，所有子數(shù)組的元素個數(shù)都為1，得到結(jié)果數(shù)組：我們從上面可以總結(jié)出規(guī)律，在實行分治過程中，如何選擇基準(zhǔn)值并拆分數(shù)組是難點。拆分算法是整個快速排序中的核心，快速排序擁有非常多的拆分方式，其中廣泛使用的是單指針遍歷法與雙指針遍歷法。篇幅所限，我們這里對面試常常問的雙指針遍歷算法進行圖解剖析?？焖倥判蛩惴ㄖp指針遍歷實現(xiàn)圖解快速排序算法之雙指針遍歷實現(xiàn)圖解：1、首先，我們得到一個初始數(shù)組：[2,1,7,9,5,8]2、進行第1次樞軸挑選，得到樞軸元素下標(biāo)=13、根據(jù)第1次樞軸挑選結(jié)果，進行遞歸處理4、遞歸1：左邊數(shù)組5、遞歸1：右邊數(shù)組6、進行第2次樞軸挑選，得到樞軸元素下標(biāo)=37、根據(jù)第2次樞軸挑選結(jié)果，進行遞歸處理8、遞歸2：右邊數(shù)組9、遞歸2：左邊數(shù)組10、進行第3次樞軸挑選，得到樞軸元素下標(biāo)=511、此時，我們完成對數(shù)組的快速排序，得到順序數(shù)組輸出：[1,2,5,7,8,9]快速排序算法之雙指針遍歷實現(xiàn)代碼下面是快速排序的算法實現(xiàn)：publicclassQuickSort{publicstaticvoidmain(String[]args){int[]array={2,1,7,9,5,8};QSort(array,0,5);System.out.println(Arrays.toString(array));}

privatestaticvoidQSort(int[]nums,intlow,inthigh){intpivot;if(low>=high){return;}//難點也是核心，partition函數(shù)工作內(nèi)容：選取某個中樞元素（樞軸,pivot），然后想辦法將它放到某一位置，//使得它左邊的值都小于它，右邊的值都大于它。pivot=partition(nums,low,high);//分解為更小的問題，遞歸QSort(nums,low,pivot-1);QSort(nums,pivot+1,high);}

/***<p>*1、交換順序表nums的記錄，使得樞軸到位，并返回所在位置*2、確保樞軸左邊元素<樞軸，樞軸右邊元素>樞軸*3、選取樞軸策略就是元素的中位數(shù)的下標(biāo)。*/privatestaticintpartition(int[]nums,intlow,inthigh){intpivotKey=nums[low];while(low<high){while(low<high&&nums[high]>=pivotKey){//findouttheelementwhichissmallerthenpivotKeyhigh--;}

//一次遍歷，找到比基準(zhǔn)值更小的元素并排序到前面swap(nums,low,high);while(low<high&&nums[low]<=pivotKey){//findouttheelementwhichisbiggerthenpivotKeylow++;}

//一次遍歷，找到比基準(zhǔn)值更大的元素并排序到后面swap(nums,low,high);}returnlow;}

staticvoidswap(int[]nums,inti,intj){inttmp=nums[i];nums[i]=nums[j];nums[j]=tmp;}}輸出：[1,2,5,7,8,9]快排復(fù)雜度分析我們來分析下快速排序算法的性能：快速排序的時間復(fù)雜度取決于快速排序遞歸的深度，在最優(yōu)情況下，快速排序算法的時間復(fù)雜度為O(nlogn)。在最壞情況下，待排序序列為正序或者逆序，每次劃分只得到一個比上次少一個記錄的子序列（另一個為空），最終時間復(fù)雜度為O(n^2)。由數(shù)學(xué)歸納法，其數(shù)量級為O(nlogn)?？焖倥判虻目臻g復(fù)雜度主要是遞歸造成的?？臻g的使用，最好情況，遞歸樹的深度為logn，那么它的空間復(fù)雜度也是O(logn)。最壞情況，要進行n-1次遞歸調(diào)用，那么空間復(fù)雜度就是O(n)。平均情況，空間復(fù)雜度為O(logn)。由于關(guān)鍵字的比較和交換是跳躍進行的，因此快速排序是不穩(wěn)定的排序方法?？偨Y(jié)

遞歸排序算法，還是有不少值得優(yōu)化的地方：1、優(yōu)化選取樞軸：采用三數(shù)取中法（median-of-three），即取是哪個關(guān)鍵字先進行排序，將中間數(shù)作為樞軸，一般使用左端、右端和中間三個數(shù)，或者隨機選取?；蛘卟捎镁艛?shù)取中（medina-of-nine），從數(shù)組中三次取樣每次三個，基于樣品取中數(shù)，然后從三個中數(shù)再取中數(shù)作為樞軸。2、優(yōu)化不必要的交換3、優(yōu)化小數(shù)組時的排序方案如果