java堆排序代码,堆排序实现

KLQ 2020-06-10 14:22:36 java常见问答 3270

下面要给大家带来的就是和堆排序算法相关的内容,一起来看看如何java实现吧!

先来看一下原始堆

java堆排序代码

堆排序算法

首先,构造出初始堆,从最后一个非叶节点开始调整,随后,选出叶子节点当中,比自己大的一个交换。

假如,交换之后的叶子节点不满足堆,那么就继续进行调整。

java堆排序代码

这里的话因为20和16交换之后导致了16不满足堆的性质,所以就要重新进行调整。

java堆排序代码

在初始堆构造好了之后,再把堆头元素交换到堆尾。

堆尾的元素已经是有序的,之后就一直进行重复,直到所有的都有序。

20已经是最大的了,将交换到堆尾。

java堆排序代码

之后,再从根节点3进行调整,之后,每次挑选出最大的放到堆尾,一直到所有的元素有序。

java堆排序代码

下面是java代码

/**
 * @author: gethin
 * @create: 2018-05-23 16:21
 * @description: 常用排序算法
 **/
public class Sort
{
    public static void main(String[] args)
    {
        int[] nums = {
            16
            , 7
            , 3
            , 20
            , 17
            , 8
        };
        headSort(nums);
        for (int num: nums)
        {
            System.out.print(num + " ");
        }
    }
    /**
     * 堆排序
     */
    public static void headSort(int[] list)
    {
        //构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
        for (int i = (list.length) / 2 - 1; i >= 0; i--)
        {
            headAdjust(list, list.length, i);
        }
        //排序,将最大的节点放在堆尾,然后从根节点重新调整
        for (int i = list.length - 1; i >= 1; i--)
        {
            int temp = list[0];
            list[0] = list[i];
            list[i] = temp;
            headAdjust(list, i, 0);
        }
    }
    private static void headAdjust(int[] list, int len, int i)
    {
        int k = i, temp = list[i], index = 2 * k + 1;
        while (index < len)
        {
            if (index + 1 < len)
            {
                if (list[index] < list[index + 1])
                {
                    index = index + 1;
                }
            }
            if (list[index] > temp)
            {
                list[k] = list[index];
                k = index;
                index = 2 * k + 1;
            }
            else
            {
                break;
            }
        }
        list[k] = temp;
    }
}

下面是堆排序的结果

java堆排序代码

今天和堆排序算法相关的代码实现就给大家分享到这里了。

你还想了解更多的java实例吗?可以继续通过本站来进行了解哦。

推荐阅读:

java继承例子代码,java类的继承示例

二叉树转化为森林例子要怎么实现?步骤有哪些?

二叉树的遍历图解例题详解