leetcode912.md

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 <= 50000
• -50000 <= nums[i] <= 50000

思路

1、冒泡排序

实现

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  const { length: len } = nums;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }

  return nums;
};

实现-复杂度分析
时间复杂度：O(n^2)，两个 for 循环嵌套，即 n^2
空间复杂度：O(1)，这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)

官方

// java
class Solution {
  public int[] sortArray(int[] nums) {
    randomizedQuicksort(nums, 0, nums.length - 1);
    return nums;
  }

  public void randomizedQuicksort(int[] nums, int l, int r) {
    if (l < r) {
      int pos = randomizedPartition(nums, l, r);
      randomizedQuicksort(nums, l, pos - 1);
      randomizedQuicksort(nums, pos + 1, r);
    }
  }

  public int randomizedPartition(int[] nums, int l, int r) {
    int i = new Random().nextInt(r - l + 1) + l; // 随机选一个作为我们的主元
    swap(nums, r, i);
    return partition(nums, l, r);
  }

  public int partition(int[] nums, int l, int r) {
    int pivot = nums[r];
    int i = l - 1;
    for (int j = l; j <= r - 1; ++j) {
      if (nums[j] <= pivot) {
        i = i + 1;
        swap(nums, i, j);
      }
    }
    swap(nums, i + 1, r);
    return i + 1;
  }

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

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