快速排序讓我看了很久，也折磨了我很長時間，因為大體上的思路我是有了，但是寫代碼時總是出現各種問題，要想把它調試出來對我個人來說還是有一定難度的，而且因為工作和偷懶的原因，導緻之前調試不出來的錯誤放了很久，今天終于出來啦，還是有些小激動的哦，下面來分享一下我的代碼并做一點點說明。
要學會快速排序，就必須先要學會分治法，分治的思想是給一串亂序的數字(數字是假設，也可以是其他的對象，當然方法的參數可以自己定義哦，我在這裡假設有一個整型的數組吧)然後給他一個中間數，分治法會把這些數字以給他的那個是中間數為分界分為兩部分，一部分在中間數的左邊，另一部分在右邊，以這個數為分界點，兩邊的數現在還是亂序的，我給他定義的方法如下：
//left是數組的想分治部分的左端點，right是數組分治部分的總端點，如長度為10的數組，我想對前5個整數進行分治，則傳0，4即可
public int signalFenZhi(int left,int right){
if(left<0||left>n-1||right<0||right>n-1){
return -1;
}
int temp = test[left];
int j=right;
int i=left;
while(i
while(test[j]>=test[left]&&i
j--;
}
while(test[i]<=test[left]&&i
i++;
}
if(i
temp = test[i];
test[i]=test[j];
test[j]=temp;
}
}
if(i==j){
temp = test[i];
test[i]=test[left];
test[left]=temp;
}
for(int m=0;m
System.out.print(test[m]+" ");
}
return i;
}
當然，也可以把那個中間數當參數傳進來，現在我隻是單純的以數組的傳進來的第left數做為分界數，這隻是為了說明。
明白了分治，那麼快速排序也就簡單了，那就是對已經分為兩部分的數再進行分治，依次類推，直到全部的數字都有序為止，代碼如下：
public void quickSort(int left,int right){
if(right-left<1){
return ;
}else{
int point = this.signalFenZhi(left, right);
System.out.println(point);
//if(point!=left&&point!=right){
quickSort(left,point-1);
quickSort(point+1,right);
//}
}
}
快速排序的效率在衆多的排序算法中是很優秀的，時間複雜度為O(N*log2n),但是如果分治的分界點選的不好的話，時間複雜度将會降到(n的平方),因為如果正好這個數組是有序的，然後我們每次都取傳過來的最左端的數，那麼效率就會很低，是以要避免發生這種情況，如果檢測所有的選項，那麼将會很花時間，是以一個折中的辦法 ，就是把最左端的數和最右端的數加上一個中間的數，找到他們三個中間的數，以這個為分界值就會變的好一點，在上面方法的基礎上，修改以後的代碼如下，但是我做完了以後這樣的做法不是很好，應該把分界值也當做傳給分治的方法會好些，細心的朋友可以自己試一下，我在這裡就不試了哈，大體上是一樣的哦！
package com.jll;
public class FenZhi {
int[] test;
int n=10;
public FenZhi(){
test = new int[10];
for(int i=0;i
test[i]=(int)(Math.random()*100)+1;
System.out.print(test[i]+" ");
}
System.out.println();
}
public FenZhi(int n){
if(n>0){
this.n=n;
test = new int[n];
for(int i=0;i
test[i]=(int)(Math.random()*100)+1;
}
}
}
public int signalFenZhiMajorizationFirst(int left,int right){
if(left<0||left>n-1||right<0||right>n-1||left>=right){
return -1;
}
if(right-left>=2){
int middle = (right+left)/2;
if(test[left]>test[middle]){
int temp = test[middle];
test[middle] = test[left];
test[left] = temp;
}
if(test[left]>test[right]){
int temp = test[left];
test[left] = test[right];
test[right] = temp;
}
if(test[middle]>test[right]){
int temp = test[middle];
test[middle] = test[right];
test[right] = temp;
}
int temp = test[middle];
test[middle] = test[left];
test[left] = temp;
int j=right-1;
int i=left+1;
while(i
while(test[j]>=test[left]&&i
j--;
}
while(test[i]<=test[left]&&i
i++;
}
if(i
temp = test[i];
test[i]=test[j];
test[j]=temp;
}
}
if(i==j){
temp = test[i];
test[i]=test[left];
test[left]=temp;
}
return i;
}else {
if(test[right]
int temp = test[right];
test[right] = test[left];
test[left] = temp;
}
return right;
}
}
public void quickSortMajorizationFirst(int left,int right){
if(right-left<1){
return ;
}else{
int point = this.signalFenZhiMajorizationFirst(left, right);
System.out.println("the point is:"+point);
quickSortMajorizationFirst(left,point-1);
quickSortMajorizationFirst(point+1,right);
}
}
public static void main(String[] args) {
FenZhi f = new FenZhi();
System.out.println(f.signalFenZhiMajorizationFirst(0, 9));
System.out.println();
f.quickSortMajorizationFirst(0,f.n-1);
//f.quickSort(0,f.test.length-1);
for(int i:f.test){
System.out.print(i+" ");
}
}
}
代碼運作如下：
95 40 64 18 78 23 73 84 40
the point is:4
the point is:1
the point is:3
the point is:7
the point is:6
the point is:9
18 23 40 40 64 73 78 84 95
以上就是我學習到的東西，記錄一下，以備後面查閱。