使用 Java 实现快速排序（递归+非递归）

快速排序 (Quick Sort)

快速排序用到了分治思想，同样的还有归并排序。乍看起来快速排序和归并排序非常相似，都是将问题变小，先排序子串，最后合并。不同的是快速排序在划分子问题的时候经过多一步处理，将划分的两组数据划分为一大一小，这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此，划分的不定性使得快速排序的时间复杂度并不稳定。

快速排序的基本思想：通过一趟排序将待排序列分隔成独立的两部分，其中一部分记录的元素均比另一部分的元素小，则可分别对这两部分子序列继续进行排序，以达到整个序列有序。

算法步骤

快速排序使用分治法 open in new window（Divide and conquer）策略来把一个序列分为较小和较大的 2 个子序列，然后递归地排序两个子序列。具体算法描述如下：

1. 从序列中随机挑出一个元素，做为 “基准”(pivot)；
2. 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个操作结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。

注意，实现快速排序的时候一定要实现分区操作。

递归版本

public class Solution {

    // partition 方法用于快速排序中的分区操作
    // 它将数组 array 从 low 到 high 之间的元素进行排序，以 pivot 为基准
    // 返回分区后基准元素的新位置
    public static int partition(int[] array, int low, int high) {
        // 选择分区的基准元素，这里选择数组的最后一个元素
        int pivot = array[high];
        // 初始化指向分区边界的指针
        int pointer = low;
        // 从 low 到 high - 1 进行遍历
        for (int i = low; i < high; i++) {
            // 如果当前元素小于等于基准元素，则交换当前元素和 pointer 指向的元素，并将 pointer 向前移动
            if (array[i] <= pivot) {
                // 交换 array[i] 和 array[pointer]
                int temp = array[i];
                array[i] = array[pointer];
                array[pointer] = temp;
                pointer++;
            }
        }
        // 将基准元素放到正确的位置，即 pointer 指向的位置
        int temp = array[pointer];
        array[pointer] = array[high];
        array[high] = temp;
        // 返回基准元素的位置
        return pointer;
    }

    // quickSort 方法用于快速排序，递归地对数组进行排序
    // 从 low 到 high 之间的元素被排序
    public static void quickSort(int[] array, int low, int high) {
        // 如果 low 小于 high，则进行排序
        if (low < high) {
            // 进行分区，得到分区位置
            int position = partition(array, low, high);
            // 对分区位置左边的元素进行递归排序
            quickSort(array, low, position - 1);
            // 对分区位置右边的元素进行递归排序
            quickSort(array, position + 1, high);
        }
    }

    // main 方法是程序的入口点
    public static void main(String[] args) {
        // 初始化一个整数数组
        int[] arr = {5, 3, 6, 7, 2, 4, 1, 32, 67, 10, 45};
        // 对整个数组进行快速排序
        quickSort(arr, 0, arr.length - 1);
        // 遍历排序后的数组并打印每个元素
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }
}

非递归版本

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Solution {

    /**
     * partition 方法用于快速排序中的分区操作
     * 它将数组 array 从 low 到 high 之间的元素进行排序，以 pivot 为基准
     * 返回分区后基准元素的新位置
     *
     * @param array 需要分区的数组
     * @param low   分区的起始索引
     * @param high  分区的结束索引
     * @return 分区后基准元素的新位置
     */
    public static int partition(int[] array, int low, int high) {
        // 选择分区的基准元素，这里选择数组的最后一个元素
        int pivot = array[high];
        // 初始化指向分区边界的指针
        int pointer = low;
        // 从 low 到 high - 1 进行遍历
        for (int i = low; i < high; i++) {
            // 如果当前元素小于等于基准元素，则交换当前元素和 pointer 指向的元素，并将 pointer 向前移动
            if (array[i] <= pivot) {
                // 交换 array[i] 和 array[pointer]
                int temp = array[i];
                array[i] = array[pointer];
                array[pointer] = temp;
                pointer++;
            }
        }
        // 将基准元素放到正确的位置，即 pointer 指向的位置
        int temp = array[pointer];
        array[pointer] = array[high];
        array[high] = temp;
        // 返回基准元素的位置
        return pointer;
    }

    /**
     * quickSort 方法用于快速排序
     * 使用分治法策略对数组进行排序
     *
     * @param a    需要排序的数组
     * @param low  排序的起始索引
     * @param high 排序的结束索引
     */
    public static void quickSort(int[] a, int low, int high) {
        // 如果分区的起始索引大于或等于结束索引，则不需要排序
        if (low >= high)
            return;
        // 使用栈来存储待处理的分区
        Deque<Integer> stack = new LinkedList<Integer>();
        // 将第一个分区入栈
        stack.addLast(low);
        stack.addLast(high);
        while (!stack.isEmpty()) {
            // 从栈中弹出一个分区
            high = stack.pollLast();
            low = stack.pollLast();
            // 执行分区操作，并获得分区的枢纽元素索引
            int pivot = partition(a, low, high);
            // 将左边分区的结束索引和起始索引入栈，以便后续处理
            if (low < pivot - 1) {
                stack.addLast(low);
                stack.addLast(pivot - 1);
            }
            // 将右边分区的起始索引和结束索引入栈，以便后续处理
            if (pivot + 1 < high) {
                stack.addLast(pivot + 1);
                stack.addLast(high);
            }
        }
    }

    /**
     * main 方法是程序的入口点
     * 它创建一个整数数组，调用 quickSort 方法对其进行排序，然后打印排序后的结果
     *
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 创建一个整数数组
        int[] arr = {5, 3, 6, 7, 2, 4, 1, 32, 67, 10, 45};
        // 对数组进行快速排序
        quickSort(arr, 0, arr.length - 1);
        // 遍历排序后的数组并打印每个元素
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }
}