詳解如何在Java中實(shí)現(xiàn)堆排序算法

更新時(shí)間：2022年03月25日 09:35:36 作者：之一Yo

這篇文章主要為大家詳細(xì)介紹了如何利用Java實(shí)現(xiàn)堆排序算法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

算法描述

堆排序算法的描述如下：

將待排序的數(shù)組調(diào)整為最大堆，此時(shí)未排序的長(zhǎng)度 N 為數(shù)組的長(zhǎng)度，調(diào)整的過(guò)程就是倒序?qū)?shù)組的前 N/2 個(gè)元素下沉的過(guò)程，每次下沉都會(huì)將較大的元素帶到上面，最終將數(shù)組變?yōu)樽畲蠖眩?/li>
彈出最大堆的堆頂元素并將其移動(dòng)到數(shù)組的最后面，將原本最后面的元素放到堆頂，然后將未排序的長(zhǎng)度 N - 1，調(diào)整數(shù)組的前 N 個(gè)元素為最大堆；
重復(fù)步驟 2 直到未排序的長(zhǎng)度為 0.

實(shí)現(xiàn)代碼

package com.zhiyiyo.collection.sort;

import java.util.Arrays;

public class HeapSort extends BaseSort {
    @Override
    public void sort(Comparable[] array) {
        int N = array.length;

        // 創(chuàng)建最大堆
        for (int i = N / 2; i >= 0; i--) {
            sink(array, i, N);
        }

        // 就地排序
        while (N > 0) {
            // 將最大的元素移動(dòng)到數(shù)組的尾部，同時(shí)將未排序的長(zhǎng)度-1
            swap(array, 0, --N);
            // 調(diào)整最大堆
            sink(array, 0, N);
        }
    }

    /**
     * 下沉元素
     *
     * @param array 數(shù)組
     * @param k     下沉的元素索引
     */
    private void sink(Comparable[] array, int k, int N) {
        while (2 * k + 1 < N) {
            int j = 2 * k + 1;
            if (j < N - 1 && less(array[j], array[j + 1])) j++;
            if (!less(array[k], array[j])) break;
            swap(array, k, j);
            k = j;
        }
    }
}

抽象類(lèi) BaseSort 的代碼為：

package com.zhiyiyo.collection.sort;

/**
 * 數(shù)組排序抽象類(lèi)
 */
public abstract class BaseSort {
    public abstract void sort(Comparable[] array);

    /**
     * 交換數(shù)組元素
     *
     * @param array 數(shù)組
     * @param a     數(shù)組下標(biāo) a
     * @param b     數(shù)組下標(biāo) b
     */
    protected static void swap(Comparable[] array, int a, int b) {
        Comparable tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    protected static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

}

測(cè)試代碼

package com.zhiyiyo.collection.sort;

import org.junit.Test;

import java.util.Arrays;


public class HeapSortTest {

    @Test
    public void sort() {
        Integer[] array = {5, 10, 9, 6, 8, 7, 2, 1, 4, 3};
        new HeapSort().sort(array);
        System.out.println(Arrays.toString(array));
    }
}

最終排序結(jié)果為 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，以上~

到此這篇關(guān)于詳解如何在Java中實(shí)現(xiàn)堆排序算法的文章就介紹到這了,更多相關(guān)Java堆排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: