JavaScript中几种排序算法的简单实现

排序算法在计算机科学中是一个基本问题。不同的排序算法具有不同的时间和空间复杂度，选择合适的排序算法可以提高程序的效率。本文介绍了JavaScript中几种排序算法的简单实现，包括冒泡排序、选择排序、插入排序、归并排序和快速排序。

冒泡排序

冒泡排序是最简单的排序算法之一。它重复遍历列表，比较相邻的元素，并交换它们的位置，直到整个列表被排序。以下是JavaScript中冒泡排序的实现：

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; 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;
}

这里使用了两个嵌套的for循环，时间复杂度为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;
      }
    }
    if (minIndex !== i) {
      let temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
    }
  }
  return arr;
}

虽然选择排序算法的时间复杂度也为O(n^2)，但是它比冒泡排序的性能要好一些。

插入排序

插入排序是一种简单直观的排序算法。它将列表分为已排序序列和未排序序列，从未排序序列中选择一个元素，在已排序序列中找到合适的位置并插入。重复这个过程，直到整个列表被排序。以下是JavaScript中插入排序的实现：

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

插入排序的时间复杂度是O(n^2)，和选择排序一样，但是对于“几乎有序”的列表，插入排序效果会很好。

归并排序

归并排序是一种高效的排序算法，使用了分治的思想。它将列表分为若干个子列表，然后对每个子列表排序，最后将排好序的子列表合并成一个有序的列表。以下是JavaScript中归并排序的实现：

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

function merge(left, right) {
  let result = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

归并排序的时间复杂度是O(nlogn)，比前面那几种排序算法要快得多。

快速排序

快速排序是一种高效的排序算法，使用了分治的思想。它选择一个基准元素，将列表分为小于基准元素和大于基准元素的两个子列表，并分别对它们进行排序。以下是JavaScript中快速排序的实现：

function quickSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  let pivot = arr[0];
  let left = [];
  let right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(pivot).concat(quickSort(right));
}

快速排序的时间复杂度是O(nlogn)，比归并排序要快一些。

总结

本文介绍了JavaScript中几种排序算法的简单实现，包括冒泡排序、选择排序、插入排序、归并排序和快速排序。每种排序算法都有各自的优缺点和适用场景，选择合适的排序算法可以提高程序的效率。