QuickSort

作者: 最爱水皮蛋 | 来源:发表于2016-12-06 14:45 被阅读0次

    思想:
    以第一个为参照元素,分别从第二个和最后一个逐一和参照元素比较,小的留在左边low区域,大的留在右边high区域
    第一个元素为中轴,i代表low区,j代表high区

    Paste_Image.png

    i的值小于中轴,则不动,如遇到大于中轴,则换j开始比较

    Paste_Image.png

    j的值大于中轴则不动,如果小于中轴,则和i值进行换位

    Paste_Image.png

    换位后

    Paste_Image.png

    按照这个规则继续循环,直至j<i时,

    Paste_Image.png Paste_Image.png Paste_Image.png

    在重新开始

    Paste_Image.png

    Java实现其思想

    package sortingAlgo;
    
    import java.util.Arrays;
    import java.util.Random;
    
    /**
     * @author 水皮蛋 
     * 思想:以第一个为参照元素,分别从第二个和最后一个逐一和参照元素比较,小的留在左边low区域,大的留在右边high区域
     * 特性:unstable sort、In-place sort。
     * 最坏运行时间:当输入数组已排序时,时间为O(n^2),当然可以通过随机化来改进(shuffle array 或者 randomized
     *         select pivot),使得期望运行时间为O(nlgn)。
     * 最佳运行时间:O(nlgn) 快速排序的思想也是分治法。
     *
     */
    public class QuickSort {
    
        public static void main(String[] args) {
            int[] arr = createRandomArray();
            System.out.println(Arrays.toString(arr));
            System.out.println(Arrays.toString(quickSort(arr, 0, arr.length - 1)));
        }
    
        public static int[] quickSort(int[] arr, int low, int high) {
            if (low < high) {
                int privotLoc = partition(arr, low, high); // 将表一分为二
                quickSort(arr, low, privotLoc - 1); // 递归对低子表递归排序
                quickSort(arr, privotLoc + 1, high); // 递归对高子表递归排序
            }
            return arr;
        }
    
        static int partition(int[] arr, int low, int high) {
    
            // 参照元素,我们可以叫中轴,一般多为第一个或者最后一个
            int privotKey = arr[low];
            // 从表的两端交替地向中间扫描
            while (low < high) {
                while (low < high && arr[high] >= privotKey) {
                    high--;
                }
                // 比中轴小移到低端
                arr[low] = arr[high];
                while (low < high && arr[low] <= privotKey) {
                    low++;
                }
                // 比中轴大移到高端
                arr[high] = arr[low];
            }
            // 中轴移至尾端
            arr[low] = privotKey;
            return low;
        }
    
        /**
         * 使用Random类产生随机数组的对象
         * 
         * @return 随机数组
         */
        public static int[] createRandomArray() {
            Random random = new Random();
            int[] array = new int[10];
            for (int i = 0; i < 10; i++) {
                array[i] = random.nextInt(100);
            }
            return array;
        }
    
    }
    
    

    相关文章

      网友评论

          本文标题:QuickSort

          本文链接:https://www.haomeiwen.com/subject/ihxrmttx.html