leetcode-Sort

一、模板

1. 三路快排

let pivot = arr[low]
let lt = low  // [low+1...lt] < pivot 
let gt = high // [gt ... high] > pivot
let i = low + 1 // [lt+1 ... gt-1] = pivot
while(i < gt){
  if(arr[i] === pivot)
    i++
 	else if(arr[i] < pivot){
    lt++
    swap(arr,i,lt)
    i++
  }else if(arr[i] > pivot){
    gt--
    swap(arr,i,gt)
  }
}

2. 归并

/**
 * nums1, m
 * nums2, n
 */
let arr = []
let i = 0,j = 0, k = 0
while(i < m && j < n)
  arr[k++] = nums1[i] <= nums2[j] ? nums1[i++] : nums2[j++]

while(i < m)
  arr[k++] = nums1[i++]
while(j < m)
  arr[k++] = nums2[j++]

二、题目

(1) 快排

75. 颜色分类

/**
 * 统计
 */

var sortColors = function (nums) {
  let count = new Array(3).fill(0)
  for (let i = 0; i < nums.length; i++)
    count[nums[i]]++

  let index = 0
  for (let i = 0; i < count.length; i++)
    for (let j = 0; j < count[i]; j++)
      nums[index++] = i
};

/**
 * 3路快排
 */

var sortColors = function (nums) {
  let zero = -1
  let two = nums.length
  let i = 0
  while(i < two){
    if(nums[i] === 1){
      i++
    }else if(nums[i] === 2){
      two--
      swap(nums,i,two)
    }else if(nums[i] === 0){
      zero++
      swap(nums,i,zero)
      i++
    }
  }
};

215. 数组中的第K个最大元素

/**
 * 快排 O(n)
 */

var findKthLargest = function (nums, k) {
  return quickSort(nums, 0, nums.length - 1)

  function quickSort(nums, low, high) {
    let p = _partition(nums, low, high)
    if (p === nums.length - k)
      return nums[p]
    else if (p < nums.length - k)
      return quickSort(nums, p + 1, high)
    else
      return quickSort(nums, low, p - 1)
  }

  function _partition(nums,low,high){
    let pivot = nums[low]
    while(low < high){
      while(low < high && nums[high] >= pivot) high--
      nums[low] = nums[high]
      while(low < high && nums[low] < pivot) low++
      nums[high] = nums[low]
    }
    nums[low] = pivot
    return low
  }
};

(2) 归并

88. 合并两个有序数组

/**
 * 归并
 */

var merge = function(nums1, m, nums2, n) {
  let nums1_copy = [].concat(nums1)

  let i = 0,j = 0,k = 0
  while(i<m && j < n)
    nums1[k++] = nums1_copy[i] < nums2[j] ? nums1_copy[i++]:nums2[j++]
  
  while(i<m)
    nums1[k++] = nums1_copy[i++]

  while(j<n)
    nums1[k++] = nums2[j++]
};