Analisis langkah demi langkah terperinci untuk melaksanakan algoritma isihan pantas dalam Java

Analisis langkah demi langkah terperinci pelaksanaan Java bagi algoritma isihan pantas

Isih Pantas ialah algoritma pengisihan yang cekap yang menggunakan idea membahagi dan menakluk dengan membahagikan urutan untuk diisih ke dalam urutan yang lebih kecil, dan kemudian Susun urutan dan akhirnya gabungkan urutan untuk mendapatkan urutan tertib. Artikel ini akan memperkenalkan langkah-langkah algoritma isihan pantas secara terperinci dan memberikan contoh kod Java tertentu.

1. Langkah algoritma:

Langkah asas algoritma isihan pantas adalah seperti berikut:

1.1 Pilih elemen sebagai pangsi (pivot), yang boleh menjadi elemen pertama, elemen terakhir atau elemen yang dipilih secara rawak.

1.2 Bahagikan jujukan untuk diisih kepada dua jujukan: jujukan unsur yang kurang daripada atau sama dengan penanda aras dan jujukan unsur yang lebih besar daripada penanda aras.

1.3 Gunakan algoritma isihan pantas secara rekursif kepada dua urutan.

1.4 Gabungkan urutan untuk mendapatkan urutan tertib yang lengkap.

2. Contoh kod Java:

Berikut ialah contoh kod khusus menggunakan Java untuk melaksanakan algoritma isihan pantas:

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0 || low >= high) {
            return;
        }

        // 选择基准元素
        int pivotIndex = partition(arr, low, high);

        // 对基准元素左边的子序列递归排序
        quickSort(arr, low, pivotIndex - 1);

        // 对基准元素右边的子序列递归排序
        quickSort(arr, pivotIndex + 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 = {5, 2, 9, 1, 6, 3, 8, 4, 7};
        int n = arr.length;

        quickSort(arr, 0, n - 1);

        System.out.println("排序后的结果：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

3. Contoh penerangan:

Dalam kod di atas, kami mentakrifkan quickSort kaedah code> Digunakan untuk mengisih jujukan yang hendak diisih, kaedah <code>partition digunakan untuk membahagikan jujukan kepada dua jujukan. quickSort方法用于对待排序序列进行排序，partition方法用于将序列分割成两个子序列。

在quickSort方法中，首先判断序列是否需要排序，然后选择基准元素，并调用partition方法将序列分割。接着，对两个子序列递归应用quickSort方法，直到序列长度为1。

partition方法选择最后一个元素作为基准，并使用变量i记录小于等于基准的元素个数。通过遍历序列，如果元素小于等于基准，则将其与i

Dalam kaedah quickSort, mula-mula tentukan sama ada jujukan perlu diisih, kemudian pilih elemen asas dan panggil kaedah partition untuk membahagikan jujukan. Seterusnya, gunakan kaedah quickSort secara rekursif pada dua urutan sehingga panjang jujukan ialah 1.

Kaedah partition memilih elemen terakhir sebagai garis dasar dan menggunakan pembolehubah i untuk merekodkan bilangan elemen yang kurang daripada atau sama dengan garis dasar. Dengan merentasi jujukan, jika elemen kurang daripada atau sama dengan rujukan, ia ditukar dengan kedudukan yang ditunjuk oleh i, dan akhirnya elemen rujukan diletakkan pada kedudukan yang sesuai.

Akhir sekali, jalankan fungsi utama untuk mengeluarkan hasil yang disusun. 🎜🎜Kerumitan masa algoritma isihan pantas ialah O(nlogn) dan mempunyai kecekapan tinggi. Dengan memahami dan menggunakan langkah di atas dengan betul, algoritma isihan pantas boleh digunakan secara fleksibel dalam pengaturcaraan sebenar untuk mencapai keperluan pengisihan. 🎜

Atas ialah kandungan terperinci Analisis langkah demi langkah terperinci untuk melaksanakan algoritma isihan pantas dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!