堆排序改进 原创 排序算法 2021年7月16日 07:21 夏至未至 1010 当前内容 787 字，在路上，马上到，马上到 上一篇是堆排序的简单过程，自认为下面这种更为合适： 思想： 1.建立大堆； 2.取堆顶元素和堆尾元素交换；（此时，大堆已破坏，需要重新往下调整，恢复大堆） 3.恢复大堆前，需要减掉已经在正确位置的堆尾元素； 代码如下： ```cpp #pragma once // //建立大堆， void AdjustUp(int *a, int index,int size) { int child = index * 2 + 1; while (child < size) { if ((child + 1) < size && a[child] < a[child + 1]) { ++child; } if (a[child] > a[(child - 1) / 2]) { swap(a[child], a[index]); index = child; child = index * 2 + 1; } else { break; } } } void HeapSort(int *a,int size) { assert(a); //建大堆 for (int i = (size - 2) / 2; i >= 0; --i) { AdjustUp(a,i,size); } //排序 for (int i = 0; i < size; ++i) //++i是因为控制后边的 保证每次最后一个数个堆顶数交换 { swap(a[0], a[size-1-i]); AdjustUp(a, 0,size-1-i); } } ``` 本文标题： 堆排序改进 本文作者： 夏至未至 发布时间： 2021年7月16日 07:21 最近更新： 2021年7月28日 07:01 原文链接： 许可协议： 署名-非商业性-禁止演绎 4.0 国际(CC BY-NC-ND 4.0) 请按协议转载并保留原文链接及作者 排序方法(4) 堆排序(1) 上一个 《一棵开花的树》 下一个 基数排序 当前文章评论暂未开放,请移步至留言处留言。
