TypeScript 算法手册 - 【冒泡排序】

【 已更新完 TypeScript 设计模式 专栏，感兴趣可以关注一下，一起学习交流🔥🔥🔥 】

TypeScript 算法手册 - 冒泡排序

1. 冒泡排序简介

1.1 冒泡排序定义

冒泡排序是一种简单的排序算法，重复地遍历要排序的数列，一次比较两个元素，他们的顺序错误就把他们交换过来。这个过程就像水底的气泡一样从底部向上"冒泡"到水面，这也是冒泡排序名字的由来。

用 TypeScript 代码表示一个简单的冒泡排序:

function bubbleSort(arr: number[]): number[] {
  const 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]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

1.2 冒泡排序特点

1. 简单直观: 冒泡排序是最简单的排序算法之一
2. 稳定性: 冒泡排序是一种稳定的排序算法
3. 原地排序: 冒泡排序是原地排序算法，不需要额外的存储空间

2. 冒泡排序步骤过程拆解

2.1 比较相邻元素

// 交换元素
if (arr[j] > arr[j + 1]) {
}

2.2 交换元素

// 交换元素
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

2.3 重复过程

// 比较和交换
for (let i = 0; i < len - 1; i++) {
  for (let j = 0; j < len - 1 - i; j++) {}
}

3. 冒泡排序的优化

3.1 提前退出

// 提前退出
function bubbleSortOptimized(arr: number[]): number[] {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let 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;
}

3.2 记录最后交换位置

// 记录最后交换位置
function bubbleSortFurther(arr: number[]): number[] {
  let lastExchangeIndex = 0;
  let sortBorder = arr.length - 1;
  for (let i = 0; i < arr.length - 1; i++) {
    let isSorted = true;
    for (let j = 0; j < sortBorder; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        isSorted = false;
        lastExchangeIndex = j;
      }
    }
    sortBorder = lastExchangeIndex;
    if (isSorted) break;
  }
  return arr;
}

案例代码和动态图

const array = [29, 10, 14, 66, 37, 14];
const sortedArray = bubbleSort(array);
console.log(sortedArray); // [10, 14, 14, 29, 37, 66]

4. 冒泡排序的优点

1. 代码简单，容易理解
2. 稳定排序
3. 原地排序，不需要额外空间

5. 冒泡排序的缺点

1. 时间复杂度较高，为 O(n^2)
2. 交换次数过多

总结

冒泡排序是一种简单直观的排序算法,虽然效率不高,但是在处理小规模数据或者基本有序的数据时还是很有用的。理解冒泡排序的原理对于学习更复杂的排序算法也很有帮助。

喜欢的话就点个赞 ❤️,关注一下吧,有问题也欢迎讨论指教。感谢大家!!!

下期预告: TypeScript 算法手册 - 选择排序