堆排序思想及代码实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了堆排序思想及代码实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3303字，纯文字阅读大概需要5分钟。

内容图文

堆排序思想及代码实现

前言

对于一个数组，如果要实现数组中元素从小到大进行排序，此时这种需求就可以利用堆排序进行实现。本文讲解如果利用堆排序实现数组元素从小到大进行排序。

一、实现步骤

1.构造堆；
2.得到堆顶元素，这个值就是最大值；
3.交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；
4.对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；
5.重复2~4这个步骤，直到堆中剩一个元素为止。

二、构造堆

1.由数组构造堆的思路一

堆的构造，最直观的想法就是另外再创建一个和新数组，然后从左往右遍历原数组，每得到一个元素后，添加到新数组中，并通过上浮，对堆进行调整，最后新的数组就是一个堆。

2.由数组构造堆的思路二

上述的方式虽然很直观，也很简单，但是我们可以用更聪明一点的办法完成它。创建一个新数组，把原数组的数据拷贝到新数组的1~length处，再从新数组长度的一半处开始往1索引处扫描（从右往左），然后对扫描到的每一个元素做下沉调整即可。
为什么是一半处？
因为堆的特性，前一半都是非叶子节点，后一半都是叶子节点，而叶子节点不能再下沉。

• 一次由数组构造堆的过程
  
  
  

3.思路二的具体代码实现

//根据原数组source，构造出堆heap
    private static void createHeap(Comparable[] source, Comparable[] heap)
    {
        //1.拷贝source数组到heap数组中（heap[0]元素不用），此时heap一个无序的堆
        System.arraycopy(source,0,heap,1,source.length);
        //2.对前一半元素使用下沉算法，使得heap成为真正有序的堆
        for (int i = (heap.length-1)/2; i >0 ; i--) {
            sink(heap,i,heap.length-1);
        }
    }

    //在heap堆中，对target处的元素做下沉，范围是0~range。
    private static void sink(Comparable[] heap, int target, int range)
    {
        //如果target位置结点的左子树存在，则循环遍历，将target位置结点与其左右子结点中较大的进行比较，若target位置处的结点小于较大的子结点，则交互
        while (2*target<=range)
        {
            int maxIndex;//左右结点中较大结点的索引
            //如果右结点存在，则比较左右子结点中较大的结点
            if (2*target+1<=range)
            {
                if (less(heap,2*target,2*target+1))
                {
                    maxIndex=2*target+1;
                }
                else
                    maxIndex=2*target;
            }
            //如果右结点不存在，则较大子结点就是左节点
            else
            {
                maxIndex=2*target;
            }

            //比较当前节点与较大子结点的大小，如果当前结点较小，则交换,否则，结束循环
            if(!less(heap,target,maxIndex))
            {
                break;
            }

            exch(heap,target,maxIndex);

            target=maxIndex;//继续下一次循环
        }
    }

    //判断heap堆中索引i处的元素是否小于索引j处的元素
    private static boolean less(Comparable[] heap, int i, int j)
    {
        return heap[i].compareTo(heap[j])<0;
    }
    //交换heap堆中i索引和j索引处的值
    private static void exch(Comparable[] heap, int i, int j)
    {
        Comparable temp=heap[i];
        heap[i]=heap[j];
        heap[j]=temp;
    }

三、堆排序

1.堆排序思路

对构造好的堆，我们只需要做类似于堆的删除操作，就可以完成排序。
1.将堆顶元素和堆中最后一个元素交换位置；
2.通过对堆顶元素下沉调整堆，把最大的元素放到堆顶(此时最后一个元素不参与堆的调整，因为最大的数据已经到了数组的最右边)
3.重复1~2步骤，直到堆中剩最后一个元素。

2.堆排序思路代码实现

 //对source数组中的数据从小到大排序
    public static void sort(Comparable[] source)
    {
        Comparable[] heap = new Comparable[source.length + 1];
        //创建堆
        createHeap(source,heap);
        int maxIndex = heap.length-1;
        //通过循环不断交互索引1和最大索引处的元素，并下沉元素1，排除最大索引处的结点
        while (maxIndex!=1)
        {
            exch(heap,1,maxIndex);
            maxIndex--;
            sink(heap,1,maxIndex);
        }
        //将堆数组拷贝到source数组
        System.arraycopy(heap,1,source,0,source.length);
    }

四、堆排序测试

//堆排序测试
public class HeapSortTest {
    public static void main(String[] args) {
        String[] arr = {"S","O","R","T","E","X","A","M","P","L","E"};
        HeapSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

内容总结

以上是互联网集市为您收集整理的堆排序思想及代码实现全部内容，希望文章能够帮你解决堆排序思想及代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---