排序算法

• 基础排序算法：
  • 冒泡排序
  • 插入排序
  • 选择排序
• 进阶排序算法
  • 归并排序
  • 快速排序

冒泡排序 - 稳定的排序

将数组中的每两个相邻的元素进行比较，如果发现前一个元素大于后一个元素，那么就交换位置，这样第一轮遍历结束之后，数组的最后一个元素就是数组中最大的元素，那么在下一轮循环中最后一个元素就不参与比较。重复上面的方式，直到整个数组都变为有序

假如数组的长度是 n，那么当我们重复完 n 轮的时候，整个数组就有序了。

不过，冒泡排序的逻辑并不会因为数组有序就立刻停下来——”从头到尾遍历数组，对比+交换每两个相邻元素“这套逻辑到底要执行多少次，是完全由数组中元素的个数来决定的

function bubbleSort(nums) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }
  return nums;
}

上面这种写法，在最好情况下对应的时间复杂度确实不是 O(n)，而是 O(n^2)。

面向“最好情况”的进一步改进

function bubbleSort(nums) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    // 区别在这里，我们加了一个标志位
    let flag = false;
    for (let j = 0; j < len - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
        // 只要发生了一次交换，就修改标志位
        flag = true;
      }
    }
    // 若一次交换也没发生，则说明数组有序，直接放过
    if (flag == false) return nums;
  }
  return nums;
}

标志位可以帮助我们在第一次冒泡的时候就定位到数组是否完全有序，进而节省掉不必要的判断逻辑，将最好情况下的时间复杂度定向优化为 O(n)。

冒泡排序的时间复杂度

• 最好时间复杂度：它对应的是数组本身有序这种情况。在这种情况下，我们只需要作比较（n-1 次），而不需要做交换。时间复杂度为 O(n)
• 最坏时间复杂度： 它对应的是数组完全逆序这种情况。在这种情况下，每一轮内层循环都要执行，重复的总次数是 n(n-1)/2 次，因此时间复杂度是 O(n^2)
• 平均时间复杂度：这个东西比较难搞，它涉及到一些概率论的知识。实际面试的时候也不会有面试官摁着你让你算这个，这里记住平均时间复杂度是 O(n^2) 即可。

选择排序 - 不稳定的排序

将数组看为两部分，一部分是有序的，一部分是无序的，每次都从无序的那部分中选出最小的元素，然后追加到有序的这部分的末尾

function selectSort(nums) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    let minIndex = i;
    for (let j = i; j < len; j++) {
      if (nums[j] < nums[minIndex]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
    }
  }
  return nums;
}

选择排序的时间复杂度

最好情况也好，最坏情况也罢，两者之间的区别仅仅在于元素交换的次数不同，但都是要走内层循环作比较的。因此选择排序的三个时间复杂度都对应两层循环消耗的时间量级： O(n^2)。

插入排序 - 稳定排序

将数组看为两部分，一部分是有序的，一部分是无序的，每次都取出无序部分的第一个元素，在有序的那部分中从后往前查找，直到找到一个元素的值 <= 当前元素，则将当前元素插入到整个元素后面

插入排序里的几个关键点：

• 当前元素前面的那个序列是有序的
• “正确的位置”如何定义——所有在当前元素前面的数都不大于它，所有在当前元素后面的数都不小于它
• 在有序序列里定位元素位置的时候，是从后往前定位的。只要发现一个比当前元素大的值，就需要为当前元素腾出一个新的坑位。

function insertSort(nums) {
  const len = nums.length;
  for (let i = 1; i < len - 1; i++) {
    let j = i;
    for (; j > 0; j--) {
      if (nums[j - 1] > nums[j]) {
        nums[j] = nums[j - 1];
      } else {
        break;
      }
    }
    nums[j] = nums[i];
  }
  return nums;
}

插入排序的时间复杂度

• 最好时间复杂度：它对应的数组本身就有序这种情况。此时内层循环只走一次，整体复杂度取决于外层循环，时间复杂度就是一层循环对应的 O(n)。

• 最坏时间复杂度：它对应的是数组完全逆序这种情况。此时内层循环每次都要移动有序序列里的所有元素，因此时间复杂度对应的就是两层循环的 O(n^2)

• 平均时间复杂度：O(n^2)

分治思想

“分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。

利用分治思想解决问题，我们一般分三步走：

• 分解子问题
• 求解每个子问题
• 合并子问题的解，得出大问题的解

