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!

JVM berfungsi dengan menukar kod Java ke dalam kod mesin dan menguruskan sumber. 1) Pemuatan Kelas: Muatkan fail kelas. Ke dalam memori. 2) Kawasan data runtime: Menguruskan kawasan memori. 3) Enjin Pelaksanaan: Mentafsirkan atau menyusun bytecode pelaksanaan. 4) Antara muka kaedah tempatan: Berinteraksi dengan sistem operasi melalui JNI.

JVM membolehkan Java melintasi platform. 1) Beban JVM, mengesahkan dan melaksanakan bytecode. 2) Kerja JVM termasuk pemuatan kelas, pengesahan bytecode, pelaksanaan tafsiran dan pengurusan ingatan. 3) JVM menyokong ciri -ciri canggih seperti pemuatan dan refleksi kelas dinamik.

Aplikasi Java boleh dijalankan pada sistem pengendalian yang berbeza melalui langkah -langkah berikut: 1) Gunakan kelas fail atau laluan untuk memproses laluan fail; 2) menetapkan dan mendapatkan pembolehubah persekitaran melalui System.getenv (); 3) Gunakan Maven atau Gradle untuk menguruskan kebergantungan dan ujian. Keupayaan merentas platform Java bergantung pada lapisan abstraksi JVM, tetapi masih memerlukan pengendalian manual ciri-ciri khusus sistem operasi tertentu.

Java memerlukan konfigurasi dan penalaan khusus pada platform yang berbeza. 1) Laraskan parameter JVM, seperti -XMS dan -XMX untuk menetapkan saiz timbunan. 2) Pilih strategi pengumpulan sampah yang sesuai, seperti ParallelGC atau G1GC. 3) Konfigurasikan perpustakaan asli untuk menyesuaikan diri dengan platform yang berbeza. Langkah -langkah ini dapat membolehkan aplikasi Java melakukan yang terbaik dalam pelbagai persekitaran.

Osgi, apachecommonslang, jna, danjvmoptionsareeffectiveforhandlingplatform-specificchallengesinjava.1) osgimanagesdependencyandisolatescomponents.2) ApachecommonslangprovideSutilityfung

JVMmanagesgarbagecollectionacrossplatformseffectivelybyusingagenerationalapproachandadaptingtoOSandhardwaredifferences.ItemploysvariouscollectorslikeSerial,Parallel,CMS,andG1,eachsuitedfordifferentscenarios.Performancecanbetunedwithflagslike-XX:NewRa

Kod Java boleh dijalankan pada sistem pengendalian yang berbeza tanpa pengubahsuaian, kerana falsafah "Write Once, Run, Everywhere" Java dilaksanakan oleh Java Virtual Machine (JVM). Oleh kerana perantara antara bytecode Java yang disusun dan sistem operasi, JVM menerjemahkan bytecode ke dalam arahan mesin tertentu untuk memastikan program itu dapat dijalankan secara bebas di mana -mana platform dengan JVM dipasang.

Penyusunan dan pelaksanaan program Java mencapai kemerdekaan platform melalui Bytecode dan JVM. 1) Tulis kod sumber Java dan menyusunnya ke dalam bytecode. 2) Gunakan JVM untuk melaksanakan bytecode pada mana -mana platform untuk memastikan kod berjalan di seluruh platform.


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

Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Artikel Panas

Alat panas

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

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),

Dreamweaver CS6
Alat pembangunan web visual

Versi Mac WebStorm
Alat pembangunan JavaScript yang berguna

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.
