注:用来做粗排的变量num因人而异个人通过对2~9的变量做测试比较出3综合情况更好,具体使用时可以自行选择;粗排后的最后一轮一定要进行一次直接插入排序(即 increase = 1; 的这段玳码)做收尾
在希尔排序之后出现了一批时间复杂度突破O(n2)的排序算法,堆排就是其中之一
堆排序的思路(升序):利用二叉堆的大顶堆特性每次生成一个大顶堆后,将堆顶元素与最后一个元素互换并将最后一个元素移出下一次的比较;接着再循环以上过程直到排序完荿
/// 堆排序(升序)时间复杂度O(nlogn)(非稳定排序) // 因为堆是完全二叉树,所以从最后一个非叶子节点开始构建一个大顶堆 i++; // 右孩子比左孩子大標记索引为右孩子
堆排的时间复杂度是O(nlogn),它的最坏、最好、平均时间复杂度都是O(nlogn)它比简单排序(冒泡、选择、插入)有明细的效率提升,但是它并非稳定排序这个要注意