冒泡排序

[toc]

冒泡排序也叫气泡排序

1.执行流程

1. 从头开始比较每一-对相邻元素， 如果第1个比第2个大，就交换它们的位置
   V执行完一轮后,最末尾那个元素就是最大的元素
2. 忽略1中曾经找到的最大元素，重复执行步骤1，直到全部元素有序

2. dart代码

///
/// Author: liyanjun
/// description: 正常冒泡排序
///
List<int> bubbleSort(List<int> list) {
  for (var end = list.length-1 ; end > 0; end--) {
    for (var i = 1; i <= end; i++) {
      if (list[i - 1] > list[i]) {
        int temp = list[I];
        list[i] = list[i - 1];
        list[i - 1] = temp;
      }
    }
  }
  return list;
}

2.1优化1

完全有序，提前终止

///
/// Author: liyanjun
/// description: 优化1 完全有序，提前终止
///
List<int> bubbleSortBetter1(List<int> list) {
 
  for (var end = list.length-1 ; end > 0; end--) {
     bool sorted = true;
    for (var i = 1; i <= end; i++) {
      if (list[i - 1] > list[i]) {
        int temp = list[I];
        list[i] = list[i - 1];
        list[i - 1] = temp;
        sorted = false;
      }
    }
    if (sorted == true) {
      break;
    }
  }
  return list;
}

2.1.1比较

main(List<String> args) {
  // List<int> list = IntergerTools.random(10000, 1, 100000);
  List<int> list = IntergerTools.ascOrder(1, 1000);
  List<int> list2 =  List.from(list);
  // print(list);
  // print(list2);
  TimesTools.test('bubbleSort', (){
     bubbleSort(list);
  });

  TimesTools.test('bubbleSortBetter1', (){
     bubbleSortBetter1(list2);
  });
}

运行结果

【bubbleSort】
开始：2020-10-31 23:27:27.211104
结束 2020-10-31 23:27:27.220070
耗时：0.004 秒
-------------------------------------
【bubbleSortBetter1】
开始：2020-10-31 23:27:27.222868
结束 2020-10-31 23:27:27.223209
耗时：0.001 秒
-------------------------------------
Exited

2.2优化2

如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
比如
[图片上传失败...(image-6e8580-1604321580519)]
最后一次交换是6，后面的不用比较

///
/// Author: liyanjun
/// description: 优化2 
/// 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
/// 
///
List<int> bubbleSortBetter2(List<int> list) {
 
  for (var end = list.length-1 ; end > 0; end--) {
   // sortedIndex的初始值在数组完全有序的时候有用,一轮结束
     int sortedIndex = 1;
    for (var i = 1; i <= end; i++) {
      if (list[i - 1] > list[i]) {
        int temp = list[I];
        list[i] = list[i - 1];
        list[i - 1] = temp;
        sortedIndex = I;
      }
    }
    end = sortedIndex;
  }
  return list;
}

2.2.1比较

main(List<String> args) {
  List<int> list = IntergerTools.random(10000, 1, 100000);
  // List<int> list = IntergerTools.ascOrder(1, 1000);
  List<int> list2 =  List.from(list);
  // print(list);
  // print(list2);
  TimesTools.test('bubbleSort', (){
     bubbleSort(list);
  });

  TimesTools.test('bubbleSortBetter2', (){
     bubbleSortBetter2(list2);
  });
}

执行结果

【bubbleSort】
开始：2020-10-31 23:26:02.962461
结束 2020-10-31 23:26:03.223240
耗时：0.252 秒
-------------------------------------
【bubbleSortBetter2】
开始：2020-10-31 23:26:03.224387
结束 2020-10-31 23:26:03.394767
耗时：0.17 秒
-------------------------------------

3 复杂度

原始

• 平均时间复杂度：O(n^2)
• 空间复杂度：O(1)

优化1

• 最坏的平均时间复杂度：O(n^2)
• 罪好的平均时间复杂度：O(n)
• 空间复杂度：O(1)

优化2

• 最坏的平均时间复杂度：O(n^2)
• 罪好的平均时间复杂度：O(n)
• 空间复杂度：O(1)

4.注意

4.1稳定排序

冒泡算法是稳定的排序算法
但是稍有不慎,稳定的排序算法也能被写成不稳定的排序算法，比如"下面的冒泡排序代码是不稳定的
比如代码中

 if (list[i - 1] > list[i]) {
        int temp = list[I];
        list[i] = list[i - 1];
        list[i - 1] = temp;
      }

换成

 if (list[i - 1] >= list[i]) {
        int temp = list[I];
        list[i] = list[i - 1];
        list[i - 1] = temp;
      }

就会变成不稳定排序

4.2 原地算法

冒泡排序属于In-place