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]

解法:(快排)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  quickSort(nums,0,nums.length-1);
  return nums;
}

var quickSort = (arr,left,right) =>{
  if(left >= right) return;
  let mid = partition(arr,left,right);
  quickSort(arr,left,mid-1);
  quickSort(arr,mid+1,right);
}

var partition = (arr,left,right) => {
  let base = arr[left];
  let start = left + 1;
  let end = right;
  while(start<end){
    while(start<end && arr[start] <= base){
      start++;
    }
    if(end != start){
      change(arr,start,end);
      end--;
    }
  }
  if(start == end && arr[end] > base) end--;
  if(end != left){
    change(arr,left,end);
  }
  return end;
}

var change = (arr,left,right)=>{
  let temp = arr[left];
  arr[left] = arr[right];
  arr[right] = temp;
}

解法:(计数排序)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
  countingSort(nums);
  return nums;
}
var countingSort = function(nums){
  let min = nums[0];
  let max = nums[0];
  for(let i=1;i<nums.length;i++){
    if(nums[i]<min) min = nums[i];
    if(nums[i]>max) max = nums[i];
  }
  let range = max-min+1;
  let counting = new Array(range).fill(0);
  for(let item of nums){
    counting[item-min]++;
  }
  counting[0]--;
  for(let i=1;i<range;i++){
    counting[i] += counting[i-1];
  }
  let res = new Array(nums.length);
  for(let i=nums.length-1;i>=0;i--){
    res[counting[nums[i] - min]] = nums[i];
    counting[nums[i] - min]--;
  }
  for(let i=0;i<nums.length;i++){
    nums[i] = res[i];
  }
  return nums;
}