java 快速排序demo

快速排序算法思想如下，先选取一个元素作为基准，然后根据这个基准依次比较整个数列，最后把这个数列分为两类，例如，左边的数都不比这个基准大，右边的全比基准大，然后把这个基准放在中间，二分这两类。然后再把这个这个数列分成两块，在用这个算法。

package cn.lsd;

import java.util.Comparator;
import java.util.Random;

/**
 *
 * @date   2008-11-29 
 * @author lsd
 */
public class QuickSort {
    public static final Random RND = new Random();

    private void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private int partition(Object[] array, int begin, int end, Comparator cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        Object pivot = array[index];
        swap(array, index, end);	
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i], pivot) <= 0) {
                swap(array, index++, i);//<=>swap(array,index,i);index++;
            }
        }
        swap(array, index, end);	
        return (index);
    }

    private void qsort(Object[] array, int begin, int end, Comparator cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index - 1, cmp);
            qsort(array, index + 1,  end,  cmp);
        }
    }

    public void sort(Object[] array, Comparator cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }

    
    public static void main(String[] args){
        Integer[] a= new Integer[10];
        for(int i=0;i<10;i++){
            a[i]=10-i;
            System.out.println("a["+i+"]="+a[i].intValue());
        }

        Comparator<Integer> cmp =   new Comparator<Integer>(){
                                      public int compare(Integer o1, Integer o2) {
                                        return (o1.intValue()<o2.intValue()?-1:1);
                                      }
                                    };
                                    
        new QuickSort().sort(a, cmp);
        
        for(int i=0;i<10;i++){
            System.out.println("a["+i+"]="+a[i].intValue());
        }
    }
}