请用 JavaScript 实现冒泡排序、快速排序或归并排序算法。 - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

呦，各位靓仔靓女，老司机我来也！今天咱们不聊妹子，不聊跑车，就聊聊代码，聊聊那些排序算法中的“扛把子”。准备好了吗？系好安全带，发车咯！

今天咱们主要唠嗑JavaScript里的排序算法，重点介绍冒泡排序、快速排序和归并排序。我会尽量用大白话，加上一些“骚操作”的代码示例，保证让你听得懂，看得明白，还能上手操作。

一、排序算法是个啥？（What is Sorting Algorithm？）

简单来说，排序算法就是把一堆乱七八糟的数据，按照某种规则（比如从小到大，从大到小，或者按字母顺序）排列整齐。就像你整理房间一样，把袜子、衣服、裤子分门别类放好，这就是一种排序。

在计算机世界里，排序算法的应用非常广泛，比如：

数据库查询： 数据库里的数据很多，需要快速找到你想要的数据，就需要用到排序。
搜索引擎： 搜索结果也是按照相关性排序的，越相关的结果越靠前。
数据分析： 对数据进行排序可以帮助我们更好地理解数据的分布和趋势。

二、冒泡排序：简单粗暴的邻居互换法（Bubble Sort）

冒泡排序，顾名思义，就像水里的气泡一样，一个个往上冒。它的核心思想是：

比较相邻的元素： 从第一个元素开始，跟它后面的元素比较，如果顺序不对，就交换它们的位置。
一轮又一轮的比较： 这样一轮下来，最大的元素就会像气泡一样“冒”到最后面。
重复操作： 然后再从头开始，重复上面的步骤，直到所有元素都排好序。

代码示例：

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]) { // 如果前面的元素比后面的大，就交换它们
        // ES6 的解构赋值，交换变量更方便
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        // 传统方法：
        // let temp = arr[j];
        // arr[j] = arr[j + 1];
        // arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

// 测试一下
let myArray = [5, 1, 4, 2, 8];
console.log("排序前：", myArray); // 输出: 排序前： [ 5, 1, 4, 2, 8 ]
let sortedArray = bubbleSort(myArray);
console.log("排序后：", sortedArray); // 输出: 排序后： [ 1, 2, 4, 5, 8 ]

代码解释：

bubbleSort(arr)：接收一个数组 arr 作为参数。
len = arr.length：获取数组的长度。
外层循环 for (let i = 0; i < len - 1; i++)：循环 len - 1 轮，因为每一轮都会把一个最大的元素放到最后面，所以最后一轮就不用再比较了。
内层循环 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]]：使用 ES6 的解构赋值来交换变量，这是一种更简洁的写法。你也可以使用传统的 temp 变量来交换。
return arr：返回排序后的数组。

冒泡排序的优缺点：

特性	优点	缺点
实现难度	简单易懂，容易实现	效率较低，时间复杂度为 O(n^2)，对于大型数据集，速度很慢。
稳定性	稳定排序（相同元素的相对位置不变）	即使数组已经排序好，仍然会进行所有轮次的比较，无法提前结束。可以通过增加一个标志位来优化，判断是否发生了交换。

优化版本 (加入标志位)：

function bubbleSortOptimized(arr) {
  let len = arr.length;
  let swapped; // 标志位，用于判断是否发生了交换
  for (let i = 0; i < len - 1; i++) {
    swapped = false; // 每一轮开始前，重置标志位
    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]];
        swapped = true; // 发生了交换，说明数组还需要排序
      }
    }
    if (!swapped) { // 如果没有发生交换，说明数组已经排好序了
      break; // 提前结束循环
    }
  }
  return arr;
}

// 测试一下
let myArray2 = [1, 2, 3, 4, 5]; // 已经排序好的数组
console.log("排序前：", myArray2);
let sortedArray2 = bubbleSortOptimized(myArray2);
console.log("排序后：", sortedArray2); // 输出: 排序后： [ 1, 2, 3, 4, 5 ]  (会提前结束)

三、快速排序：分而治之的王者（Quick Sort）

快速排序是一种非常高效的排序算法，它的核心思想是“分而治之”。

选择基准值（Pivot）： 从数组中选择一个元素作为基准值。通常选择第一个元素或者随机选择一个元素。
分区（Partition）： 将数组分成两个部分：
- 小于基准值的元素放在基准值的左边。
- 大于基准值的元素放在基准值的右边。
递归排序： 对左右两个子数组分别进行快速排序，直到子数组的长度为 1 或者 0。

代码示例：

function quickSort(arr) {
  if (arr.length <= 1) { // 递归的终止条件：数组长度小于等于 1
    return arr;
  }

  let pivotIndex = Math.floor(arr.length / 2); // 选择基准值的索引，这里选择中间的元素
  let pivot = arr.splice(pivotIndex, 1)[0]; // 取出基准值，splice会改变原数组
  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));
}

// 测试一下
let myArray3 = [10, 7, 8, 9, 1, 5];
console.log("排序前：", myArray3); // 输出: 排序前： [ 10, 7, 8, 9, 1, 5 ]
let sortedArray3 = quickSort(myArray3);
console.log("排序后：", sortedArray3); // 输出: 排序后： [ 1, 5, 7, 8, 9, 10 ]

代码解释：

