Appearance

Return to top
On this page

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

冒泡排序的说明 ​

冒泡排序是一种简单的排序方法

  • 通过两两比较相邻的元素并交换他们的位置，从而使整个序列按照顺序排列
  • 第一次排序后，最大值总会移动到数组的最后，那么就不需要再考虑这个最大值
  • 重复剩余元素的操作 最终就可以得到整个排序完成的数组，这种算法是稳定的，每个相等的元素位置不会发生变化
  • 而且在最坏情况下，时间复杂度为O(n^2)，在最好情况下，时间复杂度为O(n)。 因此，冒泡排序适用于数据规模小的场景。

冒泡排序的流程 ​

  1. 从第一个元素开始 逐一比较相邻元素的大小
  2. 如果前一个元素比后一个大，那么就交换位置
  3. 在第一轮比较结束之后，最大的元素被移动到了最后一个位置
  4. 在下一轮比较中，不用考虑最后一个位置的元素重复上述操作
  5. 每轮比较结束之后 需要排序的数量都会减一，直到没有需要排序的元素
  6. 排序结束
  7. 循环整个流程直到所有元素都被有序的排列为止

image

冒泡排序执行的代码 ​

ts
// 定义函数，用于实现冒泡排序算法
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]
// 定义函数，用于实现冒泡排序算法
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. 冒泡排序是一种时间复杂度较高的算法， 一般不用于大数据量的排序

image

冒泡排序的时间复杂度 ​

在冒泡排序中 每次比较两个相邻的元素，并且交换他们的位置，如果左边的元素比右边元素大，那么就交换他们的位置 这样的比较

  • 最好的情况下 数组已经是有序的 那么比较和交换的次数是最少的
  • 在这种情况下 比较的次数是 n-1 次 交换次数是0次 其中 n 是数组的长度
  • 最坏的情况下，数组是逆序的 那么比较和交换的次数是最多的
  • 在这种情况下 比较的次数还是 n - 1 次 交换的次数 n(n-1)/2次
  • 在平均情况下 比较和交换的次数取决于数组的排列方式
  • 一般来说， 平均情况下比较次数 是 n-1次 交换次数 n(n-1)/4次

冒泡排序的时间复杂度分析：

  • 最好情况：当序列已经有序，每次比较和交换操作都不会进行，只需要进行n-1次比较，时间复杂度为O(n)。

  • 最坏情况：当序列完全逆序，需要进行n-1轮比较和n-1次交换操作，时间复杂度为O(n^2)。

  • 平均情况：需要进行的比较和交换操作的次数在所有情况中的平均值，时间复杂度也是O(n^2)。

  • 由此可见，冒泡排序的时间复杂度主要取决于数据的初始顺序，最坏情况下时间复杂度是O(n^2)，不适用于大规模数据的排序。

在github 上编辑文档