快速排序算法是常用的排序算法之一，一次偶然的機會我發(fā)現(xiàn)快速排序算法存在一些問題，開始我以為只是我的這版教材有問題，后來才發(fā)現(xiàn)網(wǎng)上所有的快速排序算法都是這樣的。
先來說說快速排序的思想吧
選取一個基準，把一個數(shù)組邏輯上分割成兩個，使用遞歸把數(shù)組一直細分，解釋的比較簡單，如果還不理解這個算法就去先學習下快速排序算法，今天我主要講的是它存在的問題
下面我寫一個目前所用的從大到小的快速排序的代碼（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("排序結果：");
? ? ? ? for(int i=0;i<5;i++)
? ? ? ? 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;
? ? if(i<j){
? ? temp=R[i];
? ? R[i]=R[j];
? ? R[j]=temp;
? ? }
}
if(R[j]>R[low]){
temp=R[low];
R[low]=R[j];
R[j]=temp;
}
if(i-low>1)
quickSort(R,low,i-1);
if(high-j>1)
quickSort(R,j+1,high);
? }
}
我們先試一組的數(shù)據(jù)?
結果沒問題我們再換一組數(shù)據(jù)測試
結果并沒有像我們想象的那樣，老師的答復是這是一個老算法應該不會存在錯誤的。我決定從算法的本質(zhì)入手苦思冥想了一天終于有了答案
第一輪比較我們發(fā)現(xiàn)base右邊的數(shù)都比base小所以一直移動j，一直到 i=j=low+1時就算比較完成，我們再用j指向的數(shù)100和base指向的120比較，發(fā)現(xiàn)不需要替換。
后面就到了分組遞歸環(huán)節(jié)了，理想狀態(tài)下每一組遞歸都會有一位數(shù)和基數(shù)base替換然后把替換位置左邊（low到i+1）的分成一個組，右邊（j+1到high）的分成一個組，i和j指向的那個數(shù)和基數(shù)替換我們視為有序就不參與下面的分組，
算法原本的意圖就是每次用基數(shù)比較，把比基數(shù)大的分成一組，比基數(shù)小的分成一組，基數(shù)的順序就排好了就可以固定在這個位置不用參與下面的分組。
算法每一次比較i和j指向的那個數(shù)位置固定，當出現(xiàn)極端情況時就會出現(xiàn)致命錯誤
當右邊所有的數(shù)都比基數(shù)小時，base不需要與i和j指向的數(shù)替換位置，應該固定的位置應該是基數(shù)本身所在的位置，而不是i和j指向的數(shù)100，但是算法卻錯誤的還是把i和j指向的那個數(shù)視為有序剔除了，不參與下面的排序，但100雖然比基數(shù)120小，但不一定會比100右邊的數(shù)大，所以這里就存在問題
問題到這就清楚了，快速排序中的每一組排序都需要固定一個數(shù)的位置，并把這個數(shù)左邊分成一組，右邊分成一組，這種思路是正確的，但是錯就錯在每次被固定的這個數(shù)到底應該是i和j指向的那個位置還是基數(shù)最終所在的位置，結果很顯然，因為排序就是按照基數(shù)排隊，基數(shù)在數(shù)組中的順序肯定是可以確定的，所以我們最終分組的標準應該是以基數(shù)最終所在位置為分組標準，
也就是以下兩種情況下圖圈圈所在的位置
也就是說當一輪比較之后發(fā)現(xiàn)基數(shù)的位置不需要替換時，我們應該以基數(shù)為準，將它的左右分組
解決辦法也就來了，按照一般的代碼編寫我們就忽略上圖的第一種情況，當基數(shù)位置不需要替換時怎么保證排序結果的正確
改正的代碼如下
在排序方法中交換基數(shù)位置語句前插入一個判斷，當基數(shù)不需要替換時就把i和j指向基數(shù)所在的位置
?if(i==low+1&&R[i]<R[low]){
?? ??? ??? ? ? i=low;
?? ??? ??? ? ? j=low;
??? }?
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;
? ? if(i<j){
? ? temp=R[i];
? ? R[i]=R[j];
? ? R[j]=temp;
? ? }
}
? ? ? ? if(i==low+1&&R[i]<R[low]){
? i=low;
? j=low;
}
if(R[j]>R[low]){
temp=R[low];
R[low]=R[j];
R[j]=temp;
}
if(i-low>1)
quickSort(R,low,i-1);
if(high-j>1)
quickSort(R,j+1,high);
? }
我們再測試一下剛才的那組數(shù)據(jù)，結果正確
當然還有另外一種不是很好的解決辦法，就是分組的時候把i和j指向的那個位置劃分到某一個組中重新參與排序，不過這樣會造成資源浪費，我們只希望它在基數(shù)不需要改變位置的時候把i和j指向的位置放到數(shù)組中重新排序，當基數(shù)位置每次都需要交換時也就是我們理想的情況時就不會出現(xiàn)這種錯誤。
代碼如下
把quickSort(R,j+1,high);改成了quickSort(R,j,high);
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;
? ? if(i<j){
? ? temp=R[i];
? ? R[i]=R[j];
? ? R[j]=temp;
? ? }
}
if(R[j]>R[low]){
temp=R[low];
R[low]=R[j];
R[j]=temp;
}
if(i-low>1)
quickSort(R,low,i-1);
if(high-j>1)
quickSort(R,j,high);
? }
測試結果正確
小編整理了一些java進階學習資料和面試題，需要資料的請加JAVA高階學習Q群：701136382 這是小編創(chuàng)建的java高階學習交流群，加群一起交流學習深造。群里也有小編整理的2019年最新最全的java高階學習資料！
