Bagaimana untuk melaksanakan algoritma isihan timbunan menggunakan java

Cara melaksanakan algoritma isihan timbunan dalam Java

Isihan timbunan ialah algoritma isihan berdasarkan struktur data timbunan, yang mengambil kesempatan daripada sifat timbunan untuk mengisih. Isih timbunan dibahagikan kepada dua langkah utama: membina timbunan dan isihan.

Membina timbunan:
Pertama, kita perlu membina timbunan akar yang besar atau timbunan akar yang kecil berdasarkan tatasusunan yang hendak diisih. Untuk jenis menaik, kita perlu membina timbunan akar yang besar;

Harta timbunan akar yang besar ialah: nilai nod lebih besar daripada atau sama dengan nilai nod anaknya.
Harta timbunan akar kecil ialah: nilai nod adalah kurang daripada atau sama dengan nilai nod anaknya.

Proses membina timbunan akar yang besar adalah seperti berikut:

public static void buildHeap(int[] array, int length) {
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
}

public static void heapify(int[] array, int length, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < length && array[left] > array[largest]) {
        largest = left;
    }

    if (right < length && array[right] > array[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = array[i];
        array[i] = array[largest];
        array[largest] = temp;
        heapify(array, length, largest);
    }
}

Isih:
Selepas membina timbunan akar yang besar, kita perlu menukar elemen atas timbunan dengan elemen terakhir tatasusunan, dan mengurangkan skop timbunan, dan kemudian lakukan operasi timbunan pada timbunan , ulangi proses ini sehingga timbunan kosong. Tatasusunan akhir dipesan.

public static void heapSort(int[] array) {
    int length = array.length;

    buildHeap(array, length);

    for (int i = length - 1; i >= 0; i--) {
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;

        heapify(array, i, 0);
    }
}

Contoh penggunaan:

public static void main(String[] args) {
    int[] array = {4, 10, 3, 5, 1};
    heapSort(array);

    System.out.println(Arrays.toString(array));
}

Hasil keluaran ialah: [1, 3, 4, 5, 10], iaitu hasil isihan menaik.

Kerumitan masa isihan timbunan ialah O(nlogn), dengan n ialah bilangan elemen untuk diisih. Isihan timbunan ialah algoritma pengisihan yang stabil sesuai untuk mengisih data berskala besar.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma isihan timbunan menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!