Contoh paparan: Pelaksanaan Java algoritma isihan gabungan dan penilaian prestasi

Contoh demonstrasi: Menggunakan Java untuk melaksanakan algoritma isihan gabungan dan melaksanakan ujian prestasi

1. Pengenalan
Merge Sort ialah algoritma pengisihan yang cekap yang digunakan secara meluas dalam pembangunan sebenar. Ia menggunakan idea Divide and Conquer untuk menguraikan masalah kepada beberapa sub-masalah yang lebih kecil, dan kemudian menggabungkan penyelesaian sub-masalah tersebut. Artikel ini akan melaksanakan algoritma isihan gabungan melalui kod Java dan menguji prestasinya.

2. Prinsip Algoritma Isih Gabungan
Idea teras isihan gabungan ialah membahagi dan menakluk. Langkah-langkah khusus adalah seperti berikut:

1. Bahagikan tatasusunan untuk diisih kepada dua sub-tatasusunan dari kedudukan tengah.
2. Isih dua sub-tatasusunan ini secara rekursif masing-masing.
3. Gabungkan sub-tatasusunan yang diisih untuk mendapatkan tatasusunan tertib terakhir.

3. Pelaksanaan kod Java
Berikut ialah contoh kod menggunakan bahasa Java untuk melaksanakan algoritma isihan gabungan:

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
}

4. Ujian prestasi
Untuk melaksanakan ujian prestasi pada algoritma isihan gabungan, kami menjana satu set tatasusunan rawak untuk pengisihan dan rekod Masa yang diperlukan untuk pengisihan.

import java.util.Arrays;
import java.util.Random;

public class PerformanceTest {
    public static void main(String[] args) {
        int[] arr = generateRandomArray(1000000);
        System.out.println("排序前：" + Arrays.toString(arr));
        long startTime = System.currentTimeMillis();
        MergeSort.mergeSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("排序后：" + Arrays.toString(arr));
        System.out.println("排序耗时：" + (endTime - startTime) + "毫秒");
    }

    private static int[] generateRandomArray(int length) {
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            arr[i] = random.nextInt(length);
        }
        return arr;
    }
}

Dalam kod di atas, mula-mula gunakan kaedah generateRandomArray方法生成了一组长度为1000000的随机整数数组，然后使用MergeSort.mergeSort untuk mengisih tatasusunan dan merekodkan masa yang diperlukan untuk mengisih. Akhirnya, tatasusunan yang diisih dan masa pengisihan adalah output.

5. Ringkasan
Melalui contoh demonstrasi di atas, kami melaksanakan algoritma isihan gabungan melalui kod Java dan menguji prestasinya. Algoritma pengisihan gabungan ialah algoritma pengisihan yang cekap yang mempunyai prestasi yang baik apabila berhadapan dengan pengisihan data berskala besar. Melalui idea bahagi dan takluk, merge sort boleh mengurai dan menyelesaikan masalah dengan berkesan, dengan itu memperoleh penyelesaian yang teratur.

Atas ialah kandungan terperinci Contoh paparan: Pelaksanaan Java algoritma isihan gabungan dan penilaian prestasi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!