/**
*快速排序算法的应用
快速排序算法比冒泡排序算法的效率更高，它每次都要确定第一个下标数字的位置，流程图如下所示：（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★ 阅读(1715)
评论(0) 编辑 收藏 所属分类:
算法总结