【算法100天 | 15】快速排序的非递归写法（Java实现）

女爷i 2023-09-24 13:50 16阅读 0赞

#### 文章目录 ####

*   *  一、快速排序（递归版）
     *   *  1、思想
         *  2、代码
     *  二、归并排序（迭代版）
     *   *  1、思路
         *  2、代码

### 一、快速排序（递归版） ###

#### 1、思想 ####

从基准元素比较后的结果来看，快速排序分为两种实现：

*  分两块：小于等于x的放左边，=x的在左边的最后面，大于x的放右边
 *  分三块：小于x的放左边，=x的放中间，大于x的放右边

我们这里聊一下分三块（小于x的放左边，=x的放中间，大于x的放右边）的实现；

> 选择一个基准元素，通常选择第一个元素或者最后一个元素，通过一趟扫描，将待排序列分成三部分：一部分比基准元素小,一部分等于基准元素，一部分等大于基准元素，此时基准元素所在的范围就是排序后基准元素应该在的问题。

复杂度分析：

*  空间复杂度：O(logn) — 递归的空间复杂度，每次要记录=x的范围
 *  时间复杂度：O（nlogn）

#### 2、代码 ####

/**
     * 方法二：
     * 分三块：小于x的放左边，=x的放中间，大于x的放右边
     */
    public void quickSort(int[] arr) {
        
        if (arr == null || arr.length < 2) {
        
            return;
        }
        process(arr, 0, arr.length - 1);
    }
    
    // 每次改变x的值可以最终确定排序有序
    private void process(int[] arr, int L, int R) {
        
        if (L >= R) {
        
            return;
        }
        // 等于x区域的范围：[equalArea[0], equalArea[1]]
        int[] equalArea = netherlandsFlag(arr, L, R);
        process(arr, L, equalArea[0] - 1);
        process(arr, equalArea[1] + 1, R);
    }
    
    /**
     * 荷兰国旗问题，返回数组arr中[left, right]范围中 等于arr[right]的数在数组中的索引位置区间。
     */
    private int[] netherlandsFlag(int[] arr, int left, int right) {
        
        if (left > right) {
        
            return new int[]{
        -1, -1};
        }
        if (left == right) {
        
            return new int[]{
        left, right};
        }
        // < arr[R] 区域的右边界
        int less = left - 1;
        // > arr[R] 区域的左边界
        int more = right;
        // 遍历数组
        int index = left;
        while (index < more) {
        
            // 如果数组中的数 = arr[R]，直接遍历下一个数
            if (arr[index] == arr[right]) {
        
                index++;
            } else if (arr[index] < arr[right]) {
        
                // 如果数组中的数 < arr[R]：移动 < arr[R] 区域的右边界、交换右边界后一个数和当前数，遍历下一个数
                swap(arr, index++, ++less);
            } else {
        
                // 如果数组中的数 > arr[R]：移动 > arr[R] 区域的左边界、交换左边界前一个数和当前数，继续遍历交换后的当前数
                swap(arr, index, --more);
            }
        }
        // 最后将arr[R]位置的数字交换到> arr[R] 区域的左边界more，此时=arr[R]的数索引位置为[less + 1, more]
        swap(arr, more, right);
        return new int[]{
        less + 1, more};
    }

我们都知道快速排序的时间复杂度：O(nlogn)，空间复杂度：O(logn)；但从递归版本的代码我们不太好看出这个时间复杂度为什么为O(nlogn)，下面看迭代版本的代码，时间复杂度就很清晰。

### 二、归并排序（迭代版） ###

#### 1、思路 ####

在递归版版本中有一个在线程栈中隐式的保存< x的递归方法、> x的递归方法；所以要提供一个显式的栈保存这两部分。

#### 2、代码 ####

/**
         * 非递归的辅助类
         */
        class Op {
        
            public int l;
            public int r;
    
            public Op(int left, int right) {
        
                l = left;
                r = right;
            }
        }
    
        // 快排-非递归版本
        public void quickSort(int[] arr) {
        
            if (arr == null || arr.length < 2) {
        
                return;
            }
            int N = arr.length;
            int[] equalArea = netherlandsFlag(arr, 0, N - 1);
            int el = equalArea[0];
            int er = equalArea[1];
            // 代替递归版本的栈
            Stack<Op> stack = new Stack<>();
            stack.push(new Op(0, el - 1));
            stack.push(new Op(er + 1, N - 1));
            while (!stack.isEmpty()) {
        
                Op op = stack.pop(); // op.l  ... op.r
                if (op.l < op.r) {
        
                    equalArea = netherlandsFlag(arr, op.l, op.r);
                    el = equalArea[0];
                    er = equalArea[1];
                    stack.push(new Op(op.l, el - 1));
                    stack.push(new Op(er + 1, op.r));
                }
            }
        }
    
        /**
         * 荷兰国旗问题，返回数组arr中[left, right]范围中 等于arr[right]的数在数组中的索引位置区间。
         */
        private int[] netherlandsFlag(int[] arr, int left, int right) {
        
            if (left > right) {
        
                return new int[]{
        -1, -1};
            }
            if (left == right) {
        
                return new int[]{
        left, right};
            }
            // < arr[R] 区域的右边界
            int less = left - 1;
            // > arr[R] 区域的左边界
            int more = right;
            // 遍历数组
            int index = left;
            while (index < more) {
        
                // 如果数组中的数 = arr[R]，直接遍历下一个数
                if (arr[index] == arr[right]) {
        
                    index++;
                } else if (arr[index] < arr[right]) {
        
                    // 如果数组中的数 < arr[R]：移动 < arr[R] 区域的右边界、交换右边界后一个数和当前数，遍历下一个数
                    swap(arr, index++, ++less);
                } else {
        
                    // 如果数组中的数 > arr[R]：移动 > arr[R] 区域的左边界、交换左边界前一个数和当前数，继续遍历交换后的当前数
                    swap(arr, index, --more);
                }
            }
            // 最后将arr[R]位置的数字交换到> arr[R] 区域的左边界more，此时=arr[R]的数索引位置为[less + 1, more]
            swap(arr, more, right);
            return new int[]{
        less + 1, more};
        }
    
        private void swap(int[] arr, int i, int j) {
        
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }