快速排序算法真的正确嗎？-試試120，100，105，103，118 從大到小排列

快速排序算法是常用的排序算法之一，一次偶然的機會我發現快速排序算法存在一些問題，開始我以為隻是我的這版教材有問題，後來才發現網上所有的快速排序算法都是這樣的。

先來說說快速排序的思想吧

選取一個基準，把一個數組邏輯上分割成兩個，使用遞歸把數組一直細分，解釋的比較簡單，如果還不了解這個算法就去先學習下快速排序算法，今天我主要講的是它存在的問題

下面我寫一個目前所用的從大到小的快速排序的代碼（java版）

測試類

public class Test{

public static void main(String[] args){

Scanner read=new Scanner(System.in);

System.out.println("請輸入測試5用例:");

int[] data=new int[5];

for(int i=0;i<5;i++)

data[i]=read.nextInt();

quickSort(data,0,4);

System.out.println("排序結果：");

System.out.print(data[i]+" ");

System.out.println();

}

public static void quickSort(int[] R,int low,int high){

int base=R[low];

int i=low+1;

int j=high;

int temp=0;

while(i<j){

while((i<j)&&(R[j]<=base))

--j;

while((i<j)&&(R[i]>=base))

++i;

我們先試一組的資料 

結果沒問題我們再換一組資料測試

結果并沒有像我們想象的那樣，老師的答複是這是一個老算法應該不會存在錯誤的。我決定從算法的本質入手苦思冥想了一天終于有了答案

第一輪比較我們發現base右邊的數都比base小是以一直移動j，一直到 i=j=low+1時就算比較完成，我們再用j指向的數100和base指向的120比較，發現不需要替換。

後面就到了分組遞歸環節了，理想狀态下每一組遞歸都會有一位數和基數base替換然後把替換位置左邊（low到i+1）的分成一個組，右邊（j+1到high）的分成一個組，i和j指向的那個數和基數替換我們視為有序就不參與下面的分組，

算法原本的意圖就是每次用基數比較，把比基數大的分成一組，比基數小的分成一組，基數的順序就排好了就可以固定在這個位置不用參與下面的分組。

算法每一次比較i和j指向的那個數位置固定，當出現極端情況時就會出現緻命錯誤

當右邊所有的數都比基數小時，base不需要與i和j指向的數替換位置，應該固定的位置應該是基數本身所在的位置，而不是i和j指向的數100，但是算法卻錯誤的還是把i和j指向的那個數視為有序剔除了，不參與下面的排序，但100雖然比基數120小，但不一定會比100右邊的數大，是以這裡就存在問題

問題到這就清楚了，快速排序中的每一組排序都需要固定一個數的位置，并把這個數左邊分成一組，右邊分成一組，這種思路是正确的，但是錯就錯在每次被固定的這個數到底應該是i和j指向的那個位置還是基數最終所在的位置，結果很顯然，因為排序就是按照基數排隊，基數在數組中的順序肯定是可以确定的，是以我們最終分組的标準應該是以基數最終所在位置為分組标準，

也就是以下兩種情況下圖圈圈所在的位置

也就是說當一輪比較之後發現基數的位置不需要替換時，我們應該以基數為準，将它的左右分組

解決辦法也就來了，按照一般的代碼編寫我們就忽略上圖的第一種情況，當基數位置不需要替換時怎麼保證排序結果的正确

改正的代碼如下

在排序方法中交換基數位置語句前插入一個判斷，當基數不需要替換時就把i和j指向基數所在的位置

 if(i==low+1&&R[i]<R[low]){

               i=low;

               j=low;

    } 

我們再測試一下剛才的那組資料，結果正确

當然還有另外一種不是很好的解決辦法，就是分組的時候把i和j指向的那個位置劃分到某一個組中重新參與排序，不過這樣會造成資源浪費，我們隻希望它在基數不需要改變位置的時候把i和j指向的位置放到數組中重新排序，當基數位置每次都需要交換時也就是我們理想的情況時就不會出現這種錯誤。

代碼如下

把quickSort(R,j+1,high);改成了quickSort(R,j,high);

測試結果正确

小編整理了一些java進階學習資料和面試題，需要資料的請加JAVA高階學習Q群：701136382 這是小編建立的java高階學習交流群，加群一起交流學習深造。群裡也有小編整理的2019年最新最全的java高階學習資料！