排序----快速排序

佚名 6年前 (2019-04-21) 随笔 1733人围观抢沙发百度已收录

一.原理

　　1.1.动态演示图

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　1.2.动态图讲解

　　快速排序选择一个基数，将数组中比该基数大的放置该数的右边，比该基数小的放置该数的左边。采用递归进行以上操作直至排序完毕.

　　1.3.数据演示

　　原始数组：8 4 7 10 6 5 4 8

　　第一次排序过程：默认使用数组第一个元素为基准8

　　8 4 7 10 6 5 4 8　　4 4 7 10 6 5 4 8　　4 4 7 10 6 5 4 8　　4 4 7 10 6 5 10 8　　4 4 7 5 6 5 10 8　　4 4 7 5 6 5 10 8　　4 4 7 5 6 8 10 8

　　对以8为基准左边数据进行排序，采用递归。

　　对以8为基准右边数据进行排序，采用递归。

二.代码实现

public class ArraySortUtils {

    /**
     * 返回数组的字符串
     * @param array
     * @return
     */
    public static String arrayToString(int[] array){
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < array.length; i++) {
            if( i != (array.length - 1)){
                sb.append(array[i] + ",");
            }else{
                sb.append(array[i] + "]");
            }
        }
        return sb.toString();
    }


    /**
     * 快速排序
     * @param array
     */
    public static void quickSort(int[] array){
        quickSort(array,0,array.length - 1);
    }

    /**
     * 内部递归实现
     * @param array
     * @param start
     * @param end
     */
    private static void quickSort(int[] array,int start,int end){
        //只有结束位置大于开始位置才能进行排序
        if(start < end) {
            //设置基准数据,默认使用数组开始元素
            int stand = array[start];
            //创建两个变量用于记录比基数大的位置和比基数小的位置，默认是传进来的start,end
            int low = start;
            int high = end;
            //进行快速排序
            //当小角标大于等于大角标就退出循环
            while (low < high) {
                //当最后数据大于等于基数就将high向前移动
                while (low < high && stand <= array[high]) {
                    high--;
                }
                //当后面元素小于基数，就将后面元素赋值给小于基数的位置
                array[low] = array[high];
                //当前面数据小于基数就将low向后移动
                while (low < high && stand > array[low]) {
                    low++;
                }
                //当前面元素大于基数，就将前面元素赋值给大于基数的位置
                array[high] = array[low];
            }
            //将基数数据赋值到low==high位置上，即上述循环跳出时,这时基数左边都是小于它的，基数右边都是大于等于它的
            array[low] = stand;
            //每一次快速排序结果打印
            System.out.println(arrayToString(array));
            //对基数左边进行快速排序
            quickSort(array, start, low - 1);
            //对基数右边进行快速排序
            quickSort(array, low + 1, end);
        }
    }
}

三.演示结果

public class ArraySortUtilsDemo {

    public static void main(String[] args) {
        //4 4 7 5 6 8 10 8
        int[] array = new int[]{8,4,7,10,6,5,4,8};
        System.out.println("排序前：" + ArraySortUtils.arrayToString(array));
        //ArraySortUtils.bubbleSort(array);
        ArraySortUtils.quickSort(array);
        System.out.println("排序后：" + ArraySortUtils.arrayToString(array));
    }
}

测试结果与上述推断一样:

　　排序前：[8,4,7,10,6,5,4,8]
　　[4,4,7,5,6,8,10,8]
　　[4,4,7,5,6,8,10,8]
　　[4,4,7,5,6,8,10,8]
　　[4,4,6,5,7,8,10,8]
　　[4,4,5,6,7,8,10,8]
　　[4,4,5,6,7,8,8,10]
　　排序后：[4,4,5,6,7,8,8,10]