quickSort(arr)：接收一个数组 arr 作为参数。
if (arr.length <= 1)：如果数组长度小于等于 1，说明已经排好序了，直接返回。这是递归的终止条件。
pivotIndex = Math.floor(arr.length / 2)：选择基准值的索引，这里选择中间的元素。你也可以选择第一个元素或者随机选择一个元素。
pivot = arr.splice(pivotIndex, 1)[0]：取出基准值，splice 方法会改变原数组，它会删除 pivotIndex 位置的元素，并返回被删除的元素组成的数组。
left 和 right 数组：用于存放小于基准值和大于等于基准值的元素。
for (let i = 0; i < arr.length; i++)：循环遍历数组，将元素放到 left 或者 right 数组中。
quickSort(left).concat([pivot], quickSort(right))：递归排序左右两个子数组，然后使用 concat 方法将它们和基准值合并起来。

快速排序的优缺点：

特性	优点	缺点
实现难度	相对冒泡排序复杂一些	最坏情况下，时间复杂度会退化到 O(n^2)，例如当数组已经排序好或者完全逆序时，每次选择的基准值都是最小或者最大的元素。但这种情况很少发生。
效率	平均时间复杂度为 O(n log n)，是所有内部排序算法中速度最快的。	不稳定排序（相同元素的相对位置可能会改变）。例如，一个数组 `[2, 2, 1]`，如果选择第一个 `2` 作为基准值，那么第一个 `2` 会被放到第二个 `2` 的后面。
空间复杂度	需要额外的空间来存储递归调用的栈帧，平均情况下空间复杂度为 O(log n)，最坏情况下空间复杂度为 O(n)。可以通过尾递归优化来减少空间复杂度，但 JavaScript 引擎对尾递归的支持并不好。

四、归并排序：稳定可靠的合并大师（Merge Sort）

归并排序也是一种基于“分而治之”思想的排序算法。它的核心思想是：

分割（Divide）： 将数组从中间分成两个子数组。
递归排序： 对左右两个子数组分别进行归并排序。
合并（Merge）： 将两个有序的子数组合并成一个有序的数组。

代码示例：

function mergeSort(arr) {
  if (arr.length <= 1) { // 递归的终止条件：数组长度小于等于 1
    return arr;
  }

  let middle = Math.floor(arr.length / 2); // 找到中间位置
  let left = arr.slice(0, middle); // 分割左子数组
  let right = arr.slice(middle); // 分割右子数组

  // 递归排序左右子数组
  let sortedLeft = mergeSort(left);
  let sortedRight = mergeSort(right);

  // 合并两个有序数组
  return merge(sortedLeft, sortedRight);
}

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));
}

// 测试一下
let myArray4 = [12, 11, 13, 5, 6, 7];
console.log("排序前：", myArray4); // 输出: 排序前： [ 12, 11, 13, 5, 6, 7 ]
let sortedArray4 = mergeSort(myArray4);
console.log("排序后：", sortedArray4); // 输出: 排序后： [ 5, 6, 7, 11, 12, 13 ]

代码解释：

mergeSort(arr)：接收一个数组 arr 作为参数。
if (arr.length <= 1)：如果数组长度小于等于 1，说明已经排好序了，直接返回。这是递归的终止条件。
middle = Math.floor(arr.length / 2)：找到中间位置。
left = arr.slice(0, middle) 和 right = arr.slice(middle)：分割左子数组和右子数组。slice 方法不会改变原数组。
sortedLeft = mergeSort(left) 和 sortedRight = mergeSort(right)：递归排序左右子数组。
merge(sortedLeft, sortedRight)：合并两个有序数组。
merge(left, right)：接收两个有序数组 left 和 right 作为参数。
result 数组：用于存放合并后的有序数组。
while (i < left.length && j < right.length)：循环比较左右数组的元素，将较小的元素放到 result 数组中。
result.concat(left.slice(i)).concat(right.slice(j))：将剩余的元素添加到 result 数组中。

归并排序的优缺点：

特性	优点	缺点
实现难度	相对快速排序简单一些	空间复杂度较高，需要额外的空间来存储临时数组，空间复杂度为 O(n)。
效率	时间复杂度稳定为 O(n log n)，不会出现最坏情况。	在某些情况下，可能比快速排序慢一些，因为需要进行额外的合并操作。
稳定性	稳定排序（相同元素的相对位置不变）。

五、总结：选择哪个排序算法？（Which Sorting Algorithm to Choose?）

算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	适用场景
冒泡排序	O(n^2)	O(n^2)	O(1)	稳定	适用于小规模数据，或者基本有序的数据。由于实现简单，也常用于教学示例。
快速排序	O(n log n)	O(n^2)	O(log n)	不稳定	适用于大规模数据，对性能要求较高的情况。但需要注意最坏情况的发生，可以采用随机选择基准值等方法来避免。
归并排序	O(n log n)	O(n log n)	O(n)	稳定	适用于对稳定性有要求的场景，例如排序链表。或者在内存空间有限的情况下，可以使用外部排序。

总的来说：

小规模数据： 冒泡排序或者插入排序（未讲，但也很简单）都可以。
大规模数据，追求速度： 快速排序通常是首选。
对稳定性有要求： 归并排序是更好的选择。
空间有限： 尽量避免归并排序，可以考虑堆排序（未讲，但也很重要）。

六、最后的唠叨（Final Words）

排序算法是编程的基础，理解它们的工作原理可以帮助我们更好地理解程序的性能瓶颈，并选择合适的算法来解决问题。希望今天的讲解能够帮助你更好地理解这些算法，并在实际开发中灵活应用。记住，代码不是死的，要灵活变通，才能成为真正的编程高手！

今天就到这里，下课！记得给老司机点个赞哦！溜了溜了~

发表回复 取消回复

发表回复取消回复