Laksanakan dan optimumkan algoritma isihan gabungan Java

Pelaksanaan dan pengoptimuman algoritma isihan gabungan Java

Isih gabung ialah algoritma pengisihan berdasarkan perbandingan Idea utamanya ialah membahagikan urutan untuk diisih kepada beberapa urutan, mengisih setiap urutan, dan akhirnya akan terdapat urutan Tertib. digabungkan ke dalam urutan tertib keseluruhan.

1. Pelaksanaan algoritma isihan cantuman:
   Pelaksanaan algoritma isihan cantum boleh dibahagikan kepada dua langkah: bahagi dan takluk dan cantum.

(1) Bahagi dan takluk:
Pertama, bahagikan urutan untuk diisih kepada dua bahagian sehingga setiap urutan hanya mempunyai satu elemen. Kemudian, urutan ini digabungkan menjadi urutan tertib.

Berikut ialah contoh kod untuk pelaksanaan rekursif algoritma isihan cantuman:

public class MergeSort {
    // 归并排序
    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 递归地对左右两边进行归并排序
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            // 合并两个有序子序列
            merge(array, left, mid, right);
        }
    }

    // 合并两个有序子序列
    public void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left; // 左序列指针
        int j = mid + 1; // 右序列指针
        int k = 0; // 临时数组指针

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < temp.length; l++) {
            array[left + l] = temp[l];
        }
    }
}

(2) Cantum:
Fungsi fungsi cantum adalah untuk menggabungkan dua urutan tertib ke dalam urutan tertib. Dalam pelaksanaan khusus, kita perlu mencipta tatasusunan sementara untuk menyimpan hasil gabungan. Apabila merentasi urutan, kami membandingkan elemen dalam urutan, meletakkan elemen yang lebih kecil ke dalam tatasusunan sementara, dan menggerakkan penunjuk yang sepadan. Akhir sekali, unsur-unsur dalam tatasusunan sementara disalin kembali ke tatasusunan asal. . Untuk mengurangkan overhed ini, kecekapan algoritma isihan cantuman boleh dipertingkatkan melalui kaedah pengoptimuman berikut:

2. (1) Gunakan isihan sisipan untuk urutan berskala kecil:
   Apabila saiz jujukan agak kecil, sisipan sort adalah lebih cekap. Oleh itu, semasa proses rekursif isihan cantum, apabila saiz jujukan adalah kurang daripada ambang tertentu, jenis sisipan boleh digunakan untuk menggantikan proses rekursif.

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        if (right - left <= THRESHOLD) {
            // 子序列的规模小于阈值，采用插入排序
            insertionSort(array, left, right);
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
}

(2) Optimumkan proses penggabungan:

Semasa proses penggabungan, anda boleh terlebih dahulu menyimpan kedua-dua urutan dalam dua tatasusunan sementara, dan kemudian menggabungkan dua tatasusunan sementara ke dalam tatasusunan asal. Dengan cara ini anda mengelakkan berulang kali membuat tatasusunan sementara semasa proses gabungan. Pada masa yang sama, memandangkan saiz tatasusunan sementara ditetapkan, ia boleh ditakrifkan sebagai pembolehubah ahli kelas untuk mengelakkan penciptaan berulang semasa proses rekursif.

public class MergeSort {
    private int[] temp;

    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            if (right - left <= THRESHOLD) {
                insertionSort(array, left, right);
            } else {
                int mid = (left + right) / 2;
                mergeSort(array, left, mid);
                mergeSort(array, mid + 1, right);
                merge(array, left, mid, right);
            }
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < k; l++) {
            array[left + l] = temp[l];
        }
    }
}

Ringkasnya, perkara di atas ialah pelaksanaan algoritma isihan gabungan Java dan kaedah pengoptimumannya. Dengan mengoptimumkan proses penggabungan dan menggunakan isihan sisipan untuk urutan berskala kecil, kecekapan algoritma isihan cantuman boleh dipertingkatkan dan ruang atas boleh dikurangkan. Dalam aplikasi praktikal, memilih kaedah pengoptimuman yang sesuai dan membuat pilihan yang munasabah berdasarkan ciri-ciri urutan pengisihan boleh menjadikan algoritma lebih cekap.

Atas ialah kandungan terperinci Laksanakan dan optimumkan algoritma isihan gabungan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!