Perbincangan mendalam tentang prinsip dan langkah pelaksanaan algoritma isihan pantas Java

Penjelasan terperinci tentang prinsip dan pelaksanaan Java Quick Sort

Quick Sort ialah algoritma pengisihan yang biasa digunakan Pelaksanaannya adalah mudah dan cekap, dan ia merupakan salah satu algoritma rekursif klasik. Artikel ini akan memperkenalkan prinsip dan pelaksanaan isihan pantas secara terperinci, dan menyediakan contoh kod Java tertentu. . Idea teras adalah untuk meletakkan elemen pada kedudukan terakhirnya melalui satu jenis, walaupun ia mungkin dipindahkan beberapa kali semasa proses isihan.

1. Langkah umum pengisihan pantas adalah seperti berikut:
   (1) Pilih elemen penanda aras dan bahagikan urutan kepada dua bahagian, supaya elemen di sebelah kiri adalah kurang daripada atau sama dengan penanda aras, dan elemen pada kanan kedua-duanya lebih besar daripada atau sama dengan penanda aras
(2) Gandingkan elemen kiri dan kanan secara rekursif Isih kedua-dua bahagian secara rekursif.

Pelaksanaan
Berikut ialah contoh kod pelaksanaan isihan pantas dalam 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);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        
        swap(arr, i + 1, high);
        
        return i + 1;
    }

    private 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 = {9, 2, 4, 7, 1, 5, 3, 8, 6};
        
        System.out.println("Before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        
        quickSort(arr, 0, arr.length - 1);
        
        System.out.println("
After sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

2. Dalam kod di atas, kami mentakrifkan kaedah statik quickSort, yang menerima tatasusunan integer, bermula dan indeks akhir sebagai hujah. Dalam kaedah quickSort, tentukan dahulu sama ada indeks permulaan lebih kecil daripada indeks penamat Jika syarat dipenuhi, elemen asas dipilih dan dibahagikan melalui kaedah partition. Dalam kaedah partition, kami menggunakan elemen terakhir sebagai elemen asas, merentasi elemen antara indeks permulaan dan indeks akhir, dan menukar elemen yang lebih kecil daripada elemen asas dengan elemen yang lebih besar daripada elemen asas. Akhir sekali, tukar elemen asas ke kedudukan terakhirnya dan kembalikan kedudukan itu.
   
Dalam kaedah utama, kami mencipta tatasusunan integer dan memulakannya. Kemudian, panggil kaedah quickSort untuk mengisih tatasusunan dan mengeluarkan keputusan sebelum dan selepas mengisih.

quickSort，它接受一个整型数组、起始和结束索引作为参数。quickSort方法中，首先判断起始索引是否小于结束索引，如果满足条件，则选取基准元素，并通过partition方法进行分区操作。partition方法中，我们以最后一个元素作为基准元素，遍历起始索引到结束索引之间的元素，将小于基准元素的元素与大于基准元素的元素进行交换。最后，交换基准元素到最终位置，返回该位置。

在main方法中，我们创建一个整型数组并初始化。然后，调用quickSortAnalisis

Purata kerumitan masa isihan cepat ialah O(nlogn), dan kerumitan masa terburuk ialah O(n^2). Ia adalah algoritma pengisihan di tempat, iaitu, ia boleh diisih pada tatasusunan asal.

3. 
   Memandangkan isihan pantas dilaksanakan secara rekursif, limpahan tindanan mungkin berlaku dalam kes yang paling teruk. Untuk menyelesaikan masalah ini, anda boleh menggunakan kaedah bukan rekursif atau mengoptimumkan panggilan rekursif.

Isih cepat ialah algoritma pengisihan yang tidak stabil, iaitu tertib relatif bagi elemen yang sama boleh diubah.

Ringkasan:

Isih cepat ialah algoritma pengisihan klasik dengan prinsip yang mudah dan cekap. Artikel ini membantu pembaca memahami dan menguasai idea serta kaedah pelaksanaan algoritma isihan pantas dengan menganalisis prinsip isihan pantas secara terperinci dan menyediakan kod pelaksanaan Java tertentu. Melalui amalan dan pengoptimuman, kami boleh menggunakan algoritma isihan pantas dengan lebih baik untuk menyelesaikan masalah praktikal.

Atas ialah kandungan terperinci Perbincangan mendalam tentang prinsip dan langkah pelaksanaan algoritma isihan pantas Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!