十四、排序

访问 www.coding-time.cn 阅读原文动画效果，体验更佳。

1.冒泡排序

冒泡排序是一种基础的排序算法。其基本思想是通过不断地比较相邻元素并在必要时进行交换，将最大（或最小）的元素"冒"到序列的一端。

bubble_sort

1）排序步骤

先来感受到冒泡排序的步骤吧。

以数组 [5, 3, 8, 4, 6]为例，冒泡排序的步骤如下：

• 第一轮排序：
  

比较相邻的元素。第一次比较5和3，5大于3，交换它们两个，数组变成 [3, 5, 8, 4, 6]；接着比较5和8，5小于8，不用交换，然后比较8和4，8大于4，交换，数组变为 [3, 5, 4, 8, 6]；最后比较8和6，8大于6，交换，数组变为 [3, 5, 4, 6, 8]。这样，第一轮比较结束后，最大的数8被排到了最后。

• 第二轮排序：
  

再次从前向后比较相邻的元素，这次因为8已经是最大的元素在末尾，所以不再参与比较。先比较3和5，3小于5，不用交换；然后比较5和4，5大于4，交换，数组变为 [3, 4, 5, 6, 8]；接着比较5和6，5小于6，不用交换。这样，第二轮排序结束，第二大的元素6也排到了它应该在的位置。

• 后续轮排序：
  

如此反复进行，每一轮比较的元素对都比上一轮少一对。直至完成所有的排序。

最终，数组 [5, 3, 8, 4, 6] 被排序为 [3, 4, 5, 6, 8]。

2）冒泡排序的实现

let array = [5, 3, 8, 4, 6];
for(let i = 0; i < array.length; i++) {
  for(let j = 0; j < array.length - i - 1; j++) {
    if(array[j] > array[j + 1]) {
      // 交换元素
      let temp = array[j];
      array[j] = array[j + 1];
      array[j + 1] = temp;
    }
  }}
console.log(array);  // 输出: [3, 4, 5, 6, 8]

此算法的时间复杂度为O(n^2)，因此在处理大量数据时可能效率较低。

带你读《图解算法小抄》十四、排序（2）https://developer.aliyun.com/article/1348148?groupCode=tech_library