题目

题目来源：力扣（LeetCode）

给你一个整数数组 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. /**
  2.  * @param {number[]} nums
  3.  * @return {number[]}
  4.  */
  5. var sortArray = function(nums) {
  6.   quickSort(nums, 0, nums.length - 1);
  7.   return nums
  8. };
  10. const quickSort = (arr, left, right) => {
  11.   // 只剩一个元素时，不用再进行排序
  12.   if (left > right) return;
  13.   let i = left, j = right;
  15.   // 基准值
  16.   const pivot = arr[i];
  18.   while (i < j) {
  19.     // 从右向左找到小的
  20.     while (i < j && arr[j] >= pivot) {
  21.       j--;
  22.     }
  23.     arr[i] = arr[j];
  25.     // 从左向右找到大的
  26.     while (i < j && arr[i] <= pivot) {
  27.       i++
  28.     }
  29.     arr[j] = arr[i];
  30.   }
  32.   arr[i] = pivot;
  33.   quickSort(arr, left, i - 1);
  34.   quickSort(arr, i + 1, right);
  35. }

方法二：堆排序

堆排序的思想就是先将待排序的序列建成大根堆，使得每个父节点的元素大于等于它的子节点。此时整个序列最大值即为堆顶元素，我们将其与末尾元素交换，使末尾元素为最大值，然后再调整堆顶元素使得剩下的 n-1 个元素仍为大根堆，再重复执行以上操作我们即能得到一个有序的序列。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[]}
  4.  */
  5. var sortArray = function (nums) {
  6.   let len = nums.length
  8.   const heapify = function (index) {
  9.     const left = index * 2 + 1
  10.     const right = index * 2 + 2
  11.     let largest = index
  12.     if (left < len && nums[left] > nums[largest]) {
  13.       largest = left
  14.     }
  15.     if (right < len && nums[right] > nums[largest]) {
  16.       largest = right
  17.     }
  18.     if (largest !== index) {
  19.       swap(nums, index, largest)
  20.       heapify(largest)
  21.     }
  22.   }
  23.   const buildMaxHeap = function () {
  24.     for (let i = len >> 1; i >= 0; i--) {
  25.       heapify(i)
  26.     }
  27.   }
  28.   buildMaxHeap()
  29.   for (let i = len - 1; i >= 0; i--) {
  30.     swap(nums, i, 0)
  31.     len--
  32.     heapify(0)
  33.   }
  34.   return nums
  35. }
  37. const swap = function (arr, i, j) {
  38.   const temp = arr[i]
  39.   arr[i] = arr[j]
  40.   arr[j] = temp
  41. }

方法三：归并排序

归并排序利用了分治的思想来对序列进行排序。对一个长为 n 的待排序的序列，我们将其分解成两个长度为
n/2 的子序列。每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[]}
  4.  */
  5. var sortArray = function (nums) {
  6.   let len = nums.length
  7.   const temp = []
  9.   const merge = function (left, mid, right) {
  10.     let p1 = left, p2 = mid + 1
  11.     temp.length = 0
  12.     while (p1 <= mid && p2 <= right) {
  13.       temp.push(nums[p1] < nums[p2] ? nums[p1++] : nums[p2++])
  14.     }
  15.     while (p1 <= mid) {
  16.       temp.push(nums[p1++])
  17.     }
  18.     while (p2 <= right) {
  19.       temp.push(nums[p2++])
  20.     }
  21.     for (let i = left; i <= right; i++) {
  22.       nums[i] = temp[i - left]
  23.     }
  24.   }
  25.   const sort = function (left, right) {
  26.     if (left >= right) return
  27.     if (right - left === 1) {
  28.       if (nums[left] > nums[right]) {
  29.         swap(nums, left, right)
  30.       }
  31.       return
  32.     }
  33.     const mid = left + ((right - left) >> 1)
  34.     sort(left, mid)
  35.     sort(mid + 1, right)
  36.     merge(left, mid, right)
  37.   }
  38.   sort(0, nums.length - 1)
  39.   return nums
  40. };
  42. const swap = function (arr, i, j) {
  43.   const temp = arr[i]
  44.   arr[i] = arr[j]
  45.   arr[j] = temp
  46. }