🌕 🌕 🌕 912. 排序数组

难度: 🌕 🌕 🌕

问题描述

---

解法 1 - 快排

• 时间复杂度：
  • best = O(nlog n)
  • avg = O(nlog n)
  • worst = O(n^2) [完全逆序]
• 空间复杂度
  • O(log n) [堆栈空间调用]
• 不稳定 [若数组中两个元素相等，经过排序后，这两个元素相对顺序可能发生改变]

class Solution {
    public int[] sortArray(int[] nums) {
        // 思路:
        // method 1 : 快排
        int len = nums.length;
        mySol(nums, 0, len - 1);
        return nums;
    }

    private void mySol(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return;
        }
        // left < right
        // 以左端点的值作为基准点
        // 比它小的都在左边，比它大的都在右边
        int moniotr = nums[left];
        int i = left;
        int j = right;
        while(i < j) {
            // 反方向，从 右 => 左 找比基准值小的数
            while(i < j && nums[j] >= moniotr) {
                j --;
            }
            // 从 左 => 右 找比基准值大的数
            while(i < j && nums[i] <= moniotr) {
                i ++;
            }
            // 交换
            swap(nums, i, j);
        }
        // i == j
        swap(nums, i, left);
        // 递归
        mySol(nums, left, i - 1);
        mySol(nums, i + 1, right);
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

---

输出 1

---

解法 2 - 归并排序

• 时间复杂度：
  • best = O(nlog n)
  • avg = O(nlog n) [每一层复杂度均为 O(n) * 总层数 log n]
  • worst = O(nlog n)
• 空间复杂度
  • O(n)
• 不稳定

class Solution {
    public int[] sortArray(int[] nums) {
        // 思路：
        // method 2 - 归并排序
        int len = nums.length;
        divide(nums, 0, len - 1);
        return nums;
    }

    // 分治
    private void divide(int[] nums, int left, int right) {
        // 递归终止条件
        if(left >= right) {
            return;
        }
        // left < right
        int mid = left + ((right - left) >> 1);
        divide(nums, left, mid);
        divide(nums, mid + 1, right);
        // 合并
        merge(nums, left, mid, right);
    }

    // 合并
    private void merge(int[] nums, int left, int mid, int right) {
        int[] res = new int[right - left + 1]; // 暂存排序好的数组
        // 双指针法进行合并
        int i = left; // 左数组首元素下标
        int j = mid + 1; // 右数组首元素下标
        int index = 0; // res 当前下标
        while(i <= mid && j <= right) {
            if(nums[i] <= nums[j]) {
                res[index] = nums[i];
                index ++;
                i ++;
            } else {
                res[index] = nums[j];
                index ++;
                j ++;
            }
        }
        // 判断是否还有某侧数组没有添加完
        while(i <= mid) {
            res[index] = nums[i];
            index ++;
            i ++;
        }
        while(j <= right) {
            res[index] = nums[j];
            index ++;
            j ++;
        }
        for(int m = left; m <= right; m ++) {
            nums[m] = res[m - left];
        }
    }
}

---

输出 2

---

解法 3 - 堆排（大根堆）

大根堆 ： 堆顶元素 >= 堆里其他元素

• 时间复杂度：
  • best = O(nlog n)
  • avg = O(nlog n) [每个元素 建堆 / 弹出 复杂度均为 O(log n) * 总元素数 n]
  • worst = O(nlog n)
• 空间复杂度
  • O(1) [原数组原地交换]
• 不稳定

class Solution {
    public int[] sortArray(int[] nums) {
        // 思路：
        // method 3 :建立大根堆
        int len = nums.length;
        // 建立大根堆
        build(nums);
        // 依次将大根堆堆顶元素放到数组末尾
        for(int i = len - 1; i > 0; i --) {
            swap(nums, 0, i);
            // 取走堆顶元素后重新调整，使得剩下元素仍组成一个大根堆
            // 最后一个元素下标为 i，被堆顶元素取代后，不计入 endIndex 范围
            // 所以 endIndex = i - 1
            resize(nums, 0, i - 1);
        }
        return nums;
    }

    private void build(int[] nums) {
        int len = nums.length;
        // 遍历所有元素，一个个添加到已经构建好的大根堆中，形成更大的大根堆
        for(int i = 1; i < len; i ++) {
            int curIndex = i;
            int curVal = nums[i]; // 当前要加入大根堆的元素
            int parentIndex = (curIndex - 1) >> 1; // 父节点的下标
            // 判断是否需要上浮
            while(curIndex > 0 && parentIndex >= 0 && curVal > nums[parentIndex]) {
                swap(nums, curIndex, parentIndex);
                curIndex = parentIndex;
                curVal = nums[curIndex];
                parentIndex = (curIndex - 1) >> 1; // 新的父节点下标
            }
        }
    }

    private void resize(int[] nums, int curIndex, int endIndex) {
        // 判断当前元素所在位置，是否仍是一个大根堆
        // 若不是，则需要进行下沉
        // 边界值 endIndex
        int leftIndex = 2 * curIndex + 1; // 左子节点下标
        int rightIndex = 2 * curIndex + 2; 
        // 判断是否还有子节点
        if(leftIndex > endIndex) {
            return;
        }
        // leftIndex <= endIndex => 至少还有一个左孩子需要判断比较
        // 由于大根堆任何一个节点作为堆顶，均比其他元素大，
        // 因此只需比较当前节点 & 它左右子节点的值，即可，不可能是孙子辈节点
        int maxChildIndex = leftIndex;
        // 判断右孩子是否也需要加入比较范围
        if(rightIndex <= endIndex) {
            if(nums[rightIndex] > nums[leftIndex]) {
                maxChildIndex = rightIndex;
            }
        }
        // 判断 当前节点是否比 拥有最大值的孩子节点值要大
        // 如果 <，则需要下沉
        if(nums[curIndex] < nums[maxChildIndex]) {
            // 下沉
            swap(nums, curIndex, maxChildIndex);
            curIndex = maxChildIndex;
            resize(nums, curIndex, endIndex);
        }
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}

---

输出