排序算法

[shuangmianxiaoQ]

本文排序动画来自可视化排序

排序算法是算法中的一种，彻底掌握对程序员有很大的帮助。

对于排序算法好坏的衡量，主要从时间复杂度、空间复杂度和稳定性来判断。

稳定性是指假定原序列中arr[i] = arr[j]，且arr[i]在arr[j]之前，排序后arr[i]仍然在arr[j]之前，则称为该排序算法是稳定的，否则是不稳定的。

常见排序算法

• 冒泡排序
• 选择排序
• 插入排序
• 归并排序
• 快速排序
• 堆排序

区别

冒泡排序（Bubble Sort）

思想：每次遍历一遍未排序的数列后，将一个元素浮上去（也就是排好了一个数）。

思路：

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

实现：

const bubbleSort = (arr) => {
  const len = arr.length;
  let noSwaps;
  for (let i = 0; i < len - 1; i++) {
    // flag for optimization
    noSwaps = true;
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        noSwaps = false;
      }
    }
    if (noSwaps) break;
  }
};

选择排序（Selection Sort）

思想：每次遍历未排序数列，找到一个最小值，将其放在合适位置。

思路：

1. 先把第一个没有排序过的元素设为最小值（记录最小值下标minIndex）。
2. 遍历后面的元素，如果当前元素小于最小值，则将该元素设为新的最小值（修改最小值下标）。
3. 遍历结束后，交换最小值和第一个没排序过的元素。
4. 重复上述步骤，直到序列有序。

实现：

const selectionSort = (arr) => {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    // 假设第一个元素为最小值
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      // 遍历后面的元素，如果小于假设的最小值，则将该元素设为新的最小值
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 如果是最小值就是自己，就不用交换了
    if (i !== minIndex) {
      // 将交换假设的最小值与新的最小值
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
};

插入排序（Insertion Sort）

思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

思路：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素x，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素x，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5。

实现：

const insertionSort = (arr) => {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    // 从第二个数开始往前比较
    const x = arr[i + 1];
    let j;
    for (j = i; j >= 0; j--) {
      // 如果比取出的数大，则往后移动一位
      if (arr[j] > x) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    // 最后将取出的数插到合适位置
    arr[j + 1] = x;
  }
};

归并排序（Merge Sort）

思想：采用分治思想，把序列递归的分成多个子序列，再将子序列进行合并，得到完全有序的序列。

思路：

1. 分：把数组分成两半，再递归对子数组进行分操作，直至到一个个单独数字。
2. 合：把两个数合成有序数组，再对有序数组进行合并操作，直到全部子数组合成一个完整的数组。具体的归并操作如下：
   • 新建一个数组，用于存放排序后的数组；
   • 比较两个数组的头部，较小者出队并且推入到上述新建的数组中；
   • 如果两个数组还有值，则重复上述第二步；
   • 如果只有一个数组有值，则将该数组的值出队并推入到上述新建的数组中。

实现：

const merge = (left, right) => {
  const res = [];
  while (left.length && right.length) {
    // 比较两个数组头部，较小者推入数组
    if (left[0] < right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  // 合并两个有序数组
  return res.concat(left, right);
};

const mergeSort = (arr) => {
  const len = arr.length;
  if (len === 1) return arr;
  const midIdx = len >> 1;
  const left = arr.slice(0, midIdx);
  const right = arr.slice(midIdx);
  // 递归拆分子数组，直到分成只有一个数的数组
  return merge(mergeSort(left), mergeSort(right));
};

快速排序（Quick Sort）

思想：又称分区交换排序，通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小；然后继续沿用此方法分别对两部分进行同样的操作，直到每一个小部分不可再分，所得到的整个序列就变成有序序列。

思路：

1. 分区：从数组中选择任意一个基准pivot，所有比基准小的元素放在基准的左边，比基准大的元素放到基准的右边。
2. 递归：递归地对基准前后的子数组进行分区。

实现：

// 这种算法借助空间，空间复杂度为O(n)
const quickSort = (arr) => {
  const rec = (arr) => {
    const len = arr.length;
    if (len <= 1) return arr;
    const left = [];
    const right = [];
    const mid = arr[0]; // 基准元素
    for (let i = 1; i < len; i++) {
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return [...rec(left), mid, ...rec(right)];
  };
  return rec(arr);
};

// 这种写法原地排序，空间复杂度为O(1)
const partition = (arr, l, r) => {
  const pivot = arr[r];
  let pIndex = l;
  for (let i = l; i < r; i++) {
    if (arr[i] < pivot) {
      // 小于基准值交换左右指针位置，并移动左指针
      [arr[pIndex], arr[i]] = [arr[i], arr[pIndex]];
      pIndex++;
    }
  }
  // 交换左指针与基准值
  [arr[pIndex], arr[r]] = [arr[r], arr[pIndex]];
  return pIndex;
};

const quickSort = (arr, l = 0, r = arr.length - 1) => {
  if (l < r) {
    const pIndex = partition(arr, l, r);
    quickSort(arr, l, pIndex - 1);
    quickSort(arr, pIndex + 1, r);
  }
};