乐趣区

关于前端:01冒泡排序

jiezi

TypeScript 实现十大排序算法 (一) – 冒泡排序

一. 冒泡排序的定义

冒泡排序是一种简略的排序办法。

  • 基本思路是通过两两比拟相邻的元素并替换它们的地位，从而使整个序列依照顺序排列。
  • 该算法一趟排序后，最大值总是会移到数组最初面，那么接下来就不必再思考这个最大值。
  • 始终反复这样的操作，最终就能够失去排序实现的数组。

这种算法是稳固的，即相等元素的绝对地位不会发生变化。

  • 而且在最坏状况下，工夫复杂度为 O(n^2)，在最好状况下，工夫复杂度为 O(n)。

因而，冒泡排序实用于数据规模小的场景。

二. 冒泡排序的流程

冒泡排序的流程如下：

  1. 从第一个元素开始，逐个比拟相邻元素的大小。
  2. 如果前一个元素比后一个元素大，则替换地位。
  3. 在第一轮比拟完结后，最大的元素被挪动到了最初一个地位。
  4. 在下一轮比拟中，不再思考最初一个地位的元素，反复上述操作。
  5. 每轮比拟完结后，须要排序的元素数量减一，直到没有须要排序的元素。
  6. 排序完结。
  7. 这个流程会始终循环，直到所有元素都有序排列为止。

三. 冒泡排序的图解

四. 冒泡排序的代码 

// 定义函数，用于实现冒泡排序算法
function bubbleSort(arr: number[]): number[] {
  // 外层循环，管制须要比拟的轮数
  for (let i = 0; i < arr.length - 1; i++) {
    // 内层循环，管制每轮须要比拟的次数
    for (let j = 0; j < arr.length - 1 - i; j++) {
      // 如果前一个元素比后一个元素大，则替换它们的地位
      if (arr[j] > arr[j + 1]) {[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  // 返回排序后的数组
  return arr;
}

// 测试代码
const arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr));
// 输入：[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

阐明：

  1. 冒泡排序是一种暴力枚举算法，通过屡次循环比拟相邻的元素，把最大的元素逐步冒泡到数组末端。
  2. 外层循环：管制排序的趟数，每一轮排序会把最大的元素放到最初，因而每次循环须要比拟的元素个数也会逐步缩小。
  3. 内层循环：比拟相邻元素，如果右边元素比左边元素大，则替换地位。
  4. 冒泡排序是一种工夫复杂度较高的算法，个别不用于大数据量的排序，但它很容易了解，是一种初学者学习排序算法的好

五. 冒泡排序的工夫复杂度

在冒泡排序中，每次比拟两个相邻的元素，并替换他们的地位，如果右边的元素比左边的元素大，则替换它们的地位。这样的比拟和替换的过程能够用一个循环实现。

  • 在最好的状况下，数组曾经是有序的，那么比拟和替换的次数是起码的。

    • 在这种状况下，比拟次数是 n - 1 次，替换次数是 0 次，其中 n 是数组的长度。

  • 在最坏的状况下，数组是逆序的，那么比拟和替换的次数是最多的。

    • 在这种状况下，比拟次数是 n - 1 次，替换次数是 n(n-1)/ 2 次，其中 n 是数组的长度。

  • 在均匀状况下，比拟和替换的次数取决于数组的排列形式。

    • 一般来说，均匀状况下比拟次数是 n - 1 次，替换次数是 n(n-1)/ 4 次，其中 n 是数组的长度。

冒泡排序的工夫复杂度剖析：

  • 最好状况：当序列曾经有序，每次比拟和替换操作都不会进行，只须要进行 n - 1 次比拟，工夫复杂度为 O(n)。
  • 最坏状况：当序列齐全逆序，须要进行 n - 1 轮比拟和 n - 1 次替换操作，工夫复杂度为 O(n^2)。
  • 均匀状况：须要进行的比拟和替换操作的次数在所有状况中的平均值，工夫复杂度也是 O(n^2)。

由此可见，冒泡排序的工夫复杂度次要取决于数据的初始程序，最坏状况下工夫复杂度是 O(n^2)，不适用于大规模数据的排序。

六. 冒泡排序的总结

  • 冒泡排序实用于数据规模较小的状况，因为它的工夫复杂度为 O(n^2)，对于大数据量的排序会变得很慢。
  • 同时，它的实现简略，代码实现也容易了解，实用于学习排序算法的初学者。
  • 然而，在理论的利用中，冒泡排序并不罕用，因为它的效率较低。
  • 此外，冒泡排序比拟和替换的次数较多，占用更多的存储空间和工夫，不适用于解决大数据量的状况。
  • 因而，在理论利用中，冒泡排序通常被更高效的排序算法代替，如疾速排序、归并排序等。

本文由 mdnice 多平台公布

退出移动版