快速排序

• 利用分治思想的实现排序的算法
• 其基本思路是先将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，然后继续在这两侧进行划分，直到数组有序
• 快速排序的最好时间复杂度为O(N*logN)，最差时间负责度为O(N^2)，空间复杂度为O(1)
  快速排序算法最重要的是如何分区的问题，我们可以利用荷兰国旗算法问题的思路来完成对数组的分区

1、快速排序的分区算法

1.1、荷兰国旗问题-二分区域

   将一个数组arr[L…R]按照指定位置的数进行划分，小于等于的到左边，大于的到右边，最后返回这个指定值的位置


思路：

• 我们选定最右侧的一个数作为基准数据，先将arr[L…R-1]上的数与基准数arr[R]进行比较,小于等于的放到左侧，大于的放到右侧，再将大于区域最左边的数和arr[R]进行交换，这个位置下标就是返回值
• 在划分的过程中，我们先假定一个小于等于的区域，最右侧边界的下标位置为L-1,即不包含任何区域上的数，从数组的L位置开始，到R-1位置进行和基准数字arr[R]比较，
• 假设比较时当前位置为index,如果arr[index]<=arr[R],则将arr[index]与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
• 如果arr[index]>arr[R],则当前下标右移一位
• 这样做的目的是小于等于区域包含了最右侧的下标位置，并且小于等于区域的下一位就是大于区域的第一个位置，最后将其和arr[R]位置交换，就能得到最后的结果
  
  
  过程：
• 1、先假定arr[R]位置的数为比较的基准值，假定小于等于区域的最右侧边界为L-1
• 2、从L开始到R-1位置，将当前值与arr[R]进行比较，
• 3、如果当前值小于等于基准值，则将当前值与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
• 4、如果当前值大于基准值，则当前下标右移一位
• 3、最后将小于等于区域的下一个位置的数和arr[R]位置交换，此时和arr[R]交换位置的下标就是二分区域的位置下标
  • 时间复杂度：O(N)
  • 空间复杂度：O(1)

