Algoritma isihan pantas dilaksanakan dalam Java dan penilaian kecekapannya

Pelaksanaan Java bagi isihan pantas dan analisis prestasinya

Isih Pantas (Quick Sort) ialah algoritma pengisihan yang sangat biasa digunakan dan cekap Ia adalah idea bahagi dan takluk (Divide and Conquer). Algoritma ini membahagikan tatasusunan kepada dua sub-tatasusunan, kemudian mengisih kedua-dua sub-tatasusunan masing-masing, dan akhirnya menukar keseluruhan tatasusunan kepada urutan tertib. Isih pantas menunjukkan prestasi cemerlang semasa memproses data berskala besar.

Isihan pantas dilaksanakan secara rekursif Idea asasnya adalah seperti berikut:

1. Pilih elemen pangsi (pivot) dan bahagikan tatasusunan kepada dua sub-tatasusunan yang lebih besar daripada elemen pangsi diletakkan di sebelah kanan , dan yang lebih kecil daripada elemen pivot diletakkan di sebelah kiri;
2. Isih dengan pantas subarray kiri dan kanan secara rekursif
3. Apabila panjang subarray ialah 1 atau 0, hentikan rekursi dan isihan selesai.

Berikut ialah contoh kod untuk melaksanakan isihan pantas menggunakan bahasa Java:

public class QuickSort {
    public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int pivotIndex = partition(arr, start, end); // 将数组分成两部分，并返回基准元素的索引
            quickSort(arr, start, pivotIndex - 1); // 对左子数组进行快速排序
            quickSort(arr, pivotIndex + 1, end); // 对右子数组进行快速排序
        }
    }

    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[start]; // 选择数组的第一个元素作为基准元素
        int left = start + 1;
        int right = end;
        while (left <= right) {
            // 从左边找到大于基准元素的值
            while (left <= right && arr[left] <= pivot) {
                left++;
            }
            // 从右边找到小于基准元素的值
            while (left <= right && arr[right] > pivot) {
                right--;
            }
            // 交换左右两个值
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 将基准元素放到正确的位置
        arr[start] = arr[right];
        arr[right] = pivot;
        return right;
    }

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

Di atas ialah pelaksanaan asas algoritma isihan pantas, menggunakan rekursi untuk membahagi tatasusunan dan isihan. Seterusnya kita menganalisis prestasinya.

Kerumitan masa isihan pantas ialah O(nlogn), dengan n ialah saiz tatasusunan yang hendak diisih. Prestasi pengisihan pantas terutamanya bergantung pada pemilihan elemen rujukan dan rasionaliti pembahagian.

Untuk pemilihan elemen asas, anda secara umumnya boleh memilih elemen pertama, elemen terakhir, elemen tengah, dsb. tatasusunan. Memilih elemen rujukan yang sesuai boleh mengurangkan bilangan bahagian dan meningkatkan prestasi isihan pantas.

Rasionaliti pembahagian juga merupakan kunci kepada prestasi menyusun pantas. Setiap kali pembahagian dilakukan, nilai yang lebih besar daripada elemen rujukan perlu diletakkan di sebelah kanan, dan nilai yang lebih kecil daripada elemen rujukan diletakkan di sebelah kiri Ini memastikan bahawa bahagian kiri kedudukan elemen rujukan mempunyai nilai lebih kecil daripadanya, dan sebelah kanan mempunyai nilai yang lebih besar daripadanya. Jika pembahagian tidak sekata, mengakibatkan perbezaan panjang yang besar di antara subarray kiri dan kanan hasil pembahagian, kecekapan isihan pantas mungkin dikurangkan.

Quicksort ialah algoritma pengisihan yang tidak stabil kerana susunan relatif unsur yang sama mungkin berubah semasa proses pertukaran elemen.

Ringkasnya, isihan pantas ialah algoritma pengisihan yang cekap Dengan memilih elemen rujukan dan membahagikan tatasusunan secara munasabah, anda boleh mencapai prestasi yang lebih baik. Walau bagaimanapun, apabila memproses data berskala besar, adalah perlu untuk memberi perhatian kepada rasional pemilihan dan pembahagian elemen penanda aras untuk meningkatkan kecekapan algoritma.

Atas ialah kandungan terperinci Algoritma isihan pantas dilaksanakan dalam Java dan penilaian kecekapannya. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!