快速排序算法

快速排序的思想是找一个基准值pivot，两个索引从后，从前 同时推进，第一次排完比基准值大的都在其右边，比基准值小的都在其左边。下面给出两种解法

1

private static void quitckSort(int[] arr, int low, int high) {
        if (low < high) {//递归终止条件
            int pivot = getPivot(arr,low,high);//找到中轴，中轴左边全比中轴小，中轴右边全比中轴大
            System.out.println(Arrays.toString(arr));
            quitckSort(arr, low, pivot-1);//递归左边
            quitckSort(arr, pivot+1, high);//递归右边
        }
    }

    private static int getPivot(int[] arr, int start, int end) {
        int pivot =  arr[start];//以第一个元素做基准值
        while(end > start) {
            while(end > start && arr[end] >= pivot)
                end --;
            arr[start] = arr[end];//覆盖
            while(end > start && arr[start] <= pivot)
                start ++;
            arr[end] = arr[start];

        }
//        System.out.println(start);//到了这个位置，start 和 end 索引指向都一个位置，所以才退出的while循环
//        System.out.println(end);
        arr[end] = pivot;
        return start;
    }

View Code

2

    private static void quitckSort2(int[] arr, int low, int high) {
        int start = low;
        int end = high;
        int key = arr[low];
        while(end > start) {
            while(end > start && arr[end] >=key)
                end--;
            if (arr[end] <= key) {
                int temp = arr[end] ; //一旦出来了，要么是end和start索引重合了，要么是遇到比key小的值了
                arr[end] = arr[start];
                arr[start] = temp;
            }
            //此时key已不再最左边
            while(end > start && arr[start] <= key)
                start++;
            if (arr[start] >=key) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }

        }
        System.out.println(Arrays.toString(arr));
        if (start > low) {//说明存在左区间
            quitckSort2(arr, low, start-1);
        }
        if (high >end) {
            quitckSort2(arr, start+1, high);
        }

    }

View Code

这两种方法，第一个是从b站，青岛大学王卓老师视频中习得，第二种方法看书《offer来了》中看到，自我感觉第一种更容易理解和使用。