JS前端面试必备——基本排序算法原理与实现方法详解【插入/选择/归并/冒泡/快速排序】

JS前端面试必备——基本排序算法原理与实现方法详解

在前端面试中，算法是一个必考的考点，掌握一些基本的排序算法对于一个前端工程师来说是非常重要的。

排序算法的分类

排序算法可以按照许多不同的标准进行分类：

• 平均时间复杂度
• 空间复杂度
• 稳定性
• 内部排序和外部排序

在这篇文章中，我们将按照时间复杂度从小到大的顺序介绍以下五个基本的排序算法：插入排序、选择排序、归并排序、冒泡排序和快速排序。

插入排序（Insertion Sort）

插入排序的算法思想是将一个待排序的数组，分成两部分，第一部分是已经排序的部分（第一个元素），第二部分是待排序的部分（第二个元素到最后一个元素）。然后，从待排序的部分中取出一个元素，将它插入到已经排序的部分中，使得还是有序的。

插入排序的时间复杂度是 O(n^2)，它最好的情况下可以达到 O(n)，但是最坏的情况下达到 O(n^2)。

插入排序的JavaScript代码实现如下：

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

// 运行示例
let arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];
let sortedArr = insertionSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

选择排序（Selection Sort）

选择排序的算法思想是将一个待排序的数组，分成两部分，第一部分是已经排序的部分（第一个元素），第二部分是待排序的部分（第二个元素到最后一个元素）。然后，从待排序的部分中寻找最小的一个元素，将它放到已经排序部分的最后。

选择排序的时间复杂度是 O(n^2)。

选择排序的JavaScript代码实现如下：

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

// 运行示例
let arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];
let sortedArr = selectionSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

归并排序（Merge Sort）

归并排序的算法思想是将一个待排序的数组，分成两部分，然后将每一部分都排序，再将两部分归并成一个有序的数组。

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

归并排序的JavaScript代码实现如下：

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

function merge(left, right) {
  let result = [];
  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;
}

// 运行示例
let arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];
let sortedArr = mergeSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

冒泡排序（Bubble Sort）

冒泡排序的算法思想是将一个待排序的数组，从左到右依次比较相邻的两个元素的大小，如果前一个元素的值比后一个元素的值大，则交换这两个元素的位置。每一轮比较完，最后一个元素一定是最大的，下一轮比较时可以忽略这个元素，因此每一轮可以少比较一次，并且比较的元素个数一定减一。

冒泡排序的时间复杂度是 O(n^2)。

冒泡排序的JavaScript代码实现如下：

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

// 运行示例
let arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];
let sortedArr = bubbleSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

快速排序（Quick Sort）

快速排序的算法思想是选取一个基准值，然后将数组中的值分为两部分，一部分是小于基准值的，一部分是大于等于基准值的。然后递归对这两部分进行快速排序，最终得到一个有序的数组。

快速排序的时间复杂度是 O(nlogn)。

快速排序的JavaScript代码实现如下：

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  let pivot = arr[right];
  let i = left - 1;
  for (let j = left; j <= right - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  let temp = arr[right];
  arr[right] = arr[i + 1];
  arr[i + 1] = temp;
  return i + 1;
}

// 运行示例
let arr = [5, 3, 8, 4, 2, 1, 9, 7, 6];
let sortedArr = quickSort(arr);
console.log(sortedArr); // [1, 2, 3, 4, 5, 6, 7, 8, 9]

结语

以上就是五个常见的排序算法，在面试中，你可以根据实际情况给出最优的答案。一般来说，归并排序和快速排序是最常用的排序算法，因为它们的时间复杂度比较小。如果待排序的数组比较小，插入排序和选择排序也是很不错的选择。而冒泡排序则是最不推荐使用的排序算法，因为它的时间复杂度最高。