Petua pengisihan pantas Java dan langkah berjaga-jaga

Kuasai kemahiran dan langkah berjaga-jaga utama Java Quick Sort

Quick Sort ialah algoritma pengisihan yang biasa digunakan ialah membahagikan urutan untuk diisih kepada dua bahagian bebas dengan memilih elemen rujukan , semua elemen satu bahagian adalah lebih kecil daripada elemen rujukan, dan semua elemen bahagian yang lain adalah lebih besar daripada elemen rujukan, dan kemudian kedua-dua bahagian disusun secara rekursif, dan akhirnya urutan tertib diperoleh.

Walaupun kerumitan masa isihan pantas ialah O(nlogn) dalam kes purata, ia akan merosot kepada O(n^2) dalam kes terburuk, jadi dalam penggunaan sebenar, kita perlu menguasai beberapa kemahiran dan langkah berjaga-jaga utama, untuk meningkatkan kecekapan isihan pantas.

1. Pilih elemen penanda aras yang sesuai:
   Kecekapan isihan pantas dipengaruhi oleh pilihan elemen penanda aras. Biasanya, kita boleh memilih elemen pertama bagi urutan untuk diisih sebagai elemen rujukan, tetapi jika urutan yang hendak diisih sudah hampir dengan pesanan, kaedah pemilihan ini boleh membawa kepada senario kes terburuk merosot kepada O(n^2). ). Untuk mengelakkan situasi ini, anda boleh memilih elemen rujukan secara rawak atau memilih elemen tengah dalam urutan untuk diisih sebagai elemen rujukan.
2. Bahagikan urutan:
   Semasa proses pembahagian jenis cepat, kita perlu membahagikan urutan untuk diisih kepada dua urutan. Anda boleh menggunakan penunjuk berganda, bermula dari kedua-dua hujung jujukan untuk diisih, dan teruskan menggerakkan penunjuk ke arah tengah sehingga bertemu, sambil menukar kedudukan elemen yang lebih kecil daripada elemen asas dan elemen yang lebih besar daripada elemen asas. Akhir sekali, masukkan elemen asas ke dalam kedudukan mesyuarat untuk melengkapkan pembahagian.
3. Panggilan rekursif:
   Selepas pembahagian selesai, kami mendapat dua urutan baharu. Pada masa ini, adalah perlu untuk memanggil isihan pantas secara rekursif pada dua urutan untuk mendapatkan urutan tertib terakhir. Keadaan akhir panggilan rekursif ialah panjang urutan kurang daripada atau sama dengan 1.

Berikut ialah contoh kod untuk menunjukkan cara melaksanakan isihan pantas:

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }

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

Dalam kod di atas, kami mentakrifkan kaedah quickSort untuk melengkapkan isihan pantas. Di dalam kaedah, kami mula-mula memilih elemen pertama urutan untuk diisih sebagai elemen rujukan, dan membahagikannya dengan memanggil kaedah partition. Kaedah partition menggunakan penunjuk berganda, bermula dari kedua-dua hujung jujukan, menggerakkan penunjuk ke arah tengah sehingga bertemu dan menukar kedudukan elemen yang lebih kecil daripada elemen asas dan elemen yang lebih besar daripada elemen asas . Akhir sekali, masukkan elemen asas di tempat ia bertemu. quickSort方法用于完成快速排序。在方法内部，我们首先选择待排序序列的第一个元素作为基准元素，并通过调用partition方法进行划分。partition方法使用双指针的方式，从序列的两端开始，不断向中间移动指针，直到相遇，并交换比基准元素小的元素和比基准元素大的元素的位置。最后，将基准元素插入到相遇的位置。

在main方法中，我们测试了该快速排序算法。输出结果为1 2 3 4 5

Dalam kaedah utama, kami menguji algoritma isihan pantas. Hasil keluaran ialah 1 2 3 4 5, menunjukkan bahawa pengisihan adalah betul.

Dengan menguasai kemahiran dan langkah berjaga-jaga utama di atas, kami boleh lebih memahami dan menggunakan algoritma isihan pantas, seterusnya meningkatkan kecekapan dan ketepatan pengisihan. Pada masa yang sama, dalam pembangunan sebenar, kami boleh mengoptimumkan lagi algoritma, seperti menggunakan kaedah tiga nombor untuk memilih elemen penanda aras untuk mengelakkan senario kes terburuk. Pendek kata, isihan pantas ialah algoritma pengisihan yang sangat praktikal dan cekap yang patut dikuasai dan dikaji secara mendalam. 🎜

Atas ialah kandungan terperinci Petua pengisihan pantas Java dan langkah berjaga-jaga. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!