/**
     * 荷兰国旗问题-二分区域
     * 将一个数组arr[L...R]按照指定位置的数进行划分，小于等于的到左边，大于的到右边，最后返回这个指定值的位置
     * 思路：
     * 我们选定最右侧的一个数作为基准数据，先将arr[L...R-1]上的数与基准数arr[R]进行比较,小于等于的放到左侧，大于的放到右侧，再将大于区域最左边的数和arr[R]进行交换，这个位置下标就是返回值
     * 在划分的过程中，我们先假定一个小于等于的区域，最右侧边界的下标位置为L-1,即不包含任何区域上的数，从数组的L位置开始，到R-1位置进行和基准数字arr[R]比较，
     * 假设比较时当前位置为index,如果arr[index]<=arr[R],则将arr[index]与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
     * 如果arr[index]>arr[R],则当前下标右移一位
     * 这样做的目的是小于等于区域包含了最右侧的下标位置，并且小于等于区域的下一位就是大于区域的第一个位置，最后将其和arr[R]位置交换，就能得到最后的结果
     * 过程：
     * 1、先假定arr[R]位置的数为比较的基准值，假定小于等于区域的最右侧边界为L-1
     * 2、从L开始到R-1位置，将当前值与arr[R]进行比较，
     * 3、如果当前值小于等于基准值，则将当前值与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
     * 4、如果当前值大于基准值，则当前下标右移一位
     * 3、最后将小于等于区域的下一个位置的数和arr[R]位置交换，此时和arr[R]交换位置的下标就是二分区域的位置下标
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public static int twoPartition(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }
        int pivot = arr[R];// 保存一个基准值
        int lessRight = L - 1;// 小于等于区域的最右侧边界
        int index = L;// 当前位置
        while (index < R) {
            if (arr[index] <= pivot) {
                // 小于等于，将当前值与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
                swap(arr, index, ++lessRight);
            }
            index++;
        }
        // 最后将小于等于区域的下一个位置的数和arr[R]位置交换
        swap(arr, ++lessRight, R);
        return lessRight;
    }

1.2、荷兰国旗问题-三分区域

   将一个数组arr[L…R]按照指定位置的数进行划分，小于等于的到左边，等于的放到中间，大于的放到右边，最右返回等于区域的前后两个下标位置
   鉴于java语言的特性，我们返回一个长度为2的数组，0位置为等于区域左边的下标，1位置为等于区域右边的下标。
  

思路：

• 整体思路和二分区域的类似，先讲arr[R]位置的数作为基准值，将arr[L…R-1]上的数与基准数arr[R]进行比较,小于等于的放到左侧，等于的放中间，大于的放到右侧，最后将大于区域最左边的数和arr[R]进行交换
• 在实际划分的过程中，我们要假定小于和大于两个区域，一开始小于区域最右侧下标为L-1(代表没有数据),大于区域最左侧下标为R(因为现在操作的是L…R-1,所以R位置代表没有数据)
• 当前值从L开始，到最大边界左侧的位置(这里非常容易出错)，将当前值与arr[R]进行比较，
• 如果当前值和基准值相等，则当前下标右移一位
• 如果当前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
• 如果当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
• 最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边的下标，和arr[R]交换的位置就是等于区域右侧的下标
    
  
  过程：
• 1、先假定arr[R]位置的数为比较的基准值，假定小于区域的最右侧边界为L-1，大于区域的最左侧边界为R
• 2、从L开始到到最大边界左侧的位置(这里非常容易出错)，将当前值与arr[R]进行比较，
• 3、如果当前值和基准值相等，则当前下标右移一位
• 4、如果当前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
• 5、如果当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
• 6、最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边e下标，和arr[R]交换的位置就是等于区域右侧的下标
• 时间复杂度：O(N)
• 空间复杂度：O(1)

/**
     * 荷兰国旗问题-三分区域
     * 将一个数组arr[L...R]按照指定位置的数进行划分，小于等于的到左边，等于的放到中间，大于的放到右边，最右返回等于区域的前后两个下标位置
     * 鉴于java语言的特性，我们返回一个长度为2的数组，0位置为等于区域左边的下标，1位置为等于区域右边的下标。
     * 思路：
     * 整体思路和二分区域的类似，先讲arr[R]位置的数作为基准值，将arr[L...R-1]上的数与基准数arr[R]进行比较,小于等于的放到左侧，等于的放中间，大于的放到右侧，最后将大于区域最左边的数和arr[R]进行交换
     * 在实际划分的过程中，我们要假定小于和大于两个区域，一开始小于区域最右侧下标为L-1(代表没有数据),大于区域最左侧下标为R(因为现在操作的是L...R-1,所以R位置代表没有数据)
     * 当前值从L开始，到最大边界左侧的位置(这里非常容易出错)，将当前值与arr[R]进行比较，
     * 如果当前值和基准值相等，则当前下标右移一位
     * 如果当前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
     * 如果当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
     * 最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边的下标，和arr[R]交换的位置就是等于区域右侧的下标
     * 过程：
     * 1、先假定arr[R]位置的数为比较的基准值，假定小于区域的最右侧边界为L-1，大于区域的最左侧边界为R
     * 2、从L开始到到最大边界左侧的位置(这里非常容易出错)，将当前值与arr[R]进行比较，
     * 3、如果当前值和基准值相等，则当前下标右移一位
     * 4、如果当前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
     * 5、如果当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
     * 6、最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边e下标，和arr[R]交换的位置就是等于区域右侧的下标
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public static int[] threePartition(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, L};
        }
        int pivot = arr[R];//保存一个基准值
        int lessRight = L - 1;//小于等于区域的最右侧边界，初始值为L-1(不包含数据)
        int moreLeft = R;//大于区域的最左侧边界，初始值为R(不包含数据)
        int index = L; // 当前位置
        while (index < moreLeft) { //当前位置从L出发，到最大边界左侧的位置(不是到R-1，这里非常容易出错)
            if (arr[index] == pivot) {
                // 当前位置和基准数据相等，当前位置右移一位
                index++;
            } else if (arr[index] < pivot) {
                //前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
                swap(arr, index, ++lessRight);
                index++;
            } else {
                // 当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
                swap(arr, index, --moreLeft);
            }
        }
        //最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边e下标，和arr[R]交换的位置就是等于区域右侧的下标
        swap(arr, moreLeft, R);
        return new int[]{lessRight + 1, moreLeft};
    }

2、快速排序的实现

2.1、二分区域实现的快速排序

• 利用二分区域的思想，将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，然后继续在这两侧进行划分，直到数组有序
• 最好时间复杂度：O(N*logN)
• 最差时间复杂度：O(N^2)
• 空间复杂度：O(1)

    /**
     * 二分区域实现的快速排序
     * 利用二分区域的思想，将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，然后继续在这两侧进行划分，直到数组有序
     * 最好时间复杂度：O(N*logN)
     * 最差时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     */
    public static void twoPartitionQuickSort(int[] arr, int L, int R) {
        if (L >= R || arr == null || arr.length < 2) {
            return;
        }
        // 利用二分区域的方法进行划分区域，获得等于基准值的位置
        int M = twoPartition(arr, L, R);
        // 递归排序小于区域
        twoPartitionQuickSort(arr, L, M - 1);
        // 递归排序大于区域
        twoPartitionQuickSort(arr, M + 1, R);
    }

2.1、三分区域实现的快速排序

• 利用三分区域的思想，将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，中间是等于某个数的，然后继续在这两侧进行划分，直到数组有序
• 最好时间复杂度：O(N*logN)
• 最差时间复杂度：O(N^2)
• 空间复杂度：O(1)

    /**
     * 三分区域实现的快速排序
     * 利用三分区域的思想，将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，中间是等于某个数的，然后继续在这两侧进行划分，直到数组有序
     * 最好时间复杂度：O(N*logN)
     * 最差时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     */
    public static void threePartitionQuickSort(int[] arr, int L, int R) {
        if (L >= R || arr == null || arr.length < 2) {
            return;
        }
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, L, R);
        // 递归排序小于区域
        threePartitionQuickSort(arr, L, equalArea[0] - 1);
        // 递归排序大于区域
        threePartitionQuickSort(arr, equalArea[1] + 1, R);
    }

2.1、改进后的三分区域实现的快速排序

• 快速排序如果一开始数据就是有序的，那其就是最差的时间复杂度的情形，时间复杂度为O(N^2)
• 这个时候，如果打乱其基准数据的选择，学术上通过证明，其时间复杂度就会收敛到O(N*logN)
• 所以在进行分区的时候，可以先在L…R范围内随机选择一个位置和arr[R]位置交换，然后用交换后的arr[R]进行分区

    /**
     * 改进后的三分区域实现：
     * 快速排序如果一开始数据就是有序的，那其就是最差的时间复杂度的情形，时间复杂度为O(N^2)
     * 这个时候，如果打乱其基准数据的选择，学术上通过证明，其时间复杂度就会收敛到O(N*logN)
     * 所以在进行分区的时候，可以先在L...R范围内随机选择一个位置和arr[R]位置交换，然后用交换后的arr[R]进行分区
     */
    public static void improvedThreePartition(int[] arr, int L, int R) {
        if (L > R || arr == null || arr.length < 2) {
            return;
        }
        // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, L, R);
        // 递归排序小于区域
        threePartitionQuickSort(arr, L, equalArea[0] - 1);
        // 递归排序大于区域
        threePartitionQuickSort(arr, equalArea[1] + 1, R);
    }

2.1、利用栈结构来实现非递归的快速排序

思路：

• 递归的本质就是程序调用栈记录了每次排序划分出来的中间位置M，然后递归程序让程序继续执行M左侧和右侧的数据，
• 如果我们自定义一个栈，用来保存中间的结果，这样就能不用递归实现快速排序，
    
  
  过程：
