public class Paixu {
public static void main(String[] args) {
int[] a={5,45,12,89,100,47,20,33,54,18,95};
quickSort(a,0,a.length-1);
for (int i=0;i<a.length;i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
static void quickSort(int a[],int left,int right) //对数组a[]从left到right进行排序
{
int i;
if(right<=left)
{
return;
}
i=partion(a,left,right);
quickSort(a,left,i-1); //对左半部排序
quickSort(a,i+1,right); //对右半部排序
}
static int partion (int a[],int left,int right) //获取中间数的下标,比中间数大的在右边,比中间数小的在左边
{
int i=left;
int j=right-1;
int item=a[right];
while(true)
{
while(a[i]<item) i++; //如果比选定的数大,一直右移
while(item<a[j]) //如果比选定的数小,一直右移
{
j--;
if(j==0) break; //边界处理
}
if(i>=j) break; //如果左边和右边扫描相遇
int temp=a[i]; //把大的换到右边,把小的换到左边
a[i]=a[j];
a[j]=temp;
}
int temp=a[i]; //最后把最右边选定的参照值换到中间
a[i]=a[right];
a[right]=temp;
return i; //返回
}
}
|
|