/**
*快速排序算法的應用
快速排序算法比冒泡排序算法的效率更高，它每次都要確定第一個下標數字的位置，流程圖如下所示：（P152）
本例應用到的知識如下：
（1）。數組的創建
（2）。數組的訪問
（3）。快速排序算法
*/
public class QuickSort
{
/**主方法*/
public static void main(String[] args)
{
int[] nums = {27,8,57,9,23,41,65,19,0,1,2,4,5};//聲明一維數組并初始化
System.out.println("該數組的長度為：" + nums.length);
System.out.println("*************************************************");
quickSort(nums,0,nums.length-1);//應用快速排序算法
System.out.println("*************************************************");
System.out.println("已經走出quickSort方法，并且下面在主程序中顯示最后結果");
for(int i = 0; i < nums.length; i++)//顯示排序后的數組
{
System.out.print(nums[i] + ",");
}
}
/**快速排序算法*/
public static void quickSort(int[] a,int low0, int hig0)//實參為quickSort(nums, 0, 12)
{
int low=low0;//low0 = 0
int hig=hig0;//hig0 = 12
if(low >= hig)//條件成立時表示已經排序完畢
return;
//transfer是確定指針方向的邏輯變量
boolean transfer = true;//默認是下標指針從后向前移動
while(low != hig)
{
if(a[low] > a[hig])
{
//交換數字
int temp = a[low];
a[low] = a[hig];
a[hig] = temp;
//決定下標移動，還是上標移動
transfer = (transfer == true) ? false : true;//這里第一次求的transfer為false
}
//將指針向前或者后移動
if(transfer)
{hig--;}//指針向前移動
else
{low++;}//指針向后移動
//顯示每一次指針移動的數組數字的變化
for(int i = 0; i < a.length; i++)
{
System.out.print(a[i] + ",");
}
System.out.print(transfer + ",");
//此時low = 1, hig = 12
System.out.println(" (low,hig) =" + "(" + low + "," + hig + ")");
}//退出while循環時low == high == 9
//將數組分開兩半重新調用quickSort()各自快速排序，確定每個數字的正確位置
low--;//low == 8
hig++;// hig == 10
quickSort(a, low0, low);//quickSort(a, 0, 8)
quickSort(a, hig, hig0);//quickSort(a, 10,12)
}
}
//運行結果如下:
E:\java\ProgramJava\35lessons\lesson8>javac QuickSort.java
E:\java\ProgramJava\35lessons\lesson8>java QuickSort
該數組的長度為：13
*************************************************
5,8,57,9,23,41,65,19,0,1,2,4,27,false, (low,hig) =(1,12)
5,8,57,9,23,41,65,19,0,1,2,4,27,false, (low,hig) =(2,12)
5,8,27,9,23,41,65,19,0,1,2,4,57,true, (low,hig) =(2,11)
5,8,4,9,23,41,65,19,0,1,2,27,57,false, (low,hig) =(3,11)
5,8,4,9,23,41,65,19,0,1,2,27,57,false, (low,hig) =(4,11)
5,8,4,9,23,41,65,19,0,1,2,27,57,false, (low,hig) =(5,11)
5,8,4,9,23,27,65,19,0,1,2,41,57,true, (low,hig) =(5,10)
5,8,4,9,23,2,65,19,0,1,27,41,57,false, (low,hig) =(6,10)
5,8,4,9,23,2,27,19,0,1,65,41,57,true, (low,hig) =(6,9)
5,8,4,9,23,2,1,19,0,27,65,41,57,false, (low,hig) =(7,9)
5,8,4,9,23,2,1,19,0,27,65,41,57,false, (low,hig) =(8,9)
5,8,4,9,23,2,1,19,0,27,65,41,57,false, (low,hig) =(9,9)
0,8,4,9,23,2,1,19,5,27,65,41,57,false, (low,hig) =(1,8)
0,5,4,9,23,2,1,19,8,27,65,41,57,true, (low,hig) =(1,7)
0,5,4,9,23,2,1,19,8,27,65,41,57,true, (low,hig) =(1,6)
0,1,4,9,23,2,5,19,8,27,65,41,57,false, (low,hig) =(2,6)
0,1,4,9,23,2,5,19,8,27,65,41,57,false, (low,hig) =(3,6)
0,1,4,5,23,2,9,19,8,27,65,41,57,true, (low,hig) =(3,5)
0,1,4,2,23,5,9,19,8,27,65,41,57,false, (low,hig) =(4,5)
0,1,4,2,5,23,9,19,8,27,65,41,57,true, (low,hig) =(4,4)
0,1,4,2,5,23,9,19,8,27,65,41,57,true, (low,hig) =(0,2)
0,1,4,2,5,23,9,19,8,27,65,41,57,true, (low,hig) =(0,1)
0,1,4,2,5,23,9,19,8,27,65,41,57,true, (low,hig) =(0,0)
0,1,4,2,5,23,9,19,8,27,65,41,57,true, (low,hig) =(1,2)
0,1,4,2,5,23,9,19,8,27,65,41,57,true, (low,hig) =(1,1)
0,1,2,4,5,23,9,19,8,27,65,41,57,false, (low,hig) =(3,3)
0,1,2,4,5,8,9,19,23,27,65,41,57,false, (low,hig) =(6,8)
0,1,2,4,5,8,9,19,23,27,65,41,57,false, (low,hig) =(7,8)
0,1,2,4,5,8,9,19,23,27,65,41,57,false, (low,hig) =(8,8)
0,1,2,4,5,8,9,19,23,27,65,41,57,true, (low,hig) =(5,6)
0,1,2,4,5,8,9,19,23,27,65,41,57,true, (low,hig) =(5,5)
0,1,2,4,5,8,9,19,23,27,65,41,57,true, (low,hig) =(6,6)
0,1,2,4,5,8,9,19,23,27,57,41,65,false, (low,hig) =(11,12)
0,1,2,4,5,8,9,19,23,27,57,41,65,false, (low,hig) =(12,12)
0,1,2,4,5,8,9,19,23,27,41,57,65,false, (low,hig) =(11,11)
*************************************************
已經走出quickSort方法，并且下面在主程序中顯示最后結果
0,1,2,4,5,8,9,19,23,27,41,57,65,
posted on 2006-02-04 19:19
★yesjoy★ 閱讀(1722)
評論(0) 編輯 收藏 所屬分類:
算法總結