package QuickSort;
imp
public class SpeedSort {
/**
* 快速排序
快速排序思想是，通过对列表分组，然后对分组进行排序，分组的策略不同其他Shell分组排序，对子列表的分组，是取子列表的第一个元素作为基准，通过移动，将子列表中，大于基准的元素移到基准右边，小于基准的元素移到基准左边。那么原 子列表被分为左右两子列表，对子列表重复下去，直到子列表长度为一
*/
public static void sort(int[] array){
Stack<Integer> stack = new Stack<Integer>();//栈中存储 分组得到的子列表两端标记
stack.push(array.length-1);//将起始列表的右端压入栈
stack.push(0);//将结束列表的左端压入栈
while(!stack.isEmpty()) //当栈中没有子列表时 跳出循环
{//因为压入栈中是成对的压入（尾首）压入顺序是 先尾 后首
int start = stack.pop();//先取 首
int end = stack.pop();//后取 尾
int mid = sortOnceIJ(array,start,end); //对以 start为首 end为尾的 子列表 进行排序 分组，返回分组 中间值
if(mid+1<end) //如果中间值和尾 之间至少有一个元素 压入尾（end）首（mid+1）
{
stack.push(end);
stack.push(mid+1);
}
if(mid-1>start) //如果首和中间值 之间至少有一个元素 压入尾（mid-1）首（start）
{
stack.push(mid-1);
stack.push(start);
}
}
}
//对array中i-j的子列表进行分组排序：选取子列表第一个元素为基准，通过移动，使基准左边元素大于基准，右边元素小于基准
private static int sortOnceIJ(int []array,int i,int j){
if(i==j)
return i;
int key = array[i];//key为基准
boolean rl = true;//true:key在左边，和右边元素进行比较，并移动 false:key在右边，和左边元素比较，并移动
while(i<j){
if(rl)
{//如果左边元素大于key，左边游标右移
if(key<=array[j])
j--;
else
{//如果左边元素小于key，交换左边元素，并设置key在左边
switchArray(array,i,j);
rl = false;
}
}else
{
if(key>array[i])
i++;
else
{
switchArray(array,i,j);
rl = true;
}
}
}
return i;
}
//只分组排序一次
public static void sortOnce(int []array){
int i=0;
int j=array.length-1;
int key = array[0];
boolean rl = true;//true:key在左边 false:key在右边
while(i<j){
if(rl)
{
if(key<=array[j])
j--;
else
{
switchArray(array,i,j);
rl = false;
}
}else
{
if(key>array[i])
i++;
else
{
switchArray(array,i,j);
rl = true;
}
}
}
}
private static void switchArray(int[] array,int i,int j){
int temp = array[j];
array[j] = array[i];
array[i] = temp;
}
private static void printArray(int[]array)
{
for(int da
System.out.print(da
}
System.out.println();
}
public static void main(String[] args) {
int []array = new int[]{-1,5,2,5,6,1,9,6};
for(int da
System.out.print(da
}
System.out.println("\n-");
sort(array);
for(int da
System.out.print(da
}
}
}
评论