排序算法

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

快速排序

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

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

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

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

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

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

  function sort(left: number, right: number) {
    if (left >= right) {
      return;
    }
    // 对 [left, right] 进行一次快排
    // 使得 nums[left, index-1] <= nums[index] < nums[p+1, right]
    const index = partition(left, right);
    // 之后对左右两侧的数组递归进行快排
    sort(left, index - 1);
    sort(index + 1, right);
  }

  function partition(left: number, right: number) {
    let flag = nums[left];
    let l = left + 1;
    let r = right;
    while (l <= r) {
      while (l < right && nums[l] <= flag) {
        l += 1;
      }
      while (r > left && nums[r] > flag) {
        r -= 1;
      }
      // 此时 [left, l) 所有元素都小于 flag，(r, right] 所有元素都大于 flag
      if (l >= r) {
        break;
      }
      // 此时存在 nums[l] > flag, nums[r] <= flag，因此将两者数值进行交换
      // 使得[left, l+1) 所有元素都小于 flag，(r-1, right] 所有元素都大于 flag
      swap(l, r);
    }
    // 此时l = r + 1。r 的左侧元素都小于 flag，右侧元素都大于 flag
    // 因此，r 的位置为 flag 排序后应当在的位置，做一次交换
    swap(left, r);
    // 返回元素有序的位置
    return r;
  }

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

归并排序

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

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

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

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

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

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

  function sort(left: number, right: number) {
    if (left === right) {
      // 单个元素不用排序
      return;
    }
    const mid = Math.floor((left + right) / 2);
    sort(left, mid);
    sort(mid + 1, right);
    merge(left, mid, right);
  }

  function merge(left: number, mid: number, right: number) {
    const temp = [];
    let l = left;
    let r = mid + 1;
    while (l < mid + 1 || r < right + 1) {
      if (l === mid + 1) {
        // 左侧数组已经全部合并，则将右边剩余数组直接拼接下来
        temp.push(nums[r]);
        r += 1;
      } else if (r === right + 1) {
        // 右侧数组已经全部合并，则将左边剩余数组直接拼接下来
        temp.push(nums[l]);
        l += 1;
      } else if (nums[l] > nums[r]) {
        // 左右指针两数相比取较小值，并前进指针
        temp.push(nums[r]);
        r += 1;
      } else {
        // temp[l] <= temp[r]
        temp.push(nums[l]);
        l += 1;
      }
    }
    // 原地更新数组
    for (let i = left; i <= right; i++) {
      nums[i] = temp[i - left];
    }
  }
}

堆排序

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

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

二叉堆中找到最大元素的时间复杂度为 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]];
  }
}