Pengoptimuman dan prinsip pelaksanaan: Isih pantas dalam Java

Prinsip pelaksanaan dan pengoptimuman fungsi isihan pantas Java

Isih cepat ialah algoritma pengisihan yang cekap Idea pelaksanaannya adalah untuk membahagikan masalah besar kepada berbilang masalah kecil melalui kaedah bahagi dan takluk, dan menyelesaikan sub-masalah melalui. rekursi , dan akhirnya mendapatkan penyelesaian keseluruhan. Dalam isihan pantas, kita perlu memilih elemen penanda aras dan membahagikan tatasusunan kepada dua bahagian, satu bahagian lebih kecil daripada elemen penanda aras dan satu lagi lebih besar daripada elemen penanda aras. Kedua-dua bahagian itu kemudian diisih dengan pantas sekali lagi sehingga terdapat hanya satu elemen bagi setiap submasalah. Akhir sekali, penyelesaian kepada semua submasalah digabungkan untuk mendapatkan urutan susunan tatasusunan.

Proses pelaksanaan khusus adalah seperti berikut:

1. Pilih elemen penanda aras. Terdapat banyak cara untuk memilih elemen asas Kaedah biasa ialah memilih elemen pertama tatasusunan.

2. Bahagikan array. Bahagikan tatasusunan kepada dua bahagian dengan membandingkan saiz elemen dalam tatasusunan dengan elemen asas. Satu bahagian mengandungi unsur yang lebih kecil daripada unsur asas, dan satu bahagian mengandungi unsur yang lebih besar daripada unsur asas.

3. Isih dua subarray terbahagi secara rekursif sehingga subarray hanya mengandungi satu elemen.

4. Gabungkan subarray yang diisih untuk mendapatkan tatasusunan yang diisih terakhir.

Berikut ialah contoh kod Java:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(arr, low, high); // 获取划分点
            quickSort(arr, low, partitionIndex - 1); // 对左侧子数组进行快速排序
            quickSort(arr, partitionIndex + 1, high); // 对右侧子数组进行快速排序
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 选取第一个元素作为基准元素
        int i = low + 1; // 左指针
        int j = high; // 右指针

        while (i <= j) {
            while (i <= j && arr[i] < pivot) {
                i++;
            }
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }

        swap(arr, low, j); // 将基准元素放到正确的位置

        return j;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 6, 1, 3, 9, 4, 8, 7};
        quickSort(arr, 0, arr.length - 1);
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Melalui kod contoh di atas, kita dapat melihat dengan jelas prinsip pelaksanaan fungsi isihan pantas. Dalam contoh ini, kami menggunakan kaedah pemilihan elemen asas untuk memilih elemen pertama tatasusunan. Fungsi isihan pantas menerima tiga parameter: tatasusunan, sempadan kiri dan sempadan kanan. Dengan memanggil fungsi quickSort secara rekursif, tatasusunan dibahagikan dan diisih, dan hasil yang diisih akhirnya dikeluarkan.

Walaupun algoritma isihan pantas sudah sangat cekap, kami juga boleh melakukan beberapa pengoptimuman padanya untuk meningkatkan lagi prestasi:

1. Pilih elemen penanda aras secara rawak: Apabila memilih elemen penanda aras dalam langkah pertama, elemen pertama tidak tetap selected , sebaliknya memilih elemen secara rawak. Melakukannya mengurangkan kebarangkalian senario terburuk dan meningkatkan prestasi purata algoritma.
2. Kaedah tiga nombor: Apabila memilih elemen rujukan, anda bukan sahaja boleh memilih secara rawak, tetapi juga menggunakan kaedah tiga nombor. Iaitu, pilih elemen dengan nilai tengah dari kedudukan kiri, tengah dan kanan sebagai elemen asas. Ini mengurangkan lagi kebarangkalian senario terburuk berlaku.
3. Tukar kepada isihan sisipan: Apabila saiz subarray cukup kecil, anda boleh beralih kepada algoritma isihan sisipan. Kerana isihan sisipan adalah lebih pantas untuk pengisihan tatasusunan berskala kecil dan lebih mudah untuk dilaksanakan.

Di atas adalah pengenalan kepada prinsip pelaksanaan dan pengoptimuman fungsi isihan pantas Java. Dengan memahami dan mengoptimumkan algoritma pengisihan pantas, kecekapan pengisihan program boleh dipertingkatkan, menjadikan proses pengisihan lebih cepat dan lebih cekap.

Atas ialah kandungan terperinci Pengoptimuman dan prinsip pelaksanaan: Isih pantas dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!