常用的 JS 排序算法 整理版

下面是对“常用的JS排序算法 整理版”的完整攻略的详细讲解。

一、排序算法介绍

排序是计算机科学中的一个基本问题，它的目的是对一组元素进行升序或降序排列。JS中常用的排序算法包括 冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序等。

二、常用排序算法示例

下面是两个常用排序算法的示例：

1. 冒泡排序

冒泡排序是一种简单的排序算法，它重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换位置。代码实现如下：

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

2. 快速排序

快速排序是一种常见的排序算法，它采用了分治的思想。它选择一个基准数，将数列中小于基准数的数放在基准数的左边，大于基准数的数放在基准数的右边，然后递归地对左右无序区间进行同样的操作，直到整个序列有序。代码实现如下：

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2); // 取基准点
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

三、排序算法的时间复杂度

排序算法的时间复杂度是指该算法执行的基本操作次数，它可以衡量该算法的执行效率。常用的排序算法的时间复杂度如下：

排序算法	最好时间复杂度	最坏时间复杂度	平均时间复杂度
冒泡排序	O(n)	O(n²)	O(n²)
选择排序	O(n²)	O(n²)	O(n²)
插入排序	O(n)	O(n²)	O(n²)
希尔排序	O(n log n)	O(n log² n)	O(n log² n)
归并排序	O(n log n)	O(n log n)	O(n log n)
快速排序	O(n log n)	O(n²)	O(n log n)

四、排序算法的稳定性

排序算法的稳定性是指在排序过程中，相同元素的相对位置是否会发生变化。稳定的排序算法可以保证排序后相同元素的相对位置不会改变，不稳定的排序算法则不能保证。常用的排序算法的稳定性如下：

排序算法	是否稳定
冒泡排序	稳定
选择排序	不稳定
插入排序	稳定
希尔排序	不稳定
归并排序	稳定
快速排序	不稳定

五、总结

本文主要对常用的JS排序算法进行了介绍并给出了部分排序算法的代码示例，同时还介绍了排序算法的时间复杂度和稳定性，希望可以帮助读者更好地理解和掌握常用的JS排序算法。