快速排序法1

方法1：
public class QuickSort {
int[] n ={45,99,69,29,28,27,26,2,10,3,24,23,9,8,25,85,33,40,78,98,54,7,69};
public static void main(String[] args) {
QuickSort q = new QuickSort();
q.out(q.n.length);
q.quickSort(0, q.n.length-1);
q.out(q.n.length);
}
/**
* 快速排序主循环体，主要利用一个可变数组list
* 把作为参考的基准数先放到list中，然后跟数组一段区间内的数
* 比较，大的放到list末尾，小的就放到这个基准数的左边
* @param i 数组区间的起始坐标
* @param j 数组区间的终止坐标
*/
public void quickSort(int i, int j){
int t = n[i];            //t 记录一个用来做参考的数
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(t);
int length = j + 1 - i;  //记录i----j总共是多少个数字
int start = i++;            //记录i的起始坐标
int left = 0;          //给temp里面填数字时候的坐标,也就是小于t的数值的索引
int right = length -1;
/**
* 判断temp数组当前的左边left和右边坐标right是否重叠
* 如果重叠就表示区间内所有数据都按一定的顺序放到temp中
*/
while(left < right){        
if(t < n[j]){
    //将此数字加到末尾
temp.add(n[j]) ;
right--;
}else{
//在temp中放到t的前面
temp.add(left, n[j]);
left++;
}
if(left == right){
break;
}
if(t < n[i]){
temp.add(n[i]);
right--;
}else{
temp.add(left, n[i]);
left++;
}
i += 1;
j -= 1;
}
//到此时temp里面的顺序就排成了左边都小于t，右边都大于t
for(int k = 0; k < temp.size(); k++){
n[start + k] = temp.get(k);
}
//以t为分界线再分别对左边和右边进行划分，这样逐级进行最终将分成若干对最小的两个数值比较
//t的左边在原数组里的范围
if(left > 1){
quickSort(start, start + left -1);
}
//t的右边在原数组里的范围
if(left + 1 < length -1){
quickSort(start + left + 1, start + length -1); 
}
}
public void out(int j){
for(int i = 0; i < j; i++){
System.out.print(n[i] + " ");
}
System.out.println();
}
}