堆排序思想及代码实现

2024-01-29 12:22:16

堆排序思想及代码实现

前言

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

一、实现步骤

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));
    }
}

码农公寓