Question

912. 排序数组

English Version

题目描述

给你一个整数数组 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

解法

方法一：快速排序

快速排序是一种高效的排序算法。它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

class Solution:
  def sortArray(self, nums: List[int]) -> List[int]:
    def quick_sort(l, r):
      if l >= r:
        return
      x = nums[randint(l, r)]
      i, j, k = l - 1, r + 1, l
      while k < j:
        if nums[k] < x:
          nums[i + 1], nums[k] = nums[k], nums[i + 1]
          i, k = i + 1, k + 1
        elif nums[k] > x:
          j -= 1
          nums[j], nums[k] = nums[k], nums[j]
        else:
          k = k + 1
      quick_sort(l, i)
      quick_sort(j, r)

    quick_sort(0, len(nums) - 1)
    return nums

class Solution {
  private int[] nums;

  public int[] sortArray(int[] nums) {
    this.nums = nums;
    quikcSort(0, nums.length - 1);
    return nums;
  }

  private void quikcSort(int l, int r) {
    if (l >= r) {
      return;
    }
    int x = nums[(l + r) >> 1];
    int i = l - 1, j = r + 1;
    while (i < j) {
      while (nums[++i] < x) {
      }
      while (nums[--j] > x) {
      }
      if (i < j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
      }
    }
    quikcSort(l, j);
    quikcSort(j + 1, r);
  }
}

class Solution {
public:
  vector<int> sortArray(vector<int>& nums) {
    function<void(int, int)> quick_sort = [&](int l, int r) {
      if (l >= r) {
        return;
      }
      int i = l - 1, j = r + 1;
      int x = nums[(l + r) >> 1];
      while (i < j) {
        while (nums[++i] < x) {
        }
        while (nums[--j] > x) {
        }
        if (i < j) {
          swap(nums[i], nums[j]);
        }
      }
      quick_sort(l, j);
      quick_sort(j + 1, r);
    };
    quick_sort(0, nums.size() - 1);
    return nums;
  }
};

func sortArray(nums []int) []int {
  quickSort(nums, 0, len(nums)-1)
  return nums
}

func quickSort(nums []int, l, r int) {
  if l >= r {
    return
  }
  i, j := l-1, r+1
  x := nums[(l+r)>>1]
  for i < j {
    for {
      i++
      if nums[i] >= x {
        break
      }
    }
    for {
      j--
      if nums[j] <= x {
        break
      }
    }
    if i < j {
      nums[i], nums[j] = nums[j], nums[i]
    }
  }
  quickSort(nums, l, j)
  quickSort(nums, j+1, r)
}

function sortArray(nums: number[]): number[] {
  function quickSort(l: number, r: number) {
    if (l >= r) {
      return;
    }
    let i = l - 1;
    let j = r + 1;
    const x = nums[(l + r) >> 1];
    while (i < j) {
      while (nums[++i] < x);
      while (nums[--j] > x);
      if (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    }
    quickSort(l, j);
    quickSort(j + 1, r);
  }
  const n = nums.length;
  quickSort(0, n - 1);
  return nums;
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  function quickSort(l, r) {
    if (l >= r) {
      return;
    }
    let i = l - 1;
    let j = r + 1;
    const x = nums[(l + r) >> 1];
    while (i < j) {
      while (nums[++i] < x);
      while (nums[--j] > x);
      if (i < j) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
      }
    }
    quickSort(l, j);
    quickSort(j + 1, r);
  }
  const n = nums.length;
  quickSort(0, n - 1);
  return nums;
};

方法二：归并排序

归并排序是一种分治算法，其思想是将待排序的数据序列不断地折半拆分，直到每个数据块只有一个元素为止，然后再按照拆分的顺序将每个数据块两两合并，在合并的过程中进行排序，最终得到一个有序的数据序列。

归并排序是一种稳定的排序算法，时间复杂度为 $O(n \times \log n)$，空间复杂度为 $O(n)$。其中 $n$ 为数组长度。

class Solution:
  def sortArray(self, nums: List[int]) -> List[int]:
    def merge_sort(l, r):
      if l >= r:
        return
      mid = (l + r) >> 1
      merge_sort(l, mid)
      merge_sort(mid + 1, r)
      i, j = l, mid + 1
      tmp = []
      while i <= mid and j <= r:
        if nums[i] <= nums[j]:
          tmp.append(nums[i])
          i += 1
        else:
          tmp.append(nums[j])
          j += 1
      if i <= mid:
        tmp.extend(nums[i : mid + 1])
      if j <= r:
        tmp.extend(nums[j : r + 1])
      for i in range(l, r + 1):
        nums[i] = tmp[i - l]

    merge_sort(0, len(nums) - 1)
    return nums

class Solution {
  private int[] nums;

  public int[] sortArray(int[] nums) {
    this.nums = nums;
    quickSort(0, nums.length - 1);
    return nums;
  }

  private void quickSort(int l, int r) {
    if (l >= r) {
      return;
    }
    int i = l - 1, j = r + 1, k = l;
    int x = nums[(l + r) >> 1];
    while (k < j) {
      if (nums[k] < x) {
        swap(++i, k++);
      } else if (nums[k] > x) {
        swap(--j, k);
      } else {
        ++k;
      }
    }
    quickSort(l, i);
    quickSort(j, r);
  }

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

class Solution {
public:
  vector<int> sortArray(vector<int>& nums) {
    function<void(int, int)> merge_sort = [&](int l, int r) {
      if (l >= r) {
        return;
      }
      int mid = (l + r) >> 1;
      merge_sort(l, mid);
      merge_sort(mid + 1, r);
      int i = l, j = mid + 1, k = 0;
      int tmp[r - l + 1];
      while (i <= mid && j <= r) {
        if (nums[i] <= nums[j]) {
          tmp[k++] = nums[i++];
        } else {
          tmp[k++] = nums[j++];
        }
      }
      while (i <= mid) {
        tmp[k++] = nums[i++];
      }
      while (j <= r) {
        tmp[k++] = nums[j++];
      }
      for (i = l; i <= r; ++i) {
        nums[i] = tmp[i - l];
      }
    };
    merge_sort(0, nums.size() - 1);
    return nums;
  }
};

func sortArray(nums []int) []int {
  mergeSort(nums, 0, len(nums)-1)
  return nums
}

func mergeSort(nums []int, l, r int) {
  if l >= r {
    return
  }
  mid := (l + r) >> 1
  mergeSort(nums, l, mid)
  mergeSort(nums, mid+1, r)
  i, j, k := l, mid+1, 0
  tmp := make([]int, r-l+1)
  for i <= mid && j <= r {
    if nums[i] <= nums[j] {
      tmp[k] = nums[i]
      i++
    } else {
      tmp[k] = nums[j]
      j++
    }
    k++
  }
  for ; i <= mid; i++ {
    tmp[k] = nums[i]
    k++
  }
  for ; j <= r; j++ {
    tmp[k] = nums[j]
    k++
  }
  for i = l; i <= r; i++ {
    nums[i] = tmp[i-l]
  }
}

function sortArray(nums: number[]): number[] {
  function mergetSort(l: number, r: number) {
    if (l >= r) {
      return;
    }
    const mid = (l + r) >> 1;
    mergetSort(l, mid);
    mergetSort(mid + 1, r);
    let [i, j, k] = [l, mid + 1, 0];
    while (i <= mid && j <= r) {
      if (nums[i] <= nums[j]) {
        tmp[k++] = nums[i++];
      } else {
        tmp[k++] = nums[j++];
      }
    }
    while (i <= mid) {
      tmp[k++] = nums[i++];
    }
    while (j <= r) {
      tmp[k++] = nums[j++];
    }
    for (i = l, j = 0; i <= r; ++i, ++j) {
      nums[i] = tmp[j];
    }
  }
  const n = nums.length;
  let tmp = new Array(n).fill(0);
  mergetSort(0, n - 1);
  return nums;
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  function mergetSort(l, r) {
    if (l >= r) {
      return;
    }
    const mid = (l + r) >> 1;
    mergetSort(l, mid);
    mergetSort(mid + 1, r);
    let [i, j, k] = [l, mid + 1, 0];
    while (i <= mid && j <= r) {
      if (nums[i] <= nums[j]) {
        tmp[k++] = nums[i++];
      } else {
        tmp[k++] = nums[j++];
      }
    }
    while (i <= mid) {
      tmp[k++] = nums[i++];
    }
    while (j <= r) {
      tmp[k++] = nums[j++];
    }
    for (i = l, j = 0; i <= r; ++i, ++j) {
      nums[i] = tmp[j];
    }
  }
  const n = nums.length;
  let tmp = new Array(n).fill(0);
  mergetSort(0, n - 1);
  return nums;
};

方法三

class Solution {
  private int[] nums;

  public int[] sortArray(int[] nums) {
    this.nums = nums;
    mergeSort(0, nums.length - 1);
    return nums;
  }

  private void mergeSort(int l, int r) {
    if (l >= r) {
      return;
    }
    int mid = (l + r) >> 1;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    int[] tmp = new int[r - l + 1];
    while (i <= mid && j <= r) {
      if (nums[i] <= nums[j]) {
        tmp[k++] = nums[i++];
      } else {
        tmp[k++] = nums[j++];
      }
    }
    while (i <= mid) {
      tmp[k++] = nums[i++];
    }
    while (j <= r) {
      tmp[k++] = nums[j++];
    }
    for (i = l; i <= r; ++i) {
      nums[i] = tmp[i - l];
    }
  }
}