常见排序算法以及复杂度.md

冒泡排序

// 时间复杂度：O(N^2)  5860ms    6.25%
// 空间复杂度：O(1)    45.2MB    46.88%
const sortArray = (nums) => {
  for (let i = 0; i < nums.length - 1; i++) {
    let mark = true
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] > nums[j + 1]) {
        ;[nums[j], nums[j + 1]] = [nums[j + 1], nums[j]]
        mark = false
      }
    }
    if (mark) return
  }
}

选择排序

// 时间复杂度：O(N^2) 1372ms 12.50%
// 空间复杂度：O(1) 44.2MB 93.75%
const sortArray = (nums) => {
  for (let i = 0, len = nums.length; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      // 将 nums[i] 和它后面的元素进行比较，使 nums[i] 一直维持最小
      if (nums[i] > nums[j]) {
        ;[nums[i], nums[j]] = [nums[j], nums[i]]
      }
    }
  }
  return nums
}

快速排序

// 时间复杂度：O(NlogN)     148ms      50%
// 空间复杂度：O(logN)      45.6MB     46.88%
const sortArray = (nums, left = 0, right = nums.length - 1) => {
  if (left >= right) return nums
  let i = left
  let j = right - 1
  while (i <= j) {
    if (nums[i] > nums[right]) {
      ;[nums[i], nums[j]] = [nums[j], nums[i]]
      j--
    } else {
      i++
    }
  }
  j++
  ;[nums[j], nums[right]] = [nums[right], nums[j]]
  sortArray(nums, left, j - 1)
  sortArray(nums, j + 1, right)
  return nums
}