排序算法

一说到算法，第一个想到的一定是排序算法。是最经典，使用最广泛的算法，掌握几种快速算法的思路是很有必要的。

快速排序

快速排序是一个完全原地的排序算法，它不需要占用任何额外的空间复杂度，就能实现 O(NlogN) 的排序效率。

快速排序的思想是，每次都将一个元素放在排序后正确的位置，直到数组有序。

具体实现思路是，利用首尾指针，不断比较该元素与首尾指针指向的元素，并进行交换。使得数组分界线左侧的所有元素都小于当前元素，右侧所有元素都大于当前元素，那么当前分界线所在位置即为当前元素的正确位置。至此就完成了一次快速排序。

之后进行递归，将有序位置的左右两侧子数组再分别进行一次快速排序。

由于整体的思路是先解决最小子问题，再递归地解决两侧的问题，因此该算法在递归形式上与二叉树的前序遍历是相似的。

function sortArray(nums: number[]): number[] {
  sort(0, nums.length - 1);
  return nums;

  // 左右闭区间
  function sort(left: number, right: number) {
    // 快速排序
    if (left >= right) return;

    // 快速排序，先快速找到某个位置上的正确值，再递归
    const index = quickSort(left, right);
    sort(left, index - 1);
    sort(index + 1, right);
  }

  function quickSort(left: number, right: number): number {
    // 设置一个基准比较值，为了方便选第一个
    const temp = nums[left];
    let l = left + 1;
    let r = right;

    while (l <= r) {
      while (l < right && temp >= nums[l]) l++;
      while (r > left && temp <= nums[r]) r--;
      // 此时 [left+1, l) 都 <= temp，(r, right] 都 >= temp

      // 判断是否结束一轮比较了
      if (l >= r) break;

      // 此时有 arr[l] > temp, arr[r] < temp
      // 交换两指针对应值，使得交换完成后 [left+1, l+1) 都 <= temp，(r-1,right] 都 >= temp
      [nums[l], nums[r]] = [nums[r], nums[l]];
    }

    // 比较结束后，此时 r = l+1。[left+1, r) 都 <= temp，(r,right] 都 >= temp，且 temp >= nums[r]
    // 因此 r 位置就是基准比较值 temp 应该在的正确位置，将 temp 与此时 nums[r] 做交换
    [nums[left], nums[r]] = [nums[r], nums[left]];
    return r;
  }
}

归并排序

归并排序采用的是分治法的思路。先自顶向下地分割子问题，再自底向上地对数组进行排序。

整个算法划分为两步，分割与治理。

分指利用二分法，递归地将每一次的数组进行分割。直到分到左指针等于右指针(left = right)，即子数组元素个数为 1。

治指将两个有序子数组合并为一个有序数组。利用双指针技巧，不断地比较左右指针指向数据的大小，并将较小的那个进入排序数组。由于这里需要将两个数组合并为一个数组，因此并不能原地合并，需要新建一个辅助数组来完成有序数组的归并，完成后再赋值回原位置。

由于整体的思路是先分后治，因此该算法在递归形式上与二叉树的后序遍历是相似的。

function sortArray(nums: number[]): number[] {
  sort(0, nums.length - 1);
  return nums;

  function sort(left: number, right: number) {
    // 如果要比较的数组长度为 1 时，不需要比较
    if (left === right) return;
    // 先递归，直到单个数组长度为 1，再归并
    const mid = Math.floor((left + right) / 2);
    sort(left, mid);
    sort(mid + 1, right);
    mergeSort(left, mid, right);
  }

  function mergeSort(left: number, mid: number, right: number) {
    // 将数组分割成 [left,mid], [mid+1, right] 左右两个子数组
    let l = left;
    let r = mid + 1;
    let temp: number[] = [];

    while (l < mid + 1 && r < right + 1) {
      // 比较左右数字，将较小的数字存入临时数组中
      if (nums[l] <= nums[r]) {
        temp.push(nums[l]);
        l++;
      } else {
        temp.push(nums[r]);
        r++;
      }
    }

    // 若有一方比较完成，则剩余数字一定全部大于临时数组中的所有值，直接拼接到后侧
    temp = temp.concat(nums.slice(l, mid + 1)).concat(nums.slice(r, right + 1));
    // console.log(temp);

    // 替换掉原 left 到 right 子数组
    nums.splice(left, right - left + 1, ...temp);
  }
}

堆排序

堆排序是利用了二叉堆性质来进行排序的方法。

所谓二叉堆，分为大顶堆或小顶堆，性质是(以大顶堆为例)：二叉堆中的每一个节点都大于其的两个子节点。

二叉堆中找到最大元素的时间复杂度为 O(1),即堆顶。而同时，二叉堆的插入与删除元素的复杂度均为 O(logN)。

于是堆排序的方式，简单来说就是，先花 O(NlogN)的时间复杂度建立一个二叉堆。之后每次花费 O(logN)删除堆顶元素并输出堆顶元素，即可保证输出结果是有序的。

function sortArray(nums: number[]): number[] {
  const len = nums.length;
  sort(true);
  return nums;

  // 数组递增排序或递减排序
  function sort(increase: boolean) {
    const isHeapMin = !increase;
    // 先将数组构建为大顶堆，最大值将会在堆顶
    buildHeap(isHeapMin);
    // 接下来仅需要每次丢弃并输出堆顶元素即可保证有序
    // 原地排序的具体做法是，遍历数组，每次将最大值交换到堆底并重新堆化前 n-1 个元素
    // 从而最终实现数组从小到大的排列，O(NlogN)
    for (let i = len - 1; i > 0; i--) {
      // 将堆顶元素移到堆尾，此时 i ~ len-1 的元素均为有序
      swap(0, i);
      // 堆化前 i-1 个元素
      heapifyDown(0, i, isHeapMin);
    }
  }

  // 对数组建立二叉堆，从倒数第一个非叶子节点开始堆化，结束后最大值一定在堆顶，O(NlogN)
  function buildHeap(isHeapMin: boolean) {
    let notLeafIndex = Math.floor(len / 2) - 1;
    for (let i = notLeafIndex; i >= 0; i--) {
      heapifyDown(i, len, isHeapMin);
    }
  }

  // 将当前节点作为根节点的子树进行堆化
  function heapifyDown(index: number, heapSize: number, isHeapMin: boolean) {
    // 左右子位置
    const l = index * 2 + 1;
    const r = l + 1;
    let temp = index;
    // 判断当前节点与左右子节点哪一个是最小(大)的
    if (l < heapSize && compare(nums[l], nums[temp], isHeapMin)) {
      temp = l;
    }
    if (r < heapSize && compare(nums[r], nums[temp], isHeapMin)) {
      temp = r;
    }

    // 若当前节点值比两个子节点的值都小(大)，则不交换，下沉停止
    // 否则进行交换，并递归继续下一次下沉比较
    if (temp !== index) {
      swap(index, temp);
      heapifyDown(temp, heapSize, isHeapMin);
    }
  }

  function compare(a: number, b: number, isMinHeap: boolean): boolean {
    if (isMinHeap) {
      return a - b < 0;
    }
    return a - b > 0;
  }

  function swap(i: number, j: number) {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
}