912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

两种方法很重要，一个是快速排序，一个是归并排序。本题归并排序用时远远低于快速排序，内存也差不多。

快速排序-分治-

随机化选择主元并划分数组，返回主元的最终索引位置，对主元左侧的子数组进行递归排序，对主元右侧的子数组进行递归排序。

快速排序反而有点分治的思想，即先确定一个元素的正确位置，这个元素前面的数都比它小，后面的数都比它大。然后再去以同样的方法去排序子数组。

如何确定这个元素的位置呢？先随机取数组的一个索引，然后把它对应的元素和数组的最后一个元素换一下位置， 这样它就在最后了，然后用双指针的方法把它前面的元素分到两个连续的区间里，第一个区间里的元素都小于它， 第二个区间里的元素都大于它，注意这两个区间里的元素未必有序。分完之后再把它和第二个区间里的第一个元素交换一下就把它放到了正确的位置。

    public void quickSort(int[] arr, int low, int high) {
        // low,high 为每次处理数组时的首、尾元素索引
        //当low==high是表示该序列只有一个元素，不必排序了
        if (low >= high) {
            return;
        }
        
        // 选出哨兵元素和基准元素。这里左边的哨兵元素也是基准元素
        // 选择最左端元素为基准元素的话，一定要先处理 j，再处理 i
        int i = low, j = high, base = arr[low];
        while (i < j) {
            // 右边哨兵从后向前找
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 左边哨兵从前向后找
            while (arr[i] < base && i < j) {
                i++;
            }
            swap(arr,i,j);  // 交换元素
        }
        swap(arr,low,j);  // 基准元素与哨兵交换
        
        // 递归调用，排序左子集合和右子集合。j位置的元素已确定。
        quickSort(arr,low,j-1);  
        quickSort(arr,j+1,high);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

• 时间复杂度：基于随机选取主元的快速排序时间复杂度为期望 $O(n\log n)$，其中 n 为数组的长度。详细证明过程可以见《算法导论》第七章，这里不再大篇幅赘述。
• 空间复杂度：O(h)，其中 h 为快速排序递归调用的层数。我们需要额外的 O(h) 的递归调用的栈空间，由于划分的结果不同导致了快速排序递归调用的层数也会不同，最坏情况下需 O(n) 的空间，最优情况下每次都平衡，此时整个递归树高度为 log⁡ n，空间复杂度为 O(log⁡n)。

归并排序（分治排序）

递归的终止条件，当子序列只包含一个元素时，认为它已经排序。计算中点，用于将数组分成两部分，递归地对左半部分进行归并排序， 递归地对右半部分进行归并排序，合并两个已排序的子序列。

归并排序有点类似递归，就是把数组平分，然后先把子数组排好序（递归调用），再合并排序好的子数组。

class Solution {
    // 临时数组，用于归并过程中存储合并后的序列
    int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length]; // 初始化临时数组的大小与输入数组相同
        mergeSort(nums, 0, nums.length - 1); // 调用归并排序的递归函数
        return nums; // 返回排序后的数组
    }

    // 归并排序的递归函数
    public void mergeSort(int[] nums, int l, int r) {
        // 递归的终止条件，当子序列只包含一个元素时，认为它已经排序
        if (l >= r) {
            return;
        }
        
        // 计算中点，用于将数组分成两部分
        int mid = (l + r) >> 1;
        // 递归地对左半部分进行归并排序
        mergeSort(nums, l, mid);
        // 递归地对右半部分进行归并排序
        mergeSort(nums, mid + 1, r);
        
        // 合并两个有序数组
        // i 和 j 分别是左右子序列的起始索引
        int i = l, j = mid + 1;
        // cnt 用于在临时数组 tmp 中追踪当前填充的位置
        int cnt = 0;
        // 遍历两个子序列，将较小的元素依次移动到 tmp 数组中
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                tmp[cnt++] = nums[i++];
            } else {
                tmp[cnt++] = nums[j++];
            }
        }
        
        // 将左子序列剩余的元素复制到 tmp 数组
        while (i <= mid) {
            tmp[cnt++] = nums[i++];
        }
        // 将右子序列剩余的元素复制到 tmp 数组
        while (j <= r) {
            tmp[cnt++] = nums[j++];
        }
        
        // 将排序后的临时数组复制回原数组中对应的位置，注意原数组是[l,r]，tmp是[0,r-l]。重点。
        for (int k = 0; k < r - l + 1; ++k) {
            nums[l + k] = tmp[k];
        }
    }
}

