算法-高级排序算法

在排序算法中，常见的高级排序算法主要有 2 种：归并排序和快速排序。

归并排序#

归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置。接着将小数组（只有一个值）之间进行比较排序，之后归并成较大的数组，直到最后只有一个排序完毕的大数组。

算法步骤#

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
设定两个指针，最初位置分别为两个已经排序序列的起始位置。
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。
重复步骤 3 直到某一指针达到序列尾。
将另一序列剩下的所有元素直接复制到合并序列尾。

代码演示#

function mergeSort(arr) {
  const len = arr.length;
 
  if (len === 1) return arr; // 递归终止条件
 
  let mid = Math.floor(len / 2); // 中间点
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right)); // 递归
}
 
// 归并方法
function merge(left, right) {
  const result = []; // 新数组，用来保存归并的值
 
  // 比较 left 和 right 两个数组值第一个值
  // 谁小就把谁从原来的数组中取出来，并加入到新数组后面
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
 
  // 当其中一个数组已经清空后
  // 另外一个数组如果还有值，都是比较后剩余的较大的值
  // 把这些值依次从数组取出放入到新数组后面
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());
 
  return result;
}

归并排序的平时时间复杂度为O(NlogN)，但是空间复杂度为O(N)，有些情况下需要注意使用。

快速排序#

快速排序，也叫快排，是最常用的排序算法之一。它的复杂度为O(n log n)，且它的性能通常比其他的复杂度为O(n log n)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组。

算法步骤#

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码演示#

function quickSort(arr) {
  return quick(arr, 0, arr.length - 1);
}
 
function quick(arr, left, right) {
  let index;
  if (arr.length > 1) {
    index = partition(arr, left, right); // 分区索引
    if (left < index - 1) quick(arr, left, index - 1); // 左边分区排序
    if (index < right) quick(arr, index, right); // 右边分区排序
  }
  return arr;
}
 
// 分区操作
function partition(arr, left, right) {
  let pivot = arr[Math.floor((left + right) / 2)];
  let i = left;
  let j = right;
 
  while (i <= j) {
    while (arr[i] < pivot) i++;
    while (arr[j] > pivot) j--;
 
    if (i <= j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  }
 
  return i;
}
 
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

快速排序的平时时间复杂度为O(NlogN)，空间复杂度为O(logN)。

堆排序#

堆排序也是一种很高效的算法，因其把数组当作二叉树来排序而得名。这个算法会根据以下信息，把数组当作二叉树来管理：

索引 0 是树的根节点。
除根节点外，任意节点 N 的父节点是N / 2。
节点的左子节点 L 是2 * I + 1。
节点的右子节点 R 是2 * I + 2。

算法步骤#

创建一个堆 H[0……n - 1]。
把堆首（最大值）和堆尾互换。
把堆的尺寸缩小 1，并调用shift_down(0)，目的是把新的数组顶端数据调整到相应位置。
重复步骤 2，直到堆的尺寸为 1。

代码演示#

function heapSort(arr) {
  let heapSize = arr.length;
  buildHeap(arr);
 
  while (heapSize > 1) {
    heapSize--; // 堆的size减 1， 此时把堆尾，同时也是堆的最大值取出来了。递归，再把剩下的值的最大值再取出来
    swap(arr, 0, heapSize); // 交换堆首和堆尾的值。使得堆尾变成了最大值。这是可能会丢失堆的属性，成为数组
    heapify(arr, heapSize, 0); // 重新转换成堆
  }
 
  return arr; // 直到数组长度 === 1时，返回原数组
}
 
function buildHeap(arr) {
  let heapSize = arr.length;
  for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
    heapify(arr, heapSize, i);
  }
}
 
function heapify(arr, heapSize, i) {
  let left = i * 2 + 1; // 左子节点
  let right = i * 2 + 2; // 右子节点
  let largest = i; // 节点
 
  // 左子节点 比 节点大时，互换位置
  if (left < heapSize && arr[left] > arr[largest]) {
    largest = left;
  }
 
  // 右子节点 比 节点大时，互换位置
  if (right < heapSize && arr[right] > arr[largest]) {
    largest = right;
  }
 
  // 当最大的值不是根节点时，互换位置，保证根节点是最大值，然后重新转换成堆
  if (largest !== i) {
    swap(arr, i, largest);
    heapify(arr, heapSize, largest);
  }
}
 
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

堆排序的平时时间复杂度为O(NlogN)。