JavaScript数据结构与算法之基本排序算法定义与效率比较【冒泡、选择、插入排序】

JavaScript数据结构与算法之基本排序算法定义与效率比较

概述

排序是计算机科学中最常见的操作之一，是将数据按照一定的顺序重新排列的过程。排序算法被广泛应用于搜索、数据压缩、数据库等领域。JavaScript中常用的基本排序算法有3种：冒泡排序、选择排序和插入排序。本文将详细介绍这三种算法的原理、JavaScript实现以及时间复杂度比较。

冒泡排序

冒泡排序是一种基本排序算法，它的原理是比较相邻两个元素的大小，如果前一个元素比后一个元素大，则交换它们的位置。这样一趟排序后，最大的元素就会出现在最后面，然后再对剩下的元素进行排序，直到整个序列有序。

下面是一个JavaScript实现的冒泡排序算法：

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

冒泡排序的时间复杂度是$O(n^2)$，其中n代表要排序的元素个数。因为它的比较次数和交换次数都很多，所以效率较低。但冒泡排序的优点是它是稳定的，可以保证排序前后相等的元素的相对位置不变。

下面是一个冒泡排序的示例：

let arr = [5, 3, 8, 4, 2];
console.log(bubbleSort(arr)); // [2, 3, 4, 5, 8]

选择排序

选择排序也是一种基本排序算法，它的原理是每次从待排序的元素中选出最小的元素，放到已排序的序列的最后面，直到整个序列有序。

下面是一个JavaScript实现的选择排序算法：

function selectionSort(arr) {
  let 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]];
    }
  }
  return arr;
}

选择排序的时间复杂度也是$O(n^2)$，其中n代表要排序的元素个数。虽然选择排序的比较次数和交换次数都比冒泡排序少，但是它没有冒泡排序稳定。

下面是一个选择排序的示例：

let arr = [5, 3, 8, 4, 2];
console.log(selectionSort(arr)); // [2, 3, 4, 5, 8]

插入排序

插入排序是一种基本排序算法，它的原理是将待排序的元素逐个插入到已经排好序的序列中，直到整个序列有序。

下面是一个JavaScript实现的插入排序算法：

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

插入排序的时间复杂度也是$O(n^2)$，其中n代表要排序的元素个数。虽然插入排序的比较次数和交换次数都比冒泡排序和选择排序少，但是在最坏情况下，插入排序的效率与冒泡排序和选择排序相当。

下面是一个插入排序的示例：

let arr = [5, 3, 8, 4, 2];
console.log(insertionSort(arr)); // [2, 3, 4, 5, 8]

总结

对比冒泡排序、选择排序和插入排序，我们可以发现它们在时间复杂度上有相同的$O(n^2)$，但效率上有所不同。冒泡排序因为交换的次数较多，所以效率比较低；选择排序虽然比较次数和交换次数都比冒泡排序少，但不稳定；插入排序虽然比较次数和交换次数都更少，但在最坏情况下效率与冒泡排序和选择排序相当。

因此在实际应用中，我们要根据数据的特征来选择正确的排序算法，提高排序的效率。