• 时间复杂度：O(nlog n)。由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要 O(n) 的时间复杂度，所以我们可以列出归并排序运行时间 T(n) 的递归表达式：

$$T(n)=2T(n/2)+O(n)$$

根据主定理我们可以得出归并排序的时间复杂度为 O(nlog n)。

也可以想象一颗二叉树，树的高度为 $\log n$，每层的节点数为 $n$，总时间就是遍历这颗树的时间，即 $O(n\log n)$。

• 空间复杂度：O(n)。我们需要额外 O(n) 空间的 tmp 数组，且归并排序递归调用的层数最深为 $\log_2 n$， 所以我们还需要额外的 $O(\log n)$ 的栈空间，所需的空间复杂度即为 $O(n+\log n)=O(n)$。

堆排序

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums); // 调用堆排序
        return nums; // 返回排序后的数组
    }

    // 堆排序函数
    public void heapSort(int[] nums) {
        int len = nums.length - 1;
        // 构建最大堆。最大堆只能告诉我们最大值，不能告诉我们次大值，因为无法确定左右子节点的大小
        buildMaxHeap(nums, len);
        
        // 通过不断减小堆的大小并调用maxHeapify来完成排序
        for (int i = len; i >= 1; --i) {
            swap(nums, i, 0); // 将当前最大的元素移至数组末，nums[0]是最大元素。
            // 重新调整堆，保持最大堆的特性
            maxHeapify(nums, 0, --len);
        }
    }

    // 构建最大堆
    public void buildMaxHeap(int[] nums, int len) {
        // 从最后一个非叶子节点开始向上构建最大堆
        for (int i = (len - 1) / 2; i >= 0; --i) {
            maxHeapify(nums, i, len);
        }
    }
    
    // 把子树变成最大堆
    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2; // 左右子节点的索引，索引是从0开始的，如果是从1开始的，则是i*2, i*2+1
        int largest = i; // 假设当前节点是最大值
        
        // 如果左子节点更大，更新最大值的索引
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        }
        // 如果右子节点更大，更新最大值的索引
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        // 如果最大值不是当前节点，将其与最大子节点交换
        if (largest != i) {
            swap(a, i, largest); // 注意这里只是交换了数组中的元素，即large还是指向子节点。
            // 对交换后可能违反最大堆性质的子树进行调整
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        // 交换两个元素
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

• 时间复杂度：$O(n\log n)$。初始化建堆的时间复杂度为 $O(n)$，建完堆以后需要进行 $n-1$ 次调整， 一次调整（即 maxHeapify） 的时间复杂度为 $O(\log n)$，那么 $n-1$ 次调整即需要 $O(n\log n)$ 的时间复杂度。 因此，总时间复杂度为 $O(n+n\log n)=O(n\log n)$。

maxHeapify的时间复杂度是O(\log n)，因为交换后，它只会递归处理较小的那个子节点的树。即每层只进入一个子节点。

buildMaxHeap的时间复杂度为什么不是 $O(n \log n)$ 而是 $O(n)$ 呢？ 因为第 k 层的节点数量为 $n/2^(k+1)$，每个节点的高度为 k。因此，调用 maxHeapify 所需的总时间是这些节点所需时间的总和。即

$$T(n) = \sum_{k=0}^{\log n-1} \frac{n}{2^{k+1}}O(\log n-k)\\ \approx n \sum_{k=0}^{\log n - 1} \frac{\log n - k}{2^{k+1}}$$

• 空间复杂度：O(1)。只需要常数的空间存放若干变量。