package com.test.arithmetic;import java.util.Arrays;/** * Two point go together, small is left and big is right. * Thus the first meet will separate the array to half small and half big. * Created by Ryan on 2017/3/25/025. */public class QuickSort {    public  int count = 0;    public  int[] sort(int[] source, int low, int high) {        if (low >= high) {            return source;        }        int first = low;        int last = high;        int key = source[first];        while (first < last) {            //find the first smaller from the end            while (last > first && source[last] >= key) {                last--;            }            if (first < last) {                source[first] = source[last];                first++; //The first one has already been sorted, move to the next one.            }//else first = last, that is the same one, do not need to swap them            //find the first bigger from the start            while (first < last && source[first] <= key) {                first++;            }            if (first < last) {                source[last] = source[first];                last--; //The last one has already been sorted as a bigger, move to the previous one.            }        }        source[first] = key; //put the key        System.out.println("The " + ++count + " sort:");        Arrays.stream(source).forEach(item -> System.out.print(item + ", "));        System.out.println();        sort(source, low, first - 1);        sort(source, first + 1, high);        return source;    }    public void quickSort1(int arr[], int low, int high) {        int l = low;        int h = high;        int key = arr[low];        while (l < h) {            while (l < h && arr[h] >= key) {                h--;            }            if (l < h) {                int temp = arr[h];                arr[h] = arr[l];                arr[l] = temp;                l++;            }            while (l < h && arr[l] <= key) {                l++;            }            if (l < h) {                int temp = arr[h];                arr[h] = arr[l];                arr[l] = temp;                h--;            }        }        System.out.print("l=" + (l + 1) + "h=" + (h + 1) + "key=" + key + "\n");        if (l > low) quickSort1(arr, low, l - 1);        if (h < high) quickSort1(arr, l + 1, high);    }    public 
     
       void swap(T[] source, int i, int j) {        T temp = source[i];        source[i] = source[j];        source[j] = temp;    }    /**     * 方式2 更高效点的代码：     */    public 
      
       > T[] quickSort2(T[] targetArr, int start, int end) {        int i = start + 1, j = end;        T key = targetArr[start];        if (start >= end) return (targetArr);        /**         * 从i++和j--两个方向搜索不满足条件的值并交换         *条件为：i++方向小于key，j--方向大于key         */        while (true) {            while (targetArr[j].compareTo(key) > 0) j--;            while (targetArr[i].compareTo(key) < 0 && i < j) i++;            if (i >= j) break;            this.swap(targetArr, i, j);            if (targetArr[i] == key) {                j--;            } else {                i++;            }        }        /**         * 关键数据放到‘中间’*         */        this.swap(targetArr, start, j);        if (start < i - 1) {            this.quickSort2(targetArr, start, i - 1);        }        if (j + 1 < end) {            this.quickSort2(targetArr, j + 1, end);        }        return targetArr;    }    /**     * 方式3：减少交换次数，提高效率     */    public  
       
        > void quickSort3(T[] targetArr, int start, int end) {        int i = start, j = end;        T key = targetArr[start];        while (i < j) {                /*按j--方向遍历目标数组，直到比key小的值为止*/            while (j > i && targetArr[j].compareTo(key) >= 0) {                j--;            }            if (i < j) {                    /*targetArr[i]已经保存在key中，可将后面的数填入*/                targetArr[i] = targetArr[j];                i++;            }                /*按i++方向遍历目标数组，直到比key大的值为止*/                /*此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/            while (i < j && targetArr[i].compareTo(key) <= 0) {                i++;            }            if (i < j) {                    /*targetArr[j]已保存在targetArr[i]中，可将前面的值填入*/                targetArr[j] = targetArr[i];                j--;            }                /*此时i==j*/            targetArr[i] = key;                /*递归调用，把key前面的完成排序*/            this.quickSort3(targetArr, start, i - 1);                /*递归调用，把key后面的完成排序*/            this.quickSort3(targetArr, j + 1, end);        }    }}
       
      
     

package com.test.arithmetic;import org.junit.Assert;import org.junit.Before;import org.junit.Test;import java.util.Arrays;import static org.junit.Assert.*;/** * Created by Ryan on 2017/3/25/025. */public class QuickSortTest {    private int[] source;    private Integer[] source2;    private Integer[] source3;    private QuickSort quick;    private int[] expect;    private Integer[] expect2;    private Integer[] expect3;    @Before    public void setUp(){        source = new int[]{
     13, 16, 1, 1, 5, 15, 13, 15, 13, 8};        source2 = new Integer[]{
     13, 16, 1, 1, 5, 15, 13, 15, 13, 8};        source3 = new Integer[]{
     13, 16, 1, 1, 5, 15, 13, 15, 13, 8};        expect = new int[]{
     1, 1, 5, 8, 13, 13, 13, 15, 15, 16};        expect2 = new Integer[]{
     1, 1, 5, 8, 13, 13, 13, 15, 15, 16};        expect3 = new Integer[]{
     1, 1, 5, 8, 13, 13, 13, 15, 15, 16};        quick = new QuickSort();    }    @Test    public void testSort() throws Exception {        int[] source = new int[]{
     13,16,1,1,5,15,13,15,13,8 };        int[] sort = quick.sort(source, 0, source.length - 1);        Assert.assertArrayEquals(expect, sort);    }    @Test    public void testSort1(){        QuickSort quick = new QuickSort();        quick.quickSort1(source, 0, source.length - 1);        Assert.assertArrayEquals(expect, source);    }    @Test    public void testSort2(){        QuickSort quick = new QuickSort();        quick.quickSort2(source2, 0, source2.length - 1);        Assert.assertArrayEquals(expect2, source2);    }    @Test    public void testSort3(){        QuickSort quick = new QuickSort();        quick.quickSort3(source3, 0, source.length - 1);        Assert.assertArrayEquals(expect3, source3);    }}