【Flutter之Dart算法】冒泡排序算法

每日一新，共同前进。

大家好，我是Asscre。

在日常研发的过程中，我们无时无刻都在考虑自己开发的程序是否高效，一段好的程序执行离不开对算法的深刻认识和熟练掌握。接下来的日子，我将带着大家一起重温一下常见的几种算法。

【Flutter之Dart算法】系列二 冒泡排序算法

描述：

冒泡算法，将数组中前后两个元素进行比较，根据排序规则进行大小交换，最后得到一个从小到大或者从大到小的数组；通过冒泡排序处理的时间复杂度为 O(n^2)

实现步骤：

• 前后两个元素进行比较，根据排序规则进行大小交换
• 依次向后移动

冒泡排序算法实现

void main() {
  List<int> ary = [4, 5, 1, 3, 6, 2, 5, 6, 7, 2, 4, 1];
  print(bubbleSort(ary));
}

//冒泡排序
List<int> bubbleSort(List<int> arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        int iv = arr[i]; // 深拷贝
        arr[i] = arr[j];
        arr[j] = iv;
      }
    }
  }
  return arr;
}

结果：

拓展知识点：

Dart 语言中的深拷贝和浅拷贝

首先我们需要先了解：深拷贝和浅拷贝区别是，在有指针的情况下，浅拷贝只是增加了一个指针指向已经存在的内存，而深拷贝就是增加一个指针并且申请一个新的内存，使这个增加的指针指向这个新的内存，采用深拷贝的情况下，释放内存的时候就不会出现在浅拷贝时重复释放同一内存的错误。

void main() {
  int a = 1;
  int b = 2;
  int c = a;
  print('修改之前：a: $a, b:$b, c:$c');

  c = 3;
  void setB(int value) {
    value = 4;
  }

  setB(b);

  print('修改之前：a: $a, b:$b, c:$c');

  int d = 4;
  int e = d;
  print('修改之前: e:$e');
  d = 5;
  print('修改之后：e:$e');

  List<int> arr = [1, 2, 3, 4];
  List<int> ary = arr;
  List<int> arx = [...arr];
  arr[0] = 5;

  print('arr: $arr');
  print('ary: $ary');
  print('arx: $arx');
}

结果：

通过上述代码，我们可以得知：

1. 简单类型中，如int，通过赋值的方法为深拷贝；
2. 复杂类型中，如List，通过赋值的方法为浅拷贝；
3. 复杂类型中，如List，可以通过 ... 进行深拷贝；

至此，我们就重新温习了一下 冒泡排序算法 ！

感谢阅读！每日进步一点！未来赚（搬）钱（🧱）容易一点！

关注Asscre，让我们一起加油⛽️