归并排序 - 稳定的排序

• 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
• 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。
• 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组

function mergeSort(nums) {
  if (nums.length < 2) return nums;
  const len = nums.length;
  const mid = Math.floor(len / 2);
  const left = nums.slice(0, mid);
  const right = nums.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(nums1, nums2) {
  const n1 = nums1.length;
  const n2 = nums2.length;
  const result = [];
  let p1 = 0, p2 = 0;
  let cur;
  while (p1 < n1 || p2 < n2) {
    if (p1 === n1) {
      cur = nums2[p2++];
    } else if (p2 === n2) {
      cur = nums1[p1++];
    } else if (nums1[p1] < nums2[p2]) {
      cur = nums1[p1++];
    } else {
      cur = nums2[p2++];
    }
    result[p1 + p2 - 1] = cur;
  }
  return result;
}

我们把每一次切分+归并看做是一轮。对于规模为 n 的数组来说，需要切分 log(n) 次，因此就有 log(n) 轮。

再看合并，单次合并的时间复杂度为 O(n)。O(n) 和 O(1) 完全不在一个复杂度量级上，因此本着“抓主要矛盾”的原则，我们可以认为：决定归并排序时间复杂度的操作就是合并操作。

log(n) 轮对应 log(n) 次合并操作，因此归并排序的时间复杂度就是 O(nlog(n))。

归并排序的时间复杂度是 O(nlog(n))。

快速排序 - 不稳定的排序

快速排序会将原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。

有一个基准元素，根据这个基准元素将数组分为两部分，一部分大于这个基准元素，一部分小于这个基准元素

1. 首先要做的事情就选取一个基准值。基准值的选择有很多方式，这里我们选取数组中间的值

2. 左右指针分别指向数组的两端。接下来我们要做的，就是先移动左指针，直到找到一个不小于基准值的值为止；然后再移动右指针，直到找到一个不大于基准值的值为止。

// 快速排序入口
function quickSort(arr, left = 0, right = arr.length - 1) {
  // 定义递归边界，若数组只有一个元素，则没有排序必要
  if(arr.length > 1) {
      // lineIndex表示下一次划分左右子数组的索引位
      const lineIndex = partition(arr, left, right)
      // 如果左边子数组的长度不小于1，则递归快排这个子数组
      if(left < lineIndex-1) {
        // 左子数组以 lineIndex-1 为右边界
        quickSort(arr, left, lineIndex-1)
      }
      // 如果右边子数组的长度不小于1，则递归快排这个子数组
      if(lineIndex<right) {
        // 右子数组以 lineIndex 为左边界
        quickSort(arr, lineIndex, right)
      }
  }
  return arr
}
// 以基准值为轴心，划分左右子数组的过程
function partition(arr, left, right) {
  // 基准值默认取中间位置的元素
  let pivotValue = arr[Math.floor(left + (right-left)/2)]
  // 初始化左右指针
  let i = left
  let j = right
  // 当左右指针不越界时，循环执行以下逻辑
  while(i<=j) {
      // 左指针所指元素若小于基准值，则右移左指针
      while(arr[i] < pivotValue) {
          i++
      }
      // 右指针所指元素大于基准值，则左移右指针
      while(arr[j] > pivotValue) {
          j--
      }

      // 若i<=j，则意味着基准值左边存在较大元素或右边存在较小元素，交换两个元素确保左右两侧有序
      if(i<=j) {
          swap(arr, i, j)
          i++
          j--
      }

  }
  // 返回左指针索引作为下一次划分左右子数组的依据
  return i
}

// 快速排序中使用 swap 的地方比较多，我们提取成一个独立的函数
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}

快速排序的时间复杂度分析

快速排序的时间复杂度的好坏，是由基准值来决定的。

• 最好时间复杂度：它对应的是这种情况——我们每次选择基准值，都刚好是当前子数组的中间数。这时，可以确保每一次分割都能将数组分为两半，进而只需要递归 log(n) 次。这时，快速排序的时间复杂度分析思路和归并排序相似，最后结果也是 O(nlog(n))。
• 最坏时间复杂度：每次划分取到的都是当前数组中的最大值/最小值。大家可以尝试把这种情况代入快排的思路中，你会发现此时快排已经退化为了冒泡排序，对应的时间复杂度是 O(n^2)。
• 平均时间复杂度： O(nlog(n))