Penjelasan terperinci algoritma QuickSort: alat pengisihan yang cekap

QuickSort ialah algoritma pengisihan yang cekap berdasarkan strategi bahagi-dan-takluk. Kaedah divide-and-conquer menguraikan masalah kepada sub-masalah yang lebih kecil, menyelesaikan sub-masalah ini secara berasingan, dan kemudian menggabungkan penyelesaian sub-masalah untuk mendapatkan penyelesaian akhir. Dalam isihan pantas, tatasusunan dibahagikan dengan memilih elemen partition, yang menentukan titik pecahan tatasusunan. Sebelum pembahagian, kedudukan elemen pembahagian disusun semula supaya berada di hadapan elemen yang lebih besar daripadanya dan selepas elemen yang lebih kecil daripadanya. Subarray kiri dan kanan akan dibahagikan secara rekursif dengan cara ini sehingga setiap subarray hanya mengandungi satu elemen, di mana tatasusunan diisih.

Seberapa pantas isihan berfungsi

Mari kita mengisih tatasusunan berikut dalam tertib menaik sebagai contoh:

Langkah 1: Pilih elemen pangsi

Kami memilih elemen terakhir sebagai pangsi:

Langkah 2: Susun semula elemen pangsi

Kami meletakkan elemen pangsi sebelum elemen yang lebih besar daripadanya dan selepas elemen yang lebih kecil daripadanya. Untuk melakukan ini, kami akan lelaran melalui tatasusunan dan membandingkan pangsi kepada setiap elemen sebelum itu. Jika elemen yang lebih besar daripada pangsi ditemui, kami mencipta penuding kedua untuknya:

Jika elemen yang lebih kecil daripada pangsi ditemui, kami menukarnya dengan penuding kedua:

Ulang proses ini, tetapkan elemen seterusnya yang lebih besar daripada pangsi ke penuding kedua, tukar jika elemen yang lebih kecil daripada pangsi ditemui:

Teruskan proses ini sehingga anda sampai ke penghujung tatasusunan:

Selepas melengkapkan perbandingan elemen, elemen yang lebih kecil daripada pangsi telah dialihkan ke kanan, kemudian kita menukar pangsi dengan penuding kedua:

Langkah 3: Bahagikan tatasusunan

Bahagikan tatasusunan mengikut indeks partition. Jika kita mewakili tatasusunan sebagai arr[start..end], maka dengan membahagikan tatasusunan dengan partition, kita boleh mendapatkan subarray kiri arr[start..partitionIndex-1] dan subarray kanan arr[partitionIndex 1..end].

Teruskan membahagikan subarray dengan cara ini sehingga setiap subarray mengandungi hanya satu elemen:

Pada ketika ini, tatasusunan diisih.

Pelaksanaan kod isihan pantas

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序數(shù)組: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 將最后一個(gè)元素設(shè)置為樞軸
        int pivot = arr[end];
        // 創(chuàng)建指向下一個(gè)較大元素的指針
        int secondPointer = start-1;

        // 將小于樞軸的元素移動(dòng)到樞軸左側(cè)
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交換元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 將樞軸與第二個(gè)指針交換
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分區(qū)索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分區(qū)索引
            int partitionIndex = partition(arr, start, end);
            // 遞歸調(diào)用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

Tafsiran kod

quickSort: Mula-mula panggil kaedah partition untuk membahagi tatasusunan kepada dua subtatasusunan, dan kemudian panggil quickSortsecara rekursif untuk mengisih subtatasusunan kiri dan kanan. Proses ini berterusan sehingga semua subarray mengandungi tepat satu elemen, di mana tatasusunan diisih.

partition Kaedah: Bertanggungjawab untuk membahagikan tatasusunan kepada dua sub-tatasusunan. Ia mula-mula menetapkan pangsi dan penuding kepada elemen yang lebih besar seterusnya, kemudian melelang melalui tatasusunan, menggerakkan elemen yang lebih kecil daripada pangsi ke kiri. Selepas itu ia menukar pangsi dengan penuding kedua dan mengembalikan kedudukan partition.

Jalankan kod di atas, konsol akan mengeluarkan yang berikut:

Tatasusunan tidak diisih: [8, 6, 2, 3, 9, 4] Tatasusunan diisih: [2, 3, 4, 6, 8, 9]

Kerumitan masa

Kes terbaik (O(n log n)): Kes terbaik berlaku apabila pangsi membahagi tatasusunan kepada dua bahagian yang hampir sama setiap kali.

Kes purata (O(n log n)): Dalam kes purata, pangsi membahagi tatasusunan kepada dua bahagian yang tidak sama, tetapi kedalaman rekursi dan bilangan perbandingan masih berkadar dengan n log n.

Kes terburuk (O(n2)): Kes terburuk berlaku apabila pangsi sentiasa membahagi tatasusunan kepada bahagian yang sangat tidak sama (cth. satu bahagian hanya mempunyai satu elemen dan satu lagi mempunyai elemen n-1) . Ini boleh berlaku, sebagai contoh, apabila menyusun tatasusunan dalam susunan terbalik, dan pangsi dipilih dengan buruk.

Kerumitan ruang (O(log n)): Isih pantas biasanya dilaksanakan di tempat dan tidak memerlukan tatasusunan tambahan.

Atas ialah kandungan terperinci Memahami Algoritma Isih Pantas (dengan Contoh dalam Java). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!