排序算法

[toc]

10大经典排序比较

image.png

冒泡、选择、插入、归并、快速、希尔、堆排序,属于比较排序(Comparison Sorting)

算法的静态网站
2.visualization

排序算法的稳定性

如果相等的2个元素,在排序前后的相对位置保持不变，那么这是稳定的排序算法

• 排序前 :5，1，3(a),4,7,3(b)
• 稳定排序：1，3(a)，3(b)，4，5，7
• 不稳定排序：1，3(b)，3(a)，4，5，7

对自定义对象排序时，稳定性影响最终的排序结果

算法	是否稳定性
冒泡排序	是

原地算法

• 不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
• 空间复杂度为O(1)的都可以任务实施原地算法

非原地算法，称为Not-in-placke或者Out-of-placle
十大排序的是否为原地算法如上图

提前准备类

抽象类

import '../tools/date_utl.dart';

///
/// Author: liyanjun
/// /// Date: 2020-11-01 10:41:34
/// FilePath: /algorithm/sort/sort.dart
/// Description: 排序的超类
///
abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> {
  // abstract class Sort<T implements Comparable<T>>   {
  List<T> list;
  int cmpCount = 0; //比较次数
  int swapCount = 0; //交换次数
  int time; //耗时时间

  setList(List<T> list) {
    this.list = list;
  }

  sortPrint() {
    if (list == null || list.length < 2) return;
    int begin = DateUtil.getNowDateMs();
    sort();
    int end = DateUtil.getNowDateMs();
    time = end - begin;
  }

  sort();

  ///
  /// Author: liyanjun
  /// description:
  /// 返回值等于0，代表 list[i1] == list[i2]
  /// 返回值小于0，代表 list[i1] < list[i2]
  /// 返回值大于0，代表 list[i1] > list[i2]
  ///
  ///
  int cmpWithIndex(int i1, int i2) {
    cmpCount += 1;
    return list[i1].compareTo(list[i2]);
  }

  ///
  /// Author: liyanjun
  /// description:
  // 返回值等于0，代表 v1 == v2
  /// 返回值小于0，代表 v1  < v2
  /// 返回值大于0，代表 v1  > v2
  int cmpElement(T v1, T v2) {
    cmpCount += 1;
    return v1.compareTo(v2);
  }

  ///
  /// Author: liyanjun
  /// description: 交换两个索引位置
  ///

  void swap(int i1, int i2) {
    swapCount += 1;
    T tmp = list[i1];
    list[i1] = list[i2];
    list[i2] = tmp;
  }

  ///
  /// Author: liyanjun43
  /// description: 格式化
  ///
  String _numberString(int number) {
    if (number < 10000) return "$number";

    if (number < 100000000) return "${(number / 10000.0).toStringAsFixed(2)}万";

    return "${(number / 100000000.0).toStringAsFixed(2)}亿";
  }

  ///
  /// Author: liyanjun
  /// description:按照时间排序，如果时间相等，比较比较次数，如果再相等比较交互次数
  ///
  @override
  int compareTo(Sort o) {
    int result = (time - o.time);
    if (result != 0) return result;
    result = cmpCount - o.cmpCount;
    if (result != 0) return result;
    return swapCount - o.swapCount;
  }

  @override
  String toString() {
    // TODO: implement toString
    String timeStr = "耗时：${time / 1000.0}s (${time}ms)";
    String compareCountStr = "比较：${_numberString(cmpCount)}";
    String swapCountStr = "交换：${_numberString(swapCount)}";
    // String stableStr = "稳定性：" + isStable();
    return "【" +
        this.runtimeType.toString() +
        "】\n"
        // + stableStr + " \t"
        +
        timeStr +
        " \t" +
        compareCountStr +
        "\t " +
        swapCountStr +
        "\n" +
        "-----------------";
    // return super.toString();
  }
}

数组操作的类

import 'dart:math';

class IntergerTools {
  ///
  /// Author: liyanjun
  /// description: 生成随机数
  ///
  static List<int> random(int count, int min, int max) {
    if (count <= 0 || min > max) return null;
    List<int> array = List<int>(count);
    int delta = max - min + 1;
    for (int i = 0; i < count; i++) {
      array[i] = min + Random().nextInt(delta);
    }
    return array;
  }

  ///
  /// Author: liyanjun
  /// description: 合并两个list
  ///
  static List combine(List array1, List array2) {
    if (array1 == null || array2 == null) return null;
    List array = [];
    for (int i = 0; i < array1.length; i++) {
      array[i] = array1[i];
    }
    for (int i = 0; i < array2.length; i++) {
      array[i + array1.length] = array2[i];
    }
    return array;
  }

  ///
  /// Author: liyanjun
  /// description:
  ///
  static List same(int count, int unsameCount) {
    if (count <= 0 || unsameCount > count) return null;
    List array = [];
    for (int i = 0; i < unsameCount; i++) {
      array[i] = unsameCount - i;
    }
    for (int i = unsameCount; i < count; i++) {
      array[i] = unsameCount + 1;
    }
    return array;
  }

   static List<int> headTailAscOrder(int min, int max, int disorderCount) {
    List<int> array = ascOrder(min, max);
    if (disorderCount > array.length) return array;

    int begin = (array.length - disorderCount) >> 1;

    reverse(array, begin, begin + disorderCount);
    return array;
  }

