Rumah  >  Artikel  >  Java  >  Terokai prinsip dan amalan jenis cepat Java

Terokai prinsip dan amalan jenis cepat Java

王林
王林asal
2024-02-19 19:06:061095semak imbas

Terokai prinsip dan amalan jenis cepat Java

Pemahaman mendalam tentang prinsip dan aplikasi Java Quick Sort

Quick Sort (Quick Sort) ialah algoritma pengisihan yang biasa digunakan Kecekapan dan kelebihannya menjadikannya digunakan secara meluas dalam pelbagai bahasa pengaturcaraan, termasuk Java. Dalam artikel ini, kami akan memberikan pemahaman yang mendalam tentang prinsip dan aplikasi algoritma isihan pantas Java dan memberikan contoh kod khusus.

1. Prinsip
Idea asas algoritma isihan cepat adalah untuk terus membahagikan masalah besar kepada masalah kecil melalui kaedah bahagi dan takluk, kemudian mengisih masalah kecil, dan akhirnya menggabungkan hasil yang disusun ke dalam urutan yang teratur.

Secara khusus, langkah pelaksanaan algoritma isihan pantas adalah seperti berikut:

  1. Pilih elemen pangsi (pivot), dengan anggapan ia adalah elemen pertama dalam tatasusunan.
  2. Pisah tatasusunan kepada dua sub-tatasusunan, supaya unsur-unsur dalam sub-tatasusunan pertama adalah kurang daripada atau sama dengan elemen penanda aras, dan unsur-unsur dalam sub-tatasusunan kedua adalah lebih besar daripada elemen penanda aras. Proses ini dipanggil partition.
  3. Gunakan langkah-langkah di atas secara rekursif pada dua sub-array masing-masing sehingga setiap sub-array hanya mengandungi satu elemen, iaitu, syarat penamatan rekursi dicapai.
  4. Gabungkan hasil sub-tatasusunan untuk mendapatkan keseluruhan tatasusunan yang diisih.

2. Aplikasi
Algoritma pengisihan pantas digunakan secara meluas dalam aplikasi praktikal, dan kelajuan pengisihannya yang cekap menjadikannya algoritma pengisihan yang biasa digunakan. Di bawah ini kami menunjukkan aplikasi isihan pantas melalui contoh kod sebenar.

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;

        quickSort(arr, 0, n-1);

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

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);

            // 对划分后的子数组进行递归排序
            quickSort(arr, low, pi-1);
            quickSort(arr, pi+1, high);
        }
    }

    public 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++;

                // 交换arr[i]和arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 交换arr[i+1]和arr[high]
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }
}

Kod di atas mengisih tatasusunan melalui algoritma isihan pantas dan mencetak hasil yang diisih. Dalam contoh ini, kami memilih elemen terakhir dalam tatasusunan sebagai elemen asas, membahagikan subarray dengan menggerakkan elemen yang lebih kecil ke kiri elemen asas, elemen yang lebih besar ke kanan dan menggabungkan hasil subarray .

Melalui kod dan pengenalan di atas, kita boleh mempunyai pemahaman yang lebih mendalam tentang prinsip dan aplikasi algoritma isihan pantas Java. Saya harap artikel ini akan membantu pembaca dan memberi pemahaman yang lebih menyeluruh tentang algoritma isihan pantas kepada semua orang.

Atas ialah kandungan terperinci Terokai prinsip dan amalan jenis cepat Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn