快速排序 - 黑马程序员技术交流社区

/*快速排序基本思想；使用快速排序方法对a[0,n-1]排序，从a[0,n-1]中排序选择一个元素作为Middle，该元素为中点(支点)，把剩余的元素分割为两段--left和right。。
*/
class Sample5{
private double[] theArry;//对象私有属性
private int nElems;//记录数组长度
//----------------------------------
public Sample5(int max){//构造函数
theArry =new double[max];//创建数组
nElems=0;//开始数组长度为0
}
//------------------------------
public void insert(double value){//将元素插入数组
theArry[nElems]=value;
nElems++;
}
//------------------------------------
public void dispaly(){//打印数组
System.out.print("A=");
for(int j=0;j<nElems;j++)
System.out.print(theArry[j]+" ");
System.out.print(" ");
}
//------------------------------------------
public void quickSort(){//执行快速排序算法
recQuickSort(0,nElems-1);
}
//快速算法核心部分，设定左下标和右下标
public void recQuickSort(int left,int right){
if(right-left<=0)
//若right<=left .表明排序结束
return;
else
{
double pivot=theArry[right];//获取最右元素值
//以最右的元素为轴，划分左右范围
int partition =partitionIt(left,right,double pivot);
recQuickSort(left,partition-1);//对partition左边的元素进行排序
recQuickSort(partition+1,right);//对partition右边的元素进行排序
}
}
//总体思想：找到最左边pivot大的元素，最右边比pivot小的元素，交换这两个元素
//循环进行以上工作，直至左右下标重叠
public int partitionIt(int left,int right,double pivot){
int leftPtr=left-1;
int rightPtr=right;
while(true){
while(theArry[++leftPtr]<pivot)//找出pivot大的左边的元素
;
//找出pivot小的右边的元素
while(rightPtr>0&&theArry[--rightPtr]>pivot)
;
if(leftPtr>rightPtr)
//如果左下标大于右下标则结束
break;
else
swap(leftPtr,rightPtr);
return leftPtr;
}
}
//----------------------------------------------------------------
public void swap(int dex1,int dex2){
double temp=theArry[dex1];
theArry[dex1]=theArry[dex2];
theArry[dex2]=temp;
}
}
//对象QuickSortApp的声明如下所示
public class QuickSortApp{
public static void main(String[] args){
int maxSise=16;//数组长度
Sample5 arr;//声明对象
arr=new Sample5(maxSise);//利用构造函数创建数组
for(int j=0;j<maxSise;j++){
//利用Math函数random产生随机数，初始化数组
double n=(int)(java.lang.Math.random()*99);
arr.insert(arr);
}
arr.dispaly();
arr.quickSort();
arr.dispaly();
}
}

复制代码