   static List<int> centerAscOrder(int min, int max, int disorderCount) {
    List<int> array = ascOrder(min, max);
    if (disorderCount > array.length) return array;
    int left = disorderCount >> 1;
    reverse(array, 0, left);

    int right = disorderCount - left;
    reverse(array, array.length - right, array.length);
    return array;
  }

     static List<int> headAscOrder(int min, int max, int disorderCount) {
    List<int> array = ascOrder(min, max);
    if (disorderCount > array.length) return array;
    reverse(array, array.length - disorderCount, array.length);
    return array;
  }

   static List<int> tailAscOrder(int min, int max, int disorderCount) {
    List<int> array = ascOrder(min, max);
    if (disorderCount > array.length) return array;
    reverse(array, 0, disorderCount);
    return array;
  }

  static List<int> ascOrder(int min, int max) {
    if (min > max) return null;
    List<int> array = List<int>(max - min + 1);
    for (int i = 0; i < array.length; i++) {
      array[i] = min++;
    }
    return array;
  }

  static List<int> descOrder(int min, int max) {
    if (min > max) return null;
    List<int> array = List<int>(max - min + 1);
    for (int i = 0; i < array.length; i++) {
      array[i] = max--;
    }
    return array;
  }

  /**
   * 反转一个数组，索引范围是[begin, end)
   */
   static void reverse(List<int> array, int begin, int end) {
    int count = (end - begin) >> 1;
    int sum = begin + end - 1;
    for (int i = begin; i < begin + count; i++) {
        int j = sum - i;
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
  }



   static bool isAscOrder(List<int> array) {
    if (array == null || array.length == 0) return false;
    for (int i = 1; i < array.length; i++) {
        if (array[i - 1] > array[i]) return false;
    }
    return true;
  }

  
}

时间类

import 'date_utl.dart';

///
/// Date: 2020-10-31 22:51:08
/// FilePath: /sort/tools/times_tools.dart
/// Description: 测试时间的工具类
///


class TimesTools {
    static  final DateFormat _fmt = DateFormat.DEFAULT;
    
    
     static void test(String title, Function task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        print(title);
    print("开始：${DateUtil.getDateStrByDateTime(DateTime.now(),format: _fmt)}");
        int begin =  DateUtil.getNowDateMs();
        task();
        int end =  DateUtil.getNowDateMs();
      print("结束 ${DateUtil.getDateStrByDateTime(DateTime.now(),format: _fmt)}");
        double delta = (end - begin) / 1000.0;
      print("耗时：$delta 秒");
        print("-------------------------------------");
    }
}

断言判断类

///
/// Author: liyanjun
/// Date: 2020-11-01 10:10:37
/// FilePath: /algorithm/tools/assert.dart
/// Description: 利用断言判断结果
///

class Asserts {
static  void  test(bool value ){
  try {
    if (value == false) {
      throw Exception("测试未通过");
    }
  } catch (e) {
     print('异常: $e');
     rethrow;
  }
  }
}

排序算法对比

main(List<String> args) {
  List<int> list = IntergerTools.random(10000, 1, 20000); //生成10000个数，最小是1，最大是20000
  // List<int> list = IntergerTools.random(10, 1, 20); //生成10000个数，最小是1，最大是20000
  List<Sort> sortList = [
      HeapSort<num>(),//堆排序
    SelectSort<num>(),//选择排序
    BubbleSort2<num>(),//冒泡排序
    BubbleSort1<num>(),//冒泡排序优化1 完全有序，提前终止
    BubbleSort<num>(),//冒泡排序优化2 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数
    InsertSort<num>(),//插入排序
    InsertSort1<num>(),//插入排序优化1：改为挪动不是替换
    InsertSort2<num>(),//插入排序优化2：改为二分查找
    MergeSort<num>(),//归并排序
    QuickSort<num>(),//快速排序
    ShellSort<num>(),//希尔排序
  ];
  testSorts(list, sortList);
}

void testSorts(List<int> list, List<Sort> sorts) {
  // print('排序前 ：$list');
  for (Sort sort in sorts) {
    List<int> newList = List.from(list);
    sort.setList(newList);
    sort.sortPrint();
    Asserts.test(IntergerTools.isAscOrder(sort.list));
    //  print('排序后 ：${sort.list}');
  }
  sorts.sort(); //比较
  for (Sort sort in sorts) {
    print(sort);
  }
}
    

结果

【QuickSort<num>】
耗时：0.005s (5ms)     比较：16.30万    交换：6536
-----------------
【ShellSort<num>】
耗时：0.006s (6ms)     比较：19.66万    交换：0
-----------------
【HeapSort<num>】
耗时：0.006s (6ms)     比较：23.53万    交换：9999
-----------------
【InsertSort2<num>】
耗时：0.084s (84ms)    比较：11.91万    交换：0
-----------------
【InsertSort1<num>】
耗时：0.115s (115ms)   比较：2533.10万  交换：0
-----------------
【SelectSort<num>】
耗时：0.146s (146ms)   比较：4999.50万  交换：9999
-----------------
【InsertSort<num>】
耗时：0.178s (178ms)   比较：2533.10万  交换：2532.10万
-----------------
【BubbleSort1<num>】
耗时：0.488s (488ms)   比较：4999.23万  交换：2532.10万
-----------------
【BubbleSort2<num>】
耗时：0.506s (506ms)   比较：4997.58万  交换：2532.10万
-----------------
【BubbleSort<num>】
耗时：0.506s (506ms)   比较：4999.50万  交换：2532.10万
-----------------