快速排序示範-從小到大 關鍵操作“記錄下標,使用遞迴”
快速排序分析:關於陣列下標的操作問題,一定要注意條件迴圈變數的初始值設定以及迴圈結束條件的判定,注意條件結構的多變數控制,有時候這很繞,比較吃熟練度,所以要多訓練。才能使迴圈有效,避免陣列越界等問題出現。
快速排序的一趟操作效果(方法體)是:1.把傳入陣列分成三部分,第一部分是一個子陣列(傳入陣列的一部分呵),第二部分是一個數,第三部分還是一個子陣列,這個數叫做中間數,既然這麼個叫法,那麼你肯定能理解中間數的左邊陣列也就是第一部分的所有陣列元素都是小於或者等於這個中間數的,第二部分的所有陣列元素都大於等於這個中間數的。2.接著分別讓第一部分和第三部分子陣列作為新的傳入陣列分別呼叫方法本身,即使用遞迴。這個遞迴結束的標誌呢,就是當傳入的陣列是個單元素陣列(陣列只包含一個元素,當然就不需要排序了啊)的時候就停止了,這樣一來原來的陣列元素已經全部排序完畢。
我個人程式碼實現,註釋說明:
public class QuickSort {
public static void quickSort(int[] array,int startIndex,int endIndex) {//準備傳入 陣列,首元素下標,尾元素下標
if(startIndex<endIndex) {//單元素陣列就停止操作,因為不需要排序
int LR=startIndex+1,RL=endIndex;//記錄陣列元素下標的兩個變數
while(true) {
for(int i=startIndex+1;i<=endIndex;i++) {//記錄從左到右第一個大於等於首元素的下標
if(array[i]>=array[startIndex]) {
LR=i;
break;
}
LR++;
}
for(int j=endIndex;j>=startIndex+1;j--) {//記錄從右到左第一個小於等於首元素的下標
if(array[j]<=array[startIndex]) {
RL=j;
break;
}
RL--;
}
if(LR<RL) {//若記錄大於等於首元素的下標值 小於 記錄小於等於首元素的下標值 那麼這兩個下標代表的元素值交換,接著迴圈
int temp=array[LR];
array[LR]=array[RL];
array[RL]=temp;
}else {
break;
}
}
if(LR>=RL) {//若記錄大於等於首元素的下標值 大於 記錄小於等於首元素的下標值 那麼將記錄小於等於首元素的下標代表的元素值與首元素值交換
int temp=array[RL];//,此時首元素值變成中間數,中間數左邊是一子陣列,右邊是另一子陣列
array[RL]=array[startIndex];
array[startIndex]=temp;
quickSort(array,startIndex,RL-1);//中間數左子陣列(用三個傳入引數表示)作為引數呼叫方法本身,即使用遞迴
quickSort(array,RL+1,endIndex);//中間數右子陣列(用三個傳入引數表示)作為引數呼叫方法本身,即使用遞迴
}
}
}
public static void main(String[] args) {
int[] array= {26,17,5,33,87,53,27,49,28,78}; // TODO Auto-generated method stub
System.out.println("排序前:");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
System.out.println();
quickSort(array,0,array.length-1);
System.out.println("排序後:");
for(int i=0;i<array.length;i++)
System.out.print(array[i]+" ");
}
}
執行結果:
排序前:
26 17 5 33 87 53 27 49 28 78
排序後:
5 17 26 27 28 33 49 53 78 87