• 1、新建一个栈，用来保存每次生成的中间位置记录
• 2、每次执行了划分区域的函数后，我们将要继续执行的数据的左右侧下标位置压入栈中，
• 3、弹出栈中的数据，继续执行2的过程，直到栈为空

    /**
     * 利用栈结构来实现非递归的快速排序
     * 思路：
     * 递归的本质就是程序调用栈记录了每次排序划分出来的中间位置M，然后递归程序让程序继续执行M左侧和右侧的数据，
     * 如果我们自定义一个栈，用来保存中间的结果，这样就能不用递归实现快速排序，
     * 过程：
     * 1、新建一个栈，用来保存每次生成的中间位置记录
     * 2、每次执行了划分区域的函数后，我们将要继续执行的数据的左右侧下标位置压入栈中，
     * 3、弹出栈中的数据，继续执行2的过程，直到栈为空
     */
    public static void quickSortUnrecursiveWithStack(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
        swap(arr, (int) (Math.random() * (arr.length + 1)), arr.length);
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, 0, arr.length - 1);
        // 用来保存执行的结果
        Stack<QuickSortTempData> stack = new Stack<>();
        // 将新的划分区域压入堆栈中
        stack.push(new QuickSortTempData(0, equalArea[0] - 1));
        stack.push(new QuickSortTempData(equalArea[1] + 1, arr.length - 1));
        // 循环执行，直到栈为空
        while (!stack.isEmpty()) {
            // 弹出栈中的数据
            QuickSortTempData tempData = stack.pop();
            if (tempData.getLeft() < tempData.getRight()) { // 这一步判断一定要有，因为我们在压战的时候没有判断，所以这里要加，否则就会死循环
                // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
                swap(arr, tempData.getLeft() + (int) (Math.random() * (tempData.getRight() - tempData.getLeft() + 1)), tempData.getRight());
                // 利用三分区域的方法进行划分区域，获得等于基准值的位置
                equalArea = threePartition(arr, tempData.getLeft(), tempData.getRight());
                // 将新的划分区域压入堆栈中
                stack.push(new QuickSortTempData(tempData.getLeft(), equalArea[0] - 1));
                stack.push(new QuickSortTempData(equalArea[1] + 1, tempData.getRight()));
            }
        }
    }
/**
     * 非递归实现快速排序时保存分区结果的类
     */
    public static class QuickSortTempData {
        // 左侧区域的边界
        private final int left;
        // 右侧区域的边界
        private final int right;

        public QuickSortTempData(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public int getLeft() {
            return left;
        }

        public int getRight() {
            return right;
        }
    }

2.1、利用队列结构来实现非递归的快速排序

思路：

• 与利用栈结构实现非递归的快速排序类似，只是利用队列结构来实现非递归的快速排序，
• 既能用队列实现，也能用栈实现的原因是快速排序对左右两边的排序子过程不关注顺序。

 /**
     * 利用队列结构来实现非递归的快速排序
     * 思路：
     * 与利用栈结构实现非递归的快速排序类似，只是利用队列结构来实现非递归的快速排序，
     * 既能用队列实现，也能用栈实现的原因是快速排序对左右两边的排序子过程不关注顺序。
     */
    public static void quickSortUnrecursiveWithQueue(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
        swap(arr, (int) (Math.random() * (arr.length + 1)), arr.length);
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, 0, arr.length - 1);
        Queue<QuickSortTempData> queue = new LinkedList<>();
        // 将新的划分区域压入队列中
        queue.offer(new QuickSortTempData(0, equalArea[0] - 1));
        queue.offer(new QuickSortTempData(equalArea[1] + 1, arr.length - 1));
        while (!queue.isEmpty()) {
            QuickSortTempData tempData = queue.poll();
            if (tempData.getLeft() < tempData.getRight()) {
                // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
                swap(arr, tempData.getLeft() + (int) (Math.random() * (tempData.getRight() - tempData.getLeft() + 1)), tempData.getRight());
                // 利用三分区域的方法进行划分区域，获得等于基准值的位置
                equalArea = threePartition(arr, tempData.getLeft(), tempData.getRight());
                // 将新的划分区域压入队列中
                queue.offer(new QuickSortTempData(tempData.getLeft(), equalArea[0] - 1));
                queue.offer(new QuickSortTempData(equalArea[1] + 1, tempData.getRight()));
            }
        }
    }

