package test.java.sort.demo;

import test.java.sort.Util.DataWrap;

/**
 * 2017-5-16 Java实现快速排序
 * @author tom
 */
public class FastSortDemo {

    /**
     * 交换数组中下标为i和下标为j的两个数
     * @param data
     * @param i
     * @param j
     */
    private static void swap(DataWrap[] data, int i, int j) {

        DataWrap temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public static void fastSort(DataWrap[] data, int start, int end) {
        // 需要排序
        if (start < end) {
            // 以第一个元素作为界点
            DataWrap base = data[start];
            int i = start;
            int j = end + 1;

            while (true) {
                // 如果从左到右找到了比分界点大的值,就跳出当前循环，此时i的值记录了这个数的索引
                while (i < end && data[++i].compareTo(base) <= 0);
                // 如果从右往左找到了比分界值小的值，跳出当前循环，此时j的值记录了该数的索引
                while (j > start && data[--j].compareTo(base) >= 0);
                //i<j时才需要交换，如果i>=j还没有找到左边比分界值大，右边比分界值小的数,说明已经达到了第一趟的要求
                if (i < j) {
                    swap(data, i, j);
                } else {
                    break;
                }
            }
            //把分解值放到合适的位置,j的位置存放的是最后一个比分界值小的数
            swap(data, start, j);
            //递归左右两个序列，j这个位置是上一趟的分界值，已经放到了适当的位置了，所有不需要再排序
            System.out.println(java.util.Arrays.toString(data));
            fastSort(data, start, j-1);
            fastSort(data, j+1, end);
        }
    }
    
    public static void main(String[] args) {
        DataWrap[] data = { 
                new DataWrap(19, ""), 
                new DataWrap(45, ""), 
                new DataWrap(16, ""), 
                new DataWrap(21, "*"),
                new DataWrap(23, ""), 
                new DataWrap(21, ""),
                new DataWrap(30, ""),};
        System.out.println("排序之前");
        System.out.println(java.util.Arrays.toString(data));
        System.out.println("开始排序");
        fastSort(data,0,data.length-1);
        System.out.println("排序完成");
        System.out.println(java.util.Arrays.toString(data));
    }
}

package test.java.sort.Util;

/**
 * 2017-5-15 定义一个数据包装类
 * @author tom
 */
public class DataWrap implements Comparable<DataWrap> {
    int data;
    String flag;

    public DataWrap(int data, String flag) {
        this.data =http://www.mamicode.com/ data;
        this.flag = flag;
    }

    @Override
    public String toString() {
        return data + flag;
    }

    // 如果当前data大于dw,返回1；小于和等于返回数值不是1
    @Override
    public int compareTo(DataWrap dw) {
        return this.data > dw.data ? 1 : (this.data =http://www.mamicode.com/= dw.data ? 0 : -1);
    }
}