算法6 排序算法 QuickSort 快速排序

     

   

        快算排序 Quick Sort ，可能是应用最为广泛的算法，被视为20世纪科学和工程领域的十大算法之一。其流行的原因是因为它实现简单，可适用于不同数据，并且在一般场景下比其他算法要更快。其优点是：

可借用一个很小空间的辅助栈来进行原地排序；

对于长度为N的数组，其时间复杂度为 NlogN；

快速排序的内循环短小，这意味它无论在理论上还是在实际中，它都要更快。

缺点：

        要小心的避免错误，防止性能退化为N² 。

算法思想：

        快速排序 和 归并排序一样都是使用了分治思想的排序算法。他们都是将一个数组，一分为二，独自独立排序。 归并排序是将数组分为两个子数组分别排序，并将有序的子数组归并将整个数组进行排序；而快速排序是当子数组都有序了之后，整个数组自然就实现了有序。归并的切分位置就在数组中间位置；而快速排序的切分位置partition 取决于数组的内容。

Partition过程大致如图所示：

 

       快速排序需要推举出一个元素来作为我们的基准元素；如图所示：我们推举出我们的首个元素作为基准元素(V)。帮助我们的基准元素找他应该所处的位置过程，我们将其命名为 Partition的过程，即找到 j 的过程。

        结合如图所示，我们来看我们应该如何去做这件事：

在这个过程中，我们需要满足的V前面的元素是不大于V的，V后面的元素是不小于V的。即 arr[l+1...j] < v && arr[j+1...i-1] > v

         图中变量 , v :基准元素  ，l ：元素开始位置索引，j基准位置索引，i 遍历比较过程中的当前时刻的位置索引；

蓝色元素e本身比较前的位置就处于不小于V的位置，如果发现e 大于 V 不动，i++遍历下一个元素；如果发现当前遍历元素e小于V,则需要将e和紫色部分的首元素交换，并且j++。如此进行下去，直到i遍历完整个数组后，把l位置所在元素，和 j 位置所在元素 进行交换后，即可完成整个Partition的过程。

算法实现：

基于以上内容，我们来实现第一版的算法基本实现：

package com.cosyit.offer.algorithms;
 
import java.util.Arrays;
 
public class QuickSort1 {
 
    private static void quickSort(Comparable[] a, int n) {
        __quickSort(a, 0, n - 1); // a[0] - a[length-1]
    }
 
    private static void __quickSort(Comparable[] a, int l, int r) {
        //设置临界条件。  obscure
        if (l >= r) return;
        //隔板分区
        int p = partition(a, l, r);
        // l 到 p-1 的分区部分 进行快速排序。
        __quickSort(a, l, p - 1);
        // p+1 到 r 的分区部分 进行快速排序。
        __quickSort(a, p + 1, r);
    }
 
    /**
     * 推举出一个元素作为隔板元素以进行分区，隔板分区后该元素将处于其顺序的位置，并返回该隔板元素的索引。
     * 元素a[p]的隔板效果：左边的比隔板元素小 a[l...p-1] < arr[p]，右边都比隔板元素大 a[p] < a[p+1...r]
     *
     * @param a 传入的数组。
     * @param l 左边界元素索引。
     * @param r 有边界元素索引。
     * @return 隔板操作后的，隔板位置索引。
     */
    private static int partition(Comparable[] a, int l, int r) {
 
        // 1.推举出一个元素，这里我们推举我们的头部元素为隔板元素。
        Comparable v = a[l];
 
        // 2.遍历整个数组。a[l+1...j]
        int j = l; //j:不大于v左边分区的尾部元素位置索引。
        /**
         * 这里有一个定义的技巧，就是 j 和 i 的初始值设计:
         * * 为什么 把j的初始化值设置为l ,  因为这样设计 a[l+1...j]即a[l+1...l]，保证了小于v的分区，从开始是不存在的分区。
         * * 为什么 把i的初始化值设置为l+1, 因为这样设计 a[j+1...i]即a[l+1...l+1) ，保证了大于v这个分区，从开始是不存在的分区。
         */
        for (int i = l + 1; i <= r; i++) {
            if (less(a[i], v)) {
                swap(a, j + 1, i);
                j++;
            }
        }
 
        //放置隔板：i 遍历完的时候，元素v即a[l] 和 j进行交换。把j的标记位置索引 j 返回。
        swap(a, l, j);
 
        return j;
    }
 
 
    private static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
 
    public static void main(String[] args) {
        Integer[] arr = {6, 7, 1, 4, 3, 5, 2, 0};
 
        quickSort(arr, arr.length);
 
        System.out.println(Arrays.toString(arr));
 
    }
 
}

基础算法的改进：

      改进1：  推举首元素为隔板元素的是有弊端的，因为往往人们处理的数据大概率会是一个近乎有序的数组，这样的数据在进行 递归时候，分区的递归树的高度会很高，递归树的平衡度会很差。基于这个问题，我们应使 隔板元素 保持随机性，来避免这个问题。固添加如下代码以做优化：

 

改进2：如果处理切分元素有大量重复元素，而导致切分不平衡的情况，栈深度会变大。

       

 

优化一下思路,如图所示：

          之前，我们把大于V和小于V的放在了数组的一端，现在把大于V和小于V的放在数据的两端。

        如图所示：i，j 的位置为比较元素e，i++往右跑，j--往左跑。

i在遍历过程中遇到e>=v 不满足小于v的情况，停止i++;同理，j--的过程中遇到 e<= v 不满足大于v的情况，停止j--;

i和j交换位置，交换位置后，i++查看下一个元素，j++查看下一个元素。

直到 i 和 j 索引重合，意味着遍历结束。

        实际上，按照这个逻辑走完，其实 左分区 是小于等于v的元素集合，右分区是大于等于v的元素集合。

        如果 i 和 j 都指向了 等于v的元素，两个仍然要交换一下位置，这样就遇到大量等于v的元素的情况，也可以尽量平分这些元素。

算法思想实现：

package com.cosyit.offer.algorithms;
 
import java.util.Arrays;
import java.util.Random;
 
public class QuickSort3 {
 
    private static void quickSort(Comparable[] a, int n) {
        __quickSort(a, 0, n - 1); // a[0] - a[length-1]
    }
 
    private static void __quickSort(Comparable[] a, int l, int r) {
        //设置临界条件。  obscure
        if (l >= r) return;
        //隔板分区
        int p = partition(a, l, r);
        // l 到 p-1 的分区部分 进行快速排序。
        __quickSort(a, l, p - 1);
        // p+1 到 r 的分区部分 进行快速排序。
        __quickSort(a, p + 1, r);
    }
 
    /**
     * 推举出一个元素作为隔板元素以进行分区，隔板分区后该元素将处于其顺序的位置，并返回该隔板元素的索引。
     * 元素a[p]的隔板效果：左边的比隔板元素小 a[l...p-1] < arr[p]，右边都比隔板元素大 a[p] < a[p+1...r]
     *
     * @param a 传入的数组。
     * @param l 左边界元素索引。
     * @param r 有边界元素索引。
     * @return 隔板操作后的，隔板位置索引。
     */
    private static int partition(Comparable[] a, int l, int r) {
        // core 保持随机性。
        //生成随机索引。 l + 随机[0 ... r - l + 1)的数
        int randomIndex = l + new Random().nextInt(r - l + 1);
        //和首元素交换。
        swap(a, l, randomIndex);
 
        // 1.推举出一个元素，这里我们推举我们的头部元素为隔板元素。
        Comparable v = a[l];
 
        int i = l + 1, j = r;
 
        while (true) {
            //  i在运动的过程中，i <= r 防止索引越界。
            while (i <= r && less(a[i], v)) i++; //  i往前走不停止。
            while (j >= l + 1 && less(v, a[j])) j--; // j往前走不停止。
            if (i > j) break;
 
            //都停下来了，交换元素。
            swap(a, i, j);
            //各自指向下一个元素，继续。
            i++;
            j--;
 
        }
 
        swap(a,l,j);
        return j;
    }
 
 
    private static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
 
    public static void main(String[] args) {
        Integer[] arr = {6, 7, 1, 4, 3, 5, 2, 0};
 
        quickSort(arr, arr.length);
 
        System.out.println(Arrays.toString(arr));
 
    }
 
}

改进3：以上实现中，对于大量重复的元素，会不必要的将等值的元素进行交换。为了规避这个问题，有一种经典的实现方式 --- 三路切分的快速排序 Quick Sort 3 Way。

算法思路： 

之前在切分过程中都是切分为大于基准元素V和小于基准元素V的情况，三路排序则是切分为 等于基准元素V，大于V和小于V 三种情况。

 

          如图所示  l 为 首元素，此处放置了基准元素。 lt 指向小于V分区 的最后一个元素；gt指向大于V分区的 第一个元素。e 是活动元素a[i]  —— 当前要和基准元素V进行比较的元素。

    ① e小于V，e 和 ==v 的第一个元素交换 即 a [ lt + 1 ] ，然后 lt++,  i++;

    ② e大于V，e和 a[gt-1] 元素交换后，gt -- ,但是此时 i不用处理，因为i的元素是一个gt-1换过来的新元素 ;

    ③ 当元素e 即 a[i] 和基准元素V相等，直接 i++ 继续处理下一个元素即可。

    当整个数组 i 和 gt 索引重合的时候，就是所有元素遍历完成的时候。最后，l位置元素和 v 进行交换。lt 位置即为返回的位置。 

三路排序算法思想实现：

package com.cosyit.offer.algorithms;
 
import java.util.Arrays;
import java.util.Random;
 
public class QuickSort3Ways {
 
 
    private static void quickSort3Ways(Comparable[] a, int l, int r) {
 
        if(r<=l) return;
 
 
        // core 保持随机性。
        //生成随机索引。 l + 随机[0 ... r - l + 1)的数
        int randomIndex = l + new Random().nextInt(r - l + 1);
        //和首元素交换。
        swap(a, l, randomIndex);
 
        // 1.推举出一个元素，这里我们推举我们的头部元素为隔板元素。
        Comparable v = a[l];
 
        int lt = l;  // a[l+1 ... lt] < v ， a[l+1 ... lt]初始范围为空。
        int gt = r + 1; // a[gt...r] > v ，a[gt...r] 初始范围为空。
        int i = l + 1;// l为首个基准元素V，遍历元素从l+1开始。     a[lt+1...i) == v
 
        while (i < gt) {  //只要i在比较的过程中，i没有和gt碰上，就一直遍历。
 
            int cmp = a[i].compareTo(v);
            if (cmp < 0) {
                swap(a, i, lt + 1);
                lt++; i++;
            } else if ( cmp >0) {
                swap(a, i, gt - 1);
                gt--;
            } else {
                i++;
            }
        }
 
 
        //v和lt交换
        swap(a, l, lt); lt--;
 
        //此时， ==v 的部分已经在有序的部分，无须排序。
        
        //排序 l...lt 的左分区。
        quickSort3Ways(a, l, lt );
        //排序 gt...r 的右分区。
        quickSort3Ways(a, gt, r);
 
    }
 
 
    private static void swap(Comparable[] arr, int i, int j) {
        Comparable temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
 
    public static void main(String[] args) {
        Integer[] arr = {6, 7, 1, 4, 3, 5, 2, 0};
 
        quickSort3Ways(arr,0, arr.length-1);
 
        System.out.println(Arrays.toString(arr));
 
    }
 
}

以上代码可以将和切分元素相等的元素归位，这样和v相等的元素在就不会在递归函数中处理了，在递归的函数中和v相等的元素，不会参与排序了，这样提高了效率。