冒泡排序（Bubble Sort）

介绍

冒泡排序是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素， 如果它们的顺序错误就把它们交换过来。走访数列的工作是重复进行的，直到没有再需要交换的元素为止， 这时数列就完全排序好了。这个算法的名字由来是因为越小（或越大）的元素会经过交换慢慢“浮”到数列的顶端，故名冒泡排序。

拉胯

最容易理解，但也是最拉胯的排序算法。

动画模拟

工作原理

冒泡排序的基本思想是：通过对待排序序列从前向后（或从后向前），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

具体来说，冒泡排序算法的执行过程如下：

• 比较相邻的元素：如果第一个比第二个大（或小，根据排序顺序决定），就交换它们两个。
• 对每一对相邻元素做同样的工作：从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大数（或最小数）。
• 针对所有的元素重复以上的步骤：除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤：直到没有任何一对数字需要比较。

算法特性

稳定性： 冒泡排序是一种稳定的排序算法，即如果两个相等元素的相对位置在排序前和排序后保持不变。

时间复杂度：

• 最优时间复杂度：O(n)（当输入数组已经是排序好的情况下，只需进行一次遍历即可确定数组已排序）。
• 最坏时间复杂度：O(n^2)（当输入数组是逆序的情况下，需要进行n*(n-1)/2次比较和交换）。
• 平均时间复杂度：O(n^2)。

空间复杂度： O(1)（因为冒泡排序是原地排序算法，不需要额外的存储空间）。

源码

<script setup lang="ts">
import SortBarChart from "../comp/sort-bar-chart.vue";
import { onBeforeUnmount, ref } from "vue";
import { genRandArray, sortExchangeReact } from "../sort.util";
import { sleep } from "../../../utils/cmm.util";

const data = ref<number[]>(genRandArray(1, 100, 100));

const refreshData = () => {
  data.value = genRandArray(1, 100, 100);
};

const actives = ref<number[]>([]);
const stepInterval = ref<number>(20);
const sorting = ref<boolean>(false);

/**
 * 冒泡排序开始
 */
const sort = async () => {
  for (let i = data.value.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      actives.value = [j, j + 1];
      if (data.value[j] > data.value[j + 1]) {
        await sleep(stepInterval.value);
        sortExchangeReact(data.value, j, j + 1);
      }
    }
  }
};

onBeforeUnmount(() => {
  sorting.value = false;
});
</script>

<template>
  <div class="">
    <a-space direction="horizontal">
      <a-input-number v-model="stepInterval" :step="50" :min="5" style="width: 200px">
        <template #suffix>ms</template>
        <template #prefix> 步进间隔 </template>
      </a-input-number>
      <a-button @click="sort()">开始排序</a-button>
      <a-button @click="refreshData">刷新数据</a-button>
    </a-space>
    <div class="mt-sm" style="height: 300px">
      <sort-bar-chart :data="data" :actives="actives" />
    </div>
  </div>
</template>

<style scoped lang="less"></style>