⭐ 题目日期：

腾讯 - 2024/10/11

！！！对快速排序比较陌生的朋友，请查阅：七大常见排序中的快速排序

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

先回顾一下用递归实现快速排序：

1. 选择基准
2. 线性扫描数组，将比基准小的元素排在基准左边，比基准大的元素排在基准右边
3. 在分好的片区里(比基准小片区 ｜ 比基准大片区)，递归重复以上步骤，直到分解的小片区元素的个数为0或1，此时分片区自动有序。

💻代码 1：

Java

	public int[] quickSort(int[] array) {
        if (array == null || array.length == 0) {
            return array;
        }
        quickSortRecursive(array, 0, array.length - 1);
        return array;
    }

    private void quickSortRecursive(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(array, left, right);
        quickSortRecursive(array, left, pivotIndex - 1);
        quickSortRecursive(array, pivotIndex + 1, right);
    }

    private int partition(int[] array, int left, int right) {
	// 总是选择最右边的元素作为基准，也可产生一个随机数来决定基准的位置
        int pivot = array[right];
        int i = left;
        int j = right - 1;
        while (i <= j) {
            if (array[i] <= pivot) {
                i++;
            } else {
                swap(array, i, j);
                j--;
            }
        }
        swap(array, i, right);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

用非递归的方式实现快速排序，需要用数据结构栈来模拟递归栈的调用。通过以上代码得知，递归调用传了3个参数：array, leftIndex, rightIndex。当用迭代的方法解题，由于array可以随时拿到，因此只需将左右边界加入栈中。

💻代码 2：

Java

    public int[] sortArray(int[] array) {
        if (array == null || array.length == 0) {
            return array;
        }
        Deque<int[]> stack = new LinkedList<>();
	// 用于在区间[left, right], 随机选择一个基准 pivot
        Random random = new Random();
        stack.offerLast(new int[]{0, array.length - 1});
        while (!stack.isEmpty()) {
            int[] interval = stack.pollLast();
            int left = interval[0];
            int right = interval[1];
            int pivot = partition(array, left, right, random);
            if (pivot + 1 < right) {
                stack.offerLast(new int[]{pivot + 1, right});
            }
            if (left < pivot - 1) {
                stack.offerLast(new int[]{left, pivot - 1});
            }
        }
        return array;
    }

    private int partition(int[] array, int left, int right, Random random) {
        swap(array, random.nextInt(left, right + 1), right);
        int pivot = array[right];
        int i = left;
        int j = right - 1;
        while (i <= j) {
            if (array[i] <= pivot) {
                i++;
            } else {
                swap(array, i, j);
                j--;
            }
        }
        swap(array, i, right);
        return i;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

🚵🏻复杂度分析：

时间复杂度跟递归法一样，空间复杂度由递归栈变为栈

时间复杂度：平均时间复杂度：O(nlogn) 最坏：O(n^2)

空间复杂度：平均：O(logn) 最坏：O(n)