博客

public class QuickSort {
    public static void main(String[] args) {
        Integer[] arrys = new Integer[]{13,11,10,3, 7, 1,14,1, 2, 6, 5, 4,9,12};
        sort(arrys, 0, arrys.length - 1);

        System.out.println(Arrays.asList(arrys));
    }

    /**
     * 排序
     * @param arrys 待排序数组 begin-end之间就是需要排序的片段
     * @param begin 数组需要排序的开始下标
     * @param end 数组需要排序的结束下标
     */
    public static void sort(Integer[] arrys, int begin, int end) {
        //如果需要排序的片段元素数量已经小于1，则不用排序
        if (begin >= end) {
            return;
        }
        //以begin作为分界值，排序比较并返回分界值最终所在的位置
        int position = compareReplace(arrys, begin, end);
        //以分界值为界，begin--分界值之间的片段重复排序操作
        int leftBegin = begin;
        int leftEnd = position - 1;
        //以分界值为界，分界值--end之间的片段重复排序操作
        int rightBegin = position + 1;
        int rightEnd = end;
        //分界值左边的片段做一次排序
        sort(arrys, leftBegin, leftEnd);
        //分界值右边的片段做一次排序
        sort(arrys, rightBegin, rightEnd);
    }

    /**
     * 比较替换 begin-end这一段数组做快速排序 以begin作为分界值进行比较
     * @param arrys
     * @param begin
     * @param end
     * @return 返回分界值最终的位置
     */
    public static int compareReplace(Integer[] arrys, int begin, int end) {
        //1-表示从右往左遍历 2-表示从左往右遍历
        int mod = 1;
        //以begin作为分界值
        while (begin != end) {
            if (arrys[begin] <= arrys[end]) {
                if (mod == 1) {
                    end--;
                }
                if (mod == 2) {
                    begin++;
                }
            }
            if (arrys[begin] > arrys[end]) {
                Integer temp = arrys[begin];
                arrys[begin] = arrys[end];
                arrys[end] = temp;
                //如果是从右往左遍历找到了比分界值小的值，则将分界值和这个值做一次位置替换，并切换遍历方式为从左往右遍历
                if (mod == 1) {
                    mod = 2;
                }
                //如果是从左往右遍历找到了比分界值小的值，则将分界值和这个值做一次位置替换，并切换遍历方式为从右往左遍历
                else {
                    mod = 1;
                }
            }
        }
        return begin;
    }
}

运行结果：