已实现基础BubbleSort，如何在Dart中编写优化版冒泡排序？

你的原始冒泡排序实现可以从两个核心方向优化，减少不必要的遍历操作：

优化点说明 #

• 缩小内层循环范围：每一轮排序后，数组末尾的i个元素已经是有序的（最大的元素会被逐步"冒泡"到末尾），内层循环无需再遍历这些已排序元素。
• 提前终止排序：如果某一轮遍历中没有发生任何元素交换，说明整个数组已经完全有序，直接结束排序流程，避免后续无意义的循环。

基础优化版代码 #

void optimizedBubbleSort(List<int> list) {
  int n = list.length;
  for (int i = 0; i < n; i++) {
    // 标记当前轮是否发生交换
    bool swapped = false;
    // 内层循环只遍历未排序部分，减去已排好的i个元素
    for (int j = 0; j < n - 1 - i; j++) {
      if (list[j] > list[j + 1]) {
        // 交换元素
        int temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
        swapped = true;
      }
    }
    // 无交换则数组已完全有序，直接退出循环
    if (!swapped) break;
  }
  print(list);
}

void main() {
  List<int> list = [2, 5, 3, 15, 20, 5, 2, 7, 9];
  optimizedBubbleSort(list);
}

进阶优化版（记录最后交换位置） #

如果想进一步压缩遍历范围，可以记录每一轮最后一次交换的位置，下一轮只需遍历到该位置即可——该位置之后的元素已经有序，能进一步减少比较次数：

void advancedOptimizedBubbleSort(List<int> list) {
  int n = list.length;
  // 记录最后一次交换的位置
  int lastSwapIndex = n - 1;
  while (lastSwapIndex > 0) {
    int currentSwapIndex = 0;
    for (int j = 0; j < lastSwapIndex; j++) {
      if (list[j] > list[j + 1]) {
        int temp = list[j];
        list[j] = list[j + 1];
        list[j + 1] = temp;
        currentSwapIndex = j;
      }
    }
    // 更新最后交换位置，缩小下一轮遍历范围
    lastSwapIndex = currentSwapIndex;
  }
  print(list);
}

void main() {
  List<int> list = [2, 5, 3, 15, 20, 5, 2, 7, 9];
  advancedOptimizedBubbleSort(list);
}

这两个优化版本都能将冒泡排序在数组已有序的最好情况时间复杂度从O(n²)降到O(n)，优化效果显著。

内容的提问来源于stack exchange，提问作者Mohmed Ashraf