堆排序

[toc]

堆排序是选择排序的一种优化

1.执行流程

1. 对序列进行原地建堆
2. 重复执行下面的操作，直到对的元素数量为1
   1. 交换对顶元素与尾元素
   2. 堆的元素数量减1
   3. 对0位置进行一次下滤操作

2.代码

import 'sort.dart';

class HeapSort extends Sort {
 HeapSort(List<int> list ) : super( list); 
  int _heapSize;
  @override
  sort() {
    //原地建堆
    _heapSize = list.length;
    for (int i = (_heapSize >> 1) - 1; i >= 0; i--) {
      _siftDown(i);
    }

    //取出
    while (_heapSize > 1) {
      //交换对顶元素和尾部元素交换
      swap(0, _heapSize - 1);
      //堆的元素数量减1
      _heapSize -= 1;
      //对0位置进行一次下滤操作(恢复堆的性质)
      _siftDown(0);
    }
  }

  _siftDown(int index) {
    int element = list[index];
        int half = _heapSize >> 1;
    // 第一个叶子节点的索引 == 非叶子节点的数量
        // index < 第一个叶子节点的索引
        // 必须保证index位置是非叶子节点
        while (index < half) { // index必须是非叶子节点
        // index的节点有2种情况
            // 1.只有左子节点
            // 2.同时有左右子节点

            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            int child = list[childIndex];
                // 右子节点
            int rightIndex = childIndex + 1;
            // // 选出左右子节点最大的那个  右子节点比左子节点大
            if (rightIndex < _heapSize && 
                    cmpElement (list[rightIndex], child) > 0) { 
        childIndex = rightIndex;
                child = list[rightIndex];
            }
            // 大于等于子节点
            if (cmpElement(element, child) >= 0) break;
            // 将子节点存放到index位置
            list[index] = child;
        // 重新设置index
            index = childIndex;
        }
        list[index] = element;
  }
}

3.校验

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);
  print("排序前：$list");
 

TimesTools.test('堆排序', () {
  HeapSort heapSort = HeapSort(list)..sortPrint();
  print("排序后：${heapSort.list}");

});

执行结果

排序前：[3, 11, 13, 15, 6, 13, 18, 9, 12, 1]
【堆排序】
开始：2020-11-01 13:36:03.273879
排序后：[1, 3, 6, 9, 11, 12, 13, 13, 15, 18]
结束 2020-11-01 13:36:03.281046
耗时：0.002 秒
-------------------------------------

总结

• 最好、最坏、平均时间复杂度都是 O(nlogn)，空间复杂度：O(1),属于不稳定排序