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("未排序数组: " + Arrays.toString(arr)); quickSort(arr, 0, arr.length-1); System.out.println("已排序数组: " + Arrays.toString(arr)); } public static int partition(int[] arr, int start, int end){ // 将最后一个元素设置为枢轴 int pivot = arr[end]; // 创建指向下一个较大元素的指针 int secondPointer = start-1; // 将小于枢轴的元素移动到枢轴左侧 for (int i = start; i < end; i++){ if (arr[i] < pivot){ secondPointer++; // 交换元素 int temp = arr[secondPointer]; arr[secondPointer] = arr[i]; arr[i] = temp; } } // 将枢轴与第二个指针交换 int temp = arr[secondPointer+1]; arr[secondPointer+1] = arr[end]; arr[end] = temp; // 返回分区索引 return secondPointer+1; } public static void quickSort(int[] arr, int start, int end){ if (start < end){ // 找到分区索引 int partitionIndex = partition(arr, start, end); // 递归调用快速排序 quickSort(arr, start, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } } }
Tafsiran kod
KaedahquickSort
: Mula-mula panggil kaedah partition
untuk membahagi tatasusunan kepada dua subtatasusunan, dan kemudian panggil quickSort
secara 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(n²)): 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!

Artikel ini membincangkan pelaksanaan caching pelbagai peringkat di Java menggunakan kafein dan cache jambu untuk meningkatkan prestasi aplikasi. Ia meliputi persediaan, integrasi, dan faedah prestasi, bersama -sama dengan Pengurusan Dasar Konfigurasi dan Pengusiran PRA Terbaik

Kelas kelas Java melibatkan pemuatan, menghubungkan, dan memulakan kelas menggunakan sistem hierarki dengan bootstrap, lanjutan, dan pemuat kelas aplikasi. Model delegasi induk memastikan kelas teras dimuatkan dahulu, yang mempengaruhi LOA kelas tersuai

Artikel ini meneroka mengintegrasikan pengaturcaraan berfungsi ke dalam Java menggunakan ekspresi Lambda, API Streams, rujukan kaedah, dan pilihan. Ia menyoroti faedah seperti kebolehbacaan dan kebolehkerjaan kod yang lebih baik melalui kesimpulan dan kebolehubahan

Artikel ini membincangkan menggunakan JPA untuk pemetaan objek-relasi dengan ciri-ciri canggih seperti caching dan pemuatan malas. Ia meliputi persediaan, pemetaan entiti, dan amalan terbaik untuk mengoptimumkan prestasi sambil menonjolkan potensi perangkap. [159 aksara]

Artikel ini membincangkan menggunakan Maven dan Gradle untuk Pengurusan Projek Java, membina automasi, dan resolusi pergantungan, membandingkan pendekatan dan strategi pengoptimuman mereka.

Artikel ini menerangkan NIO API Java untuk I/O yang tidak menyekat, menggunakan pemilih dan saluran untuk mengendalikan pelbagai sambungan dengan cekap dengan satu benang. Ia memperincikan proses, faedah (skalabilitas, prestasi), dan potensi perangkap (kerumitan,

Artikel ini membincangkan membuat dan menggunakan perpustakaan Java tersuai (fail balang) dengan pengurusan versi dan pergantungan yang betul, menggunakan alat seperti Maven dan Gradle.

Artikel ini memperincikan API soket Java untuk komunikasi rangkaian, yang meliputi persediaan pelanggan-pelayan, pengendalian data, dan pertimbangan penting seperti pengurusan sumber, pengendalian ralat, dan keselamatan. Ia juga meneroka teknik pengoptimuman prestasi, i


Alat AI Hot

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool
Gambar buka pakaian secara percuma

Clothoff.io
Penyingkiran pakaian AI

AI Hentai Generator
Menjana ai hentai secara percuma.

Artikel Panas

Alat panas

Muat turun versi mac editor Atom
Editor sumber terbuka yang paling popular

Dreamweaver Mac版
Alat pembangunan web visual

Pelayar Peperiksaan Selamat
Pelayar Peperiksaan Selamat ialah persekitaran pelayar selamat untuk mengambil peperiksaan dalam talian dengan selamat. Perisian ini menukar mana-mana komputer menjadi stesen kerja yang selamat. Ia mengawal akses kepada mana-mana utiliti dan menghalang pelajar daripada menggunakan sumber yang tidak dibenarkan.

DVWA
Damn Vulnerable Web App (DVWA) ialah aplikasi web PHP/MySQL yang sangat terdedah. Matlamat utamanya adalah untuk menjadi bantuan bagi profesional keselamatan untuk menguji kemahiran dan alatan mereka dalam persekitaran undang-undang, untuk membantu pembangun web lebih memahami proses mengamankan aplikasi web, dan untuk membantu guru/pelajar mengajar/belajar dalam persekitaran bilik darjah Aplikasi web keselamatan. Matlamat DVWA adalah untuk mempraktikkan beberapa kelemahan web yang paling biasa melalui antara muka yang mudah dan mudah, dengan pelbagai tahap kesukaran. Sila ambil perhatian bahawa perisian ini

mPDF
mPDF ialah perpustakaan PHP yang boleh menjana fail PDF daripada HTML yang dikodkan UTF-8. Pengarang asal, Ian Back, menulis mPDF untuk mengeluarkan fail PDF "dengan cepat" dari tapak webnya dan mengendalikan bahasa yang berbeza. Ia lebih perlahan dan menghasilkan fail yang lebih besar apabila menggunakan fon Unicode daripada skrip asal seperti HTML2FPDF, tetapi menyokong gaya CSS dsb. dan mempunyai banyak peningkatan. Menyokong hampir semua bahasa, termasuk RTL (Arab dan Ibrani) dan CJK (Cina, Jepun dan Korea). Menyokong elemen peringkat blok bersarang (seperti P, DIV),