排序系列堆 / 二分插入

关注

发布于: 2020 年 05 月 05 日

堆排序是一种基于完全二叉树排序的一种，也是我排序算法中印象最为深刻的一个，因为有一次写一个堆排序算法，我直接用 java 语言构造出了一棵二叉树，不是基于数组下表的哦，而是一棵真正的树，当天大脑短路的不是一星半点，结果出来吹了一阵风，一下子反应过来，哪有那么复杂，哈哈，分享一下自己的趣事，下面我们开始介绍堆排序。

堆排序

堆排序的技巧就在于完全二叉树的父子节点的定位能和数组下标完美的对应起来，其核心思想，首先根据将数组进行建堆操作（这里已大顶堆举例），大顶堆需要二叉树的父节点要大于子节点，整理完成后的数组输出堆顶节点，并将堆尾节点替换至堆顶，然后对堆进行调整，输出此时的堆顶元素，然后以此类推，直到堆中剩余一个元素输出，输出的序列即为有序，代码如下：

public static void heap(int[] nums, int parent, int size) {    if (parent < size) {        int left = 2 * parent + 1;        int right = 2 * parent + 2;        int max = parent;        if (left < size && nums[left] > nums[max]) max = left;        if (right < size && nums[right] > nums[max]) max = right;
        if (max != parent) {            swap(nums, max, parent);            heap(nums, max, size);        }    }}
public static void buildHeap(int[] nums, int size) {    for (int i = size - 1; i >= 0; i--) {        heap(nums, i, size);    }}
public static void sort(int[] nums) {    for (int i = 0; i < nums.length; i++) {        buildHeap(nums, nums.length - i);        //交换        swap(nums, 0, nums.length - 1 - i);    }}

复制代码

每次进行建堆的时间复杂度为 O(lgn)，所以其时间复杂度为 O(nlgn)，堆排序是不稳定的排序算法，此外，堆排序虽然为一种排序算法，但是真正用堆排序来排序的少之又少，堆排序通常应用在对数据的查找中，比如查找一堆数中的前 n 大数，这时维护一个 n 个元素的大顶堆就可以了。

二分插入排序

在这里有限的篇幅介绍一下二分插入排序，二分插入排序即在简单插入排序上，在数组前面已经排定的数据上使用二分查找来确定下一个插入元素的插入位置，

public static void sort4(int[] a, int n) {    int i, j, left, right, mid, x;    for (i = 1; i < n; i++) {        x = a[i];        left = 0;        right = i - 1;        while (left <= right) {            mid = (left + right) / 2;            if (x > a[mid]) {                left = mid + 1;            } else right = mid - 1;        }        for (j = i - 1; j >= left; j--) {            a[j + 1] = a[j];        }        a[j + 1] = x;    }}

复制代码

总结

堆排序主要利用了完全二叉树的父子与数组下标的对应关系，从而每次构造出一个堆，每次替换堆顶元素，从而构造出一个有序序列；二分插入也是利用插入排序前半部分已经有序的特性，从而使用二分查找，快速定位插入元素位置，仔细体会这两种排序算法，有异曲同工之妙，哈哈，扯得有点远了，希望大家多多交流。

默认自己无能，无疑是给失败制造机会。——拿破仑

发布于: 2020 年 05 月 05 日阅读数: 74

原文链接:【http://xie.infoq.cn/article/b4e7769939b20de532e08b3b0】。文章转载请联系作者。

脚动两轮男之漂流小王子

关注

还未添加个人签名 2020.02.06 加入

还未添加个人简介

发布

暂无评论

创作场景

排序系列堆 / 二分插入

堆排序

二分插入排序

总结

脚动两轮男之漂流小王子

评论