选择排序

[toc]

1.执行流程

1. 从序列中找出最大的那个元素，然后与组末尾的元素交换位置
   执行完一轮后，最末未的那个元素就是最大的元
2. 忽略1中曾找到的最大元素，重复执行步骤1

2. dart代码

///
/// Author: liyanjun
/// description: 选择排序
///
List<int> selectSourt(List<int> list) {
  if (list == null || list.length == 0) {
    return [];
  }
  for (var end = list.length - 1; end > 0; end--) {
    int maxIndex = 0;
    for (var begin = 1; begin <= end; begin++) {
      if (list[maxIndex] <= list[begin]) {
        maxIndex = begin;
      }
    }
    int temp = list[maxIndex];
    list[maxIndex] = list[end];
    list[end] = temp;
  }
  return list;
}

运行测试

main(List<String> args) {
  List<int> list = IntergerTools.random(10, 1, 20);//生成随机数
  // List<int> list = IntergerTools.ascOrder(1, 1000);//有序
  //  List<int> list = IntergerTools.tailAscOrder(1, 10000, 2000);//尾部有序
  List<int> list2 = List.from(list);
  List<int> list3 = List.from(list);
  print("排序前：$list");
  // print(list2);
  TimesTools.test('selectSourt', () {
    List result = selectSourt(list);
     print("排序后：$result");
     bool isAs = IntergerTools.isAscOrder(result);//工具类判断是否有序，返回bool值
     print("是否有序：${isAs}");
     Asserts.test(isAs);//利用断言是否有序
  });
}

运行结果

排序前：[2, 7, 19, 13, 9, 4, 12, 19, 16, 10]
【selectSourt】
开始：2020-11-01 10:24:12.729606
排序后：[2, 4, 7, 9, 10, 12, 13, 16, 19, 19]
是否有序：true
结束 2020-11-01 10:24:12.738810
耗时：0.001 秒
-------------------------------------

总结

• 选择排序的交换次数要远远少于冒泡排序，平均性能由于冒泡排序
  因为冒泡排序每次比较都要进行交换，而选择在比较后只是记录最大值的位置，最后再进行交换一次，所以性能优于冒泡排序
• 最好、最坏、平均时间复杂度：O(n^2),空间复杂度：O(1),属于不稳定排序
• 选择最大值的部分，用堆进行优化，可以达到O(nlgn)