/**
     * 非递归实现快速排序时保存分区结果的类
     */
    public static class QuickSortTempData {
        // 左侧区域的边界
        private final int left;
        // 右侧区域的边界
        private final int right;

        public QuickSortTempData(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public int getLeft() {
            return left;
        }

        public int getRight() {
            return right;
        }
    }

3、完整代码和测试程序

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 快速排序
 * 利用分治思想的实现排序的算法
 * 其基本思路是先将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，然后继续在这两侧进行划分，直到数组有序
 * 快速排序的最好时间复杂度为O(N*logN)，最差时间负责度为O(N^2)，空间复杂度为O(1)
 */
public class QuickSort {

    /**
     * 荷兰国旗问题-二分区域
     * 将一个数组arr[L...R]按照指定位置的数进行划分，小于等于的到左边，大于的到右边，最后返回这个指定值的位置
     * 思路：
     * 我们选定最右侧的一个数作为基准数据，先将arr[L...R-1]上的数与基准数arr[R]进行比较,小于等于的放到左侧，大于的放到右侧，再将大于区域最左边的数和arr[R]进行交换，这个位置下标就是返回值
     * 在划分的过程中，我们先假定一个小于等于的区域，最右侧边界的下标位置为L-1,即不包含任何区域上的数，从数组的L位置开始，到R-1位置进行和基准数字arr[R]比较，
     * 假设比较时当前位置为index,如果arr[index]<=arr[R],则将arr[index]与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
     * 如果arr[index]>arr[R],则当前下标右移一位
     * 这样做的目的是小于等于区域包含了最右侧的下标位置，并且小于等于区域的下一位就是大于区域的第一个位置，最后将其和arr[R]位置交换，就能得到最后的结果
     * 过程：
     * 1、先假定arr[R]位置的数为比较的基准值，假定小于等于区域的最右侧边界为L-1
     * 2、从L开始到R-1位置，将当前值与arr[R]进行比较，
     * 3、如果当前值小于等于基准值，则将当前值与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
     * 4、如果当前值大于基准值，则当前下标右移一位
     * 3、最后将小于等于区域的下一个位置的数和arr[R]位置交换，此时和arr[R]交换位置的下标就是二分区域的位置下标
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public static int twoPartition(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }
        int pivot = arr[R];// 保存一个基准值
        int lessRight = L - 1;// 小于等于区域的最右侧边界
        int index = L;// 当前位置
        while (index < R) {
            if (arr[index] <= pivot) {
                // 小于等于，将当前值与小于等于区域的下一个位置进行交换，小于等于区域右移一位，当前下标右移一位
                swap(arr, index, ++lessRight);
            }
            index++;
        }
        // 最后将小于等于区域的下一个位置的数和arr[R]位置交换
        swap(arr, ++lessRight, R);
        return lessRight;
    }

    /**
     * 荷兰国旗问题-三分区域
     * 将一个数组arr[L...R]按照指定位置的数进行划分，小于等于的到左边，等于的放到中间，大于的放到右边，最右返回等于区域的前后两个下标位置
     * 鉴于java语言的特性，我们返回一个长度为2的数组，0位置为等于区域左边的下标，1位置为等于区域右边的下标。
     * 思路：
     * 整体思路和二分区域的类似，先讲arr[R]位置的数作为基准值，将arr[L...R-1]上的数与基准数arr[R]进行比较,小于等于的放到左侧，等于的放中间，大于的放到右侧，最后将大于区域最左边的数和arr[R]进行交换
     * 在实际划分的过程中，我们要假定小于和大于两个区域，一开始小于区域最右侧下标为L-1(代表没有数据),大于区域最左侧下标为R(因为现在操作的是L...R-1,所以R位置代表没有数据)
     * 当前值从L开始，到最大边界左侧的位置(这里非常容易出错)，将当前值与arr[R]进行比较，
     * 如果当前值和基准值相等，则当前下标右移一位
     * 如果当前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
     * 如果当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
     * 最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边的下标，和arr[R]交换的位置就是等于区域右侧的下标
     * 过程：
     * 1、先假定arr[R]位置的数为比较的基准值，假定小于区域的最右侧边界为L-1，大于区域的最左侧边界为R
     * 2、从L开始到到最大边界左侧的位置(这里非常容易出错)，将当前值与arr[R]进行比较，
     * 3、如果当前值和基准值相等，则当前下标右移一位
     * 4、如果当前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
     * 5、如果当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
     * 6、最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边e下标，和arr[R]交换的位置就是等于区域右侧的下标
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     */
    public static int[] threePartition(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, L};
        }
        int pivot = arr[R];//保存一个基准值
        int lessRight = L - 1;//小于等于区域的最右侧边界，初始值为L-1(不包含数据)
        int moreLeft = R;//大于区域的最左侧边界，初始值为R(不包含数据)
        int index = L; // 当前位置
        while (index < moreLeft) { //当前位置从L出发，到最大边界左侧的位置(不是到R-1，这里非常容易出错)
            if (arr[index] == pivot) {
                // 当前位置和基准数据相等，当前位置右移一位
                index++;
            } else if (arr[index] < pivot) {
                //前值小于基准值，将当前值与小于区域右侧的下一个位置进行交换，小于区域右移一位，当前下标右移一位(这个过程可以将等于区域的值也右移)
                swap(arr, index, ++lessRight);
                index++;
            } else {
                // 当前值大于基准值，将当前值与大于区域的前一个位置进行交换，大于区域左移一位，当前下标不变(这个过程可以将大于区域换过来的数据继续比较)
                swap(arr, index, --moreLeft);
            }
        }
        //最后将大于区域最左边位置的数和arr[R]位置交换，此时小于区域最右侧的下一位就是等于区域左边e下标，和arr[R]交换的位置就是等于区域右侧的下标
        swap(arr, moreLeft, R);
        return new int[]{lessRight + 1, moreLeft};
    }

    /**
     * 二分区域实现的快速排序
     * 利用二分区域的思想，将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，然后继续在这两侧进行划分，直到数组有序
     * 最好时间复杂度：O(N*logN)
     * 最差时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     */
    public static void twoPartitionQuickSort(int[] arr, int L, int R) {
        if (L >= R || arr == null || arr.length < 2) {
            return;
        }
        // 利用二分区域的方法进行划分区域，获得等于基准值的位置
        int M = twoPartition(arr, L, R);
        // 递归排序小于区域
        twoPartitionQuickSort(arr, L, M - 1);
        // 递归排序大于区域
        twoPartitionQuickSort(arr, M + 1, R);
    }

    /**
     * 三分区域实现的快速排序
     * 利用三分区域的思想，将数组进行划分，划分成一侧是小于某个数的，一侧是大于某个数的，中间是等于某个数的，然后继续在这两侧进行划分，直到数组有序
     * 最好时间复杂度：O(N*logN)
     * 最差时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     */
    public static void threePartitionQuickSort(int[] arr, int L, int R) {
        if (L >= R || arr == null || arr.length < 2) {
            return;
        }
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, L, R);
        // 递归排序小于区域
        threePartitionQuickSort(arr, L, equalArea[0] - 1);
        // 递归排序大于区域
        threePartitionQuickSort(arr, equalArea[1] + 1, R);
    }

    /**
     * 改进后的三分区域实现：
     * 快速排序如果一开始数据就是有序的，那其就是最差的时间复杂度的情形，时间复杂度为O(N^2)
     * 这个时候，如果打乱其基准数据的选择，学术上通过证明，其时间复杂度就会收敛到O(N*logN)
     * 所以在进行分区的时候，可以先在L...R范围内随机选择一个位置和arr[R]位置交换，然后用交换后的arr[R]进行分区
     */
    public static void improvedThreePartition(int[] arr, int L, int R) {
        if (L > R || arr == null || arr.length < 2) {
            return;
        }
        // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, L, R);
        // 递归排序小于区域
        threePartitionQuickSort(arr, L, equalArea[0] - 1);
        // 递归排序大于区域
        threePartitionQuickSort(arr, equalArea[1] + 1, R);
    }

    /**
     * 非递归实现快速排序时保存分区结果的类
     */
    public static class QuickSortTempData {
        // 左侧区域的边界
        private final int left;
        // 右侧区域的边界
        private final int right;

        public QuickSortTempData(int left, int right) {
            this.left = left;
            this.right = right;
        }

        public int getLeft() {
            return left;
        }

        public int getRight() {
            return right;
        }
    }

    /**
     * 利用栈结构来实现非递归的快速排序
     * 思路：
     * 递归的本质就是程序调用栈记录了每次排序划分出来的中间位置M，然后递归程序让程序继续执行M左侧和右侧的数据，
     * 如果我们自定义一个栈，用来保存中间的结果，这样就能不用递归实现快速排序，
     * 过程：
     * 1、新建一个栈，用来保存每次生成的中间位置记录
     * 2、每次执行了划分区域的函数后，我们将要继续执行的数据的左右侧下标位置压入栈中，
     * 3、弹出栈中的数据，继续执行2的过程，直到栈为空
     */
    public static void quickSortUnrecursiveWithStack(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
        swap(arr, (int) (Math.random() * (arr.length + 1)), arr.length);
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, 0, arr.length - 1);
        // 用来保存执行的结果
        Stack<QuickSortTempData> stack = new Stack<>();
        // 将新的划分区域压入堆栈中
        stack.push(new QuickSortTempData(0, equalArea[0] - 1));
        stack.push(new QuickSortTempData(equalArea[1] + 1, arr.length - 1));
        // 循环执行，直到栈为空
        while (!stack.isEmpty()) {
            // 弹出栈中的数据
            QuickSortTempData tempData = stack.pop();
            if (tempData.getLeft() < tempData.getRight()) { // 这一步判断一定要有，因为我们在压战的时候没有判断，所以这里要加，否则就会死循环
                // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
                swap(arr, tempData.getLeft() + (int) (Math.random() * (tempData.getRight() - tempData.getLeft() + 1)), tempData.getRight());
                // 利用三分区域的方法进行划分区域，获得等于基准值的位置
                equalArea = threePartition(arr, tempData.getLeft(), tempData.getRight());
                // 将新的划分区域压入堆栈中
                stack.push(new QuickSortTempData(tempData.getLeft(), equalArea[0] - 1));
                stack.push(new QuickSortTempData(equalArea[1] + 1, tempData.getRight()));
            }
        }
    }

    /**
     * 利用队列结构来实现非递归的快速排序
     * 思路：
     * 与利用栈结构实现非递归的快速排序类似，只是利用队列结构来实现非递归的快速排序，
     * 既能用队列实现，也能用栈实现的原因是快速排序对左右两边的排序子过程不关注顺序。
     */
    public static void quickSortUnrecursiveWithQueue(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
        swap(arr, (int) (Math.random() * (arr.length + 1)), arr.length);
        // 利用三分区域的方法进行划分区域，获得等于基准值的位置
        int[] equalArea = threePartition(arr, 0, arr.length - 1);
        Queue<QuickSortTempData> queue = new LinkedList<>();
        // 将新的划分区域压入队列中
        queue.offer(new QuickSortTempData(0, equalArea[0] - 1));
        queue.offer(new QuickSortTempData(equalArea[1] + 1, arr.length - 1));
        while (!queue.isEmpty()) {
            QuickSortTempData tempData = queue.poll();
            if (tempData.getLeft() < tempData.getRight()) {
                // 随机选一个数和R位置的数交换,让复杂度接近O(N*logN)
                swap(arr, tempData.getLeft() + (int) (Math.random() * (tempData.getRight() - tempData.getLeft() + 1)), tempData.getRight());
                // 利用三分区域的方法进行划分区域，获得等于基准值的位置
                equalArea = threePartition(arr, tempData.getLeft(), tempData.getRight());
                // 将新的划分区域压入队列中
                queue.offer(new QuickSortTempData(tempData.getLeft(), equalArea[0] - 1));
                queue.offer(new QuickSortTempData(equalArea[1] + 1, tempData.getRight()));
            }
        }
    }

    /**
     * 用对数器的方法测试
     */
    public static void main(String[] args) {
        // 测试次数
        int testTime = 500000;
        // 数组最大长度
        int maxSize = 100;
        // 数组最大值
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            // 先生成一个随机的数组
            int[] arr = generateRandomArr(maxSize, maxValue);
            //printArray(arr);
            if (arr.length < 2) {
                continue;
            }
            // 复制一个数组,用来做对照
            int[] arrComparator = copyArr(arr);
            // 系统排序,比较器
            sortComparator(arrComparator);
            // 二分法实现的快速排序
            int[] arr1 = copyArr(arr);
            twoPartitionQuickSort(arr1, 0, arr.length - 1);
            if (!isEqual(arr1, arrComparator)) {
                succeed = false;
                System.out.println("原数组：");
                printArray(arr);
                System.out.println("系统排序后：");
                printArray(arrComparator);
                System.out.println("二分法实现快速排序后：");
                printArray(arr1);
                break;
            }
            // 三分法实现的快速排序
            int[] arr2 = copyArr(arr);
            threePartitionQuickSort(arr2, 0, arr.length - 1);
            if (!isEqual(arr2, arrComparator)) {
                succeed = false;
                System.out.println("原数组：");
                printArray(arr);
                System.out.println("系统排序后：");
                printArray(arrComparator);
                System.out.println("三分法实现快速排序后：");
                printArray(arr2);
                break;
            }
            // 改进后的三分法实现的快速排序
            int[] arr3 = copyArr(arr);
            improvedThreePartition(arr3, 0, arr.length - 1);
            if (!isEqual(arr3, arrComparator)) {
                succeed = false;
                System.out.println("原数组：");
                printArray(arr);
                System.out.println("系统排序后：");
                printArray(arrComparator);
                System.out.println("改进后的三分法实现快速排序后：");
                printArray(arr3);
                break;
            }
            // 利用栈实现的非递归的快速排序
            int[] arr4 = copyArr(arr);
            quickSortUnrecursiveWithStack(arr4);
            if (!isEqual(arr4, arrComparator)) {
                succeed = false;
                System.out.println("原数组：");
                printArray(arr);
                System.out.println("系统排序后：");
                printArray(arrComparator);
                System.out.println("利用栈实现的非递归的快速排序后：");
                printArray(arr4);
                break;
            }
            // 利用队列实现的非递归的快速排序
            int[] arr5 = copyArr(arr);
            quickSortUnrecursiveWithQueue(arr5);
            if (!isEqual(arr5, arrComparator)) {
                succeed = false;
                System.out.println("原数组：");
                printArray(arr);
                System.out.println("系统排序后：");
                printArray(arrComparator);
                System.out.println("利用队列实现的非递归的快速排序后：");
                printArray(arr5);
                break;
            }

        }
        System.out.println(succeed ? "successful!" : "error!");
    }

    /**
     * 生成随机数组
     * 长度是[0,maxSize]
     * 每个值是[-maxValue,maxValue]
     *
     * @param maxSize  数组最大长度
     * @param maxValue 数组最大值
     * @return 随机数组
     */
    public static int[] generateRandomArr(int maxSize, int maxValue) {
        // Math.random() -> [0,1) 所有的小数，等概率返回一个
        // Math.random() * N -> [0,N) 所有小数，等概率返回一个
        // (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个
        // (int)(Math.random() * (maxSize + 1)) -> [0,maxSize] 所有的整数，等概率返回一个
        int size = (int) (Math.random() * (maxSize + 1));
        int[] arr = new int[size];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * maxValue);
        }
        return arr;
    }

    /**
     * 复制数组
     *
     * @param arr 原数组
     * @return 复制数组
     */
    public static int[] copyArr(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    /**
     * 比较数组是否相等
     *
     * @param arr1 数组1
     * @param arr2 数组2
     * @return 是否相等
     */
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1 == null || arr2 == null) {
            return false;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    /**
     * 获取的系统排序的对数器，用来验证自己的排序是不是正确的参照
     *
     * @param arr 数组
     */
    public static void sortComparator(int[] arr) {
        Arrays.sort(arr);
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j || i > arr.length - 1 || j > arr.length - 1) {
            return;
        }
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }
}

---

后记
  个人学习总结笔记，不能保证非常详细，轻喷