Java教程

堆排序(两种实现思路)

本文主要是介绍堆排序(两种实现思路),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

相信有了最大堆的实现基础,我们就可以开始考虑利用最大堆的特性,实现排序的功能。

1、第一种思路:需要开辟新的空间。
我们堆传入的数组,首先需要整理成最大堆的形式。我们循环遍历每个数组的元素,然后利用堆的add方法,最终把一个数组实现成最大堆的形式。然后我们开始循环遍历最大堆,每次都使用最大堆的取出最大元素的方法,不断的放入传入的数组里。循环结束后,我们的数组则是按照从大到小的顺序。最后再倒序一下数组,就完成了堆排序。

2、第二种思路:不需要开辟额外的空间,进行原地的排序。
这种方法我们称为Heapify。
第一步:我们首先堆数组实现原地的进行最大堆的实现。也就是从最后一个非叶子节点开始,从后往前,不断进行节点的下沉操作。如何获取最后一个非叶节点的位置呢,其实也就是最后一个索引的(index-2)/2 的计算。
第二步,我们循环地把索引为0 的位置和末尾位置的元素进行交换,这样我们便把最大值放在了最后。然后最元素为0的位置就行下沉操作,其中注意,我们下沉的时候,数组的大小需要减1,也就是不包含末尾已经排好序的元素。

具体的代码实现:

public class HeapSort {

    private HeapSort() {
    }

// 第一种方法
    public static <E extends Comparable<E>> void sort(E[] data) {
        MaxHeap<E> maxHeap = new MaxHeap<>();
        for (E e : data) {
            maxHeap.add(e);
        }

        for (int i = data.length - 1; i >= 0; i--) {
            data[i] = maxHeap.extractmax();
        }
    }

// 第二种方法
    public static <E extends Comparable<E>> void sort2(E[] data) {
        if (data.length <= 1) return;
        // 需要进行heapify
        // 从最后一个非叶子结点进行下沉操作
        // (data.length-2)/2
        for (int i = (data.length - 2) / 2; i >= 0; i--) {
            shifDown(data, i, data.length);
        }
        for (int i = data.length - 1; i >= 0; i--) {
            swap(data, 0, i);
            shifDown(data, 0, data.length - i);
        }
    }

    private static <E extends Comparable<E>> void shifDown(E[] data, int k, int n) {
        // 下沉操作,是个循环的操作
        // 下沉的节点大于0 并且左孩子也有
        while ( (2 * k) + 1 < n) {
            int j = (2 * k) + 1;
            if (j + 1 < n && data[j].compareTo(data[j + 1]) < 0) {
                j = j + 1;
            }
            if (data[k].compareTo(data[j]) >= 0) {
                break;
            }
            swap(data, k, j);
            k = j;
        }
    }

    private static <E extends Comparable<E>> void swap(E[] data, int k, int j) {
        E t = data[k];
        data[j] = data[k];
        data[k] = t;
    }
这篇关于堆排序(两种实现思路)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!