快速排序

快速排序的主要思想：

第一步、在待排序列中选择一个基准数元素，

第二步、将小于（或者大于）基准数的其他元素放到基准数元素的左边，将大于（或者小于）基准数的其他元素放到基准数元素的右边；

第三步、对基准数元素左右两边的序列执行第二步的操作直到序列只有一个元素

 

public class QuickSort {

    private static SortObj[] sortArray = {
        new SortObj(11,""),new SortObj(9,""),new SortObj(18,""),
        new SortObj(77,""),new SortObj(10,""),new SortObj(9,"+"),new SortObj(6,"")};

    public static void sort(int right, int left) {
        
        if(right >= left) {
            return;
        }
        
        int first = right;
        int tail = left;
        // 选取第一个为基准数
        SortObj obj = sortArray[first];
        
        while(first < tail) {
            // 从tail开始往前查出小于obj.value的元素,放到obj的左边
            while(first < tail) {
                if (sortArray[tail].value >= obj.value) {
                    tail--;
                } else {
                    sortArray[first++] = sortArray[tail];
                    break;
                }
            }
            // 从first开始往后查出大于obj.value的元素,放到obj的右边
            while(first < tail) {
                if(sortArray[first].value < obj.value) {
                    first++;
                } else {
                    sortArray[tail--] = sortArray[first];
                    break;
                }
            }
        }
        sortArray[first] = obj;
        printSortResult();
        // 左边重复执行上述操作
        sort(right, first - 1);
        // 右边重复执行上述操作
        sort(first + 1, left);
        
    }
    
    public static void printSortResult() {
        
        for(SortObj obj : sortArray) {
            System.out.print(obj.sequence + obj.value + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        printSortResult();
        sort(0, sortArray.length - 1);
    }
}

 

对于SortObj类，请查看 http://happy-tao-cool.iteye.com/blog/2160579