快速排序详解

前言

    快排是不稳定的排序，快排的适用场景是无序的序列，例如此时有一个数组是有序的 / 逆序的，此时的快排效率是最慢的。

过程：

    找一个基准值，找的过程就以挖坑法的方式填坑，第一次排序以挖坑发填完坑之后，以基准值为界限，划分左边和右边，划分完成之后继续以递归的方式挖坑然后划分成左边和右边... 一直循环这个过程，直到划分的子区间只剩下一个元素（数组中只有一个元素就是有序的）

一、挖坑法

    在给划分后的子区间进行排序的时候。首先要有左右的区间界限，所以函数头的设计就是 数组 + 左区间 + 右区间 （都是下标的形式），挖坑法的过程如下：

  挖坑法代码实现：

public static void quickSort(int[] arr) {
        quick(arr, 0, arr.length - 1);
    }
    private static void quick(int[] arr, int start, int end) {
        if (start >= end) return;
        int pivot = partition2(arr, start, end);
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }
 
    // 挖坑法
    private static int partition(int[] arr, int left, int right) {
        int tmp = arr[left];
        while (left < right) {
            // 此时一定要取等号，否则会进入死循环
            while (left < right && arr[right] >= tmp) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= tmp) left++;
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }

二、hoare 法

 haore 法实现快排：

// hoare 法
    private static int partition2(int[] arr, int left, int right) {
        int tmp = arr[left];
        int i = left;
        while (left < right) {
            while (left < right && arr[right] >= tmp) right--;
            while (left < right && arr[left] <= tmp) left++;
            swap(arr, left, right);
        }
        swap(arr, left, i);
        return left;
    }

三、快排的问题以及优化

1. 为什么都是先走右边的指针，而不是先走左边的指针？

    如果是先走左边的 l 指针，此时左边的指针是找比基准值大的，先走左边后走右边，在左右指针相遇时，如果当前左右指针的值比基准值大，然后要和基准值交换位置，就会把大的值换到左边，而较小的基准值换到了后面，不符合排序的要求。

2. 代码中里层 while 循环条件必须写 “=” ？

    一定要写等号，如果不写可能会造成死循环，如果数组中有值相等的元素，如果不写等号，也就是循环就进不去，直接交换，此时交换的是两个相等的元素，然后再次循环下来的时候左右指针都没有变化，此时比较的还是这两个相等的元素，就造成了死循环。

3. 针对栈溢出问题？

     如果元素是有序的，此时就相当于一颗单分支的二叉树，如果树的高度很高，此时就需要递归很多次才能结束，但是此时栈帧是有限的，就很容易造成栈溢出。

4. 优化快排

    上述代码有两个问题：1. 栈溢出， 2. 如果数组有序或者数组是逆序的，时间复杂度会达到O（N）。所以针对快排代码可以进一步优化。

（1）三数取中法

private static int midThree(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        if (arr[left] < arr[right]) {
            if (arr[mid] < arr[left]) return left;
            else if (arr[mid] > arr[right]) return right;
            else return mid;
        } else {
            if (arr[mid] > arr[left]) return left;
            else if (arr[mid] < arr[right]) return right;
            else return mid;
        }
    }

     上述代码的逻辑就是在数组开始位置，数组中间位置，还有结束位置分别取三个数，然后找出这三个数的中位数，以这个数为基准（开始没有优化的时候是以数组开始位置的元素为基准，这里有一个缺陷，就是如果这个元素刚好是数组中最大的元素或者是最小的元素，此时的二叉树就是一个单分支的树），去进行递归，这样可以保证数组中的元素尽量是一颗满二叉树 / 完全二叉树，这样就可以减少递归的次数。

（2）剩余元素少的时候直接用插入排序

    可以看到递归的过程就是将数组一步一步分割形成一颗二叉树的过程，如果是一颗二叉树，此时节点数量从上到下是呈指数的形式增长的，所以最后两层的节点数量是最多的，所以递归的次数也是最多的，但是在排序过程中一定是越排越有序的，其实当剩下最后两层节点的时候，此时的数组已经是趋于有序的了，前一篇文章讲过，一个序列趋于有序的时候，用插入排序是最快的，时间复杂度是 O（N），所以快排还可以进一步的优化就是当元素剩余少的时候，用插入排序的方式来排序，此时就减少了递归的次数，也是一个有效的优化的方法。

    注：不能把插入排序直接拿过来用，现在是有区间的进行排序而不是对整个数组排序，所以函数头中还需要有数组的左右区间

// 进一步优化：当递归到只剩下后两层的节点时，此时这部分剩下的数据已经接近有序了，所以此时可以
    // 插入排序是最快的, 但是是区间内进行插入排序，所以要指定一个区间
    public static void insertSort2(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    // arr[j + 1] = tmp;
                    break;
                }
            }
            arr[j + 1] = tmp;
        }
    }
 
// 优化之后排序的逻辑
private static void quick(int[] arr, int start, int end) {
        if (start >= end) return;
 
        // 使用这个优化主要是减少递归的次数
        if (end - start + 1 <= 14) {
            // 插入排序
            insertSort2(arr, start, end);
        }
 
        int index = midThree(arr, start, end);
        // 找到这个下标之后交换 start 和 index 位置的元素即可
        swap(arr, index, start);
        int pivot = partition2(arr, start, end);
        quick(arr, start, pivot - 1);
        quick(arr, pivot + 1, end);
    }

四、非递归实现快排

// 非递归实现快速排序
    /*
    * 过程：先找一次基准，找完之后将基准左边的 左右区间 和 右边的 左右区间 进栈，
    * 之后将分别弹出左右区间再去找基准，找的过程中需要判断当前基准的左右区间的元素格式是否 >= 2
    * （如果只有一个元素 / 没有元素，此时就不用排序了）*/
    public static void quickSort2(int[] arr) {
        Deque stack = new LinkedList<>();
        int left = 0;
        int right = arr.length - 1;
        int pivot = partition(arr, left, right);
        // 左边有两个元素的情况
        if (pivot > left + 1) {
            stack.push(left);
            stack.push(pivot - 1);
        }
        // 右边有两个元素的情况
        if (pivot < right - 1) {
            stack.push(pivot + 1);
            stack.push(right);
        }
        while (!stack.isEmpty()) {
            right = stack.poll();
            left = stack.poll();
            pivot = partition(arr, left, right);
            // 找完基准之后检查左右两边有否还有两个或以上的元素，如果有此时继续找进栈
            // 之后循环出栈再找基准
            // 左边有两个元素的情况
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }
            // 右边有两个元素的情况
            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }