Cuba Isih Pantas Ini

Dalam Bab 5, anda melihat kaedah pengelasan mudah yang dipanggil
pengasingan gelembung. Disebutkan pada masa itu bahawa terdapat
penilaian yang jauh lebih baik. Di sini, anda akan membangunkan versi salah satu yang terbaik: isihan pantas (Quicksort).
Klasifikasi pantas, dicipta dan dinamakan oleh C.A.R. Hoare, ialah algoritma klasifikasi tujuan am terbaik yang tersedia pada masa ini. Saya tidak dapat menunjukkannya dalam Bab 5 kerana pelaksanaan terbaik jenis cepat adalah berdasarkan rekursi. Versi yang akan kami bangunkan mengklasifikasikan tatasusunan aksara, tetapi logiknya boleh disesuaikan untuk mengklasifikasikan sebarang jenis objek.
Isih cepat adalah berdasarkan idea partition. Prosedur am melibatkan pemilihan nilai, dipanggil membandingkan, dan kemudian membahagikan tatasusunan kepada dua bahagian. Semua elemen yang lebih besar daripada atau sama dengan nilai partition dimasukkan pada satu sisi dan yang lebih kecil dimasukkan pada sisi yang lain. Proses ini diulang untuk setiap bahagian yang tinggal sehingga tatasusunan diisih. Sebagai contoh, memandangkan tatasusunan fedacb dan menggunakan nilai d sebagai perbandingan, pas pertama isihan pantas akan menyusun semula tatasusunan seperti yang ditunjukkan di bawah:

F e d a c b awal
Petikan 1 b c a d e f

Proses ini kemudiannya diulang untuk setiap bahagian – iaitu bca dan def. Seperti yang anda boleh lihat, proses ini pada dasarnya bersifat rekursif, dan sebenarnya, pelaksanaan terbersih jenis cepat ialah rekursif.
Anda boleh memilih nilai perbandingan dalam dua cara. Anda boleh memilihnya secara rawak atau dengan mencari purata set kecil nilai yang diambil daripada tatasusunan. Untuk mendapatkan klasifikasi yang optimum, anda mesti memilih nilai yang betul-betul berada di tengah-tengah julat nilai. Walau bagaimanapun, tidak mudah untuk melakukan ini untuk kebanyakan set data. Kes terburuk ialah apabila nilai yang dipilih berada di satu hujung. Walaupun begitu, isihan pantas akan berjalan dengan betul.
Versi isihan pantas yang akan kami bangunkan memilih elemen tengah tatasusunan sebagai perbandingan.

Lihat QSDemo.java.

Isih Pantas:

• Salah satu algoritma pengelasan yang paling cekap dan digunakan secara meluas.
• Dicipta oleh C.A.R. Hoare.
• Berdasarkan konsep partition, di mana tatasusunan dibahagikan kepada bahagian yang disusun secara rekursif.
• Lebih cekap daripada jenis gelembung dan kaedah mudah lain.

Operasi:

• Nilai Perbandingan (Pivot):
• Nilai dipilih sebagai rujukan (pangsi) dan tatasusunan disusun di sekitar nilai tersebut.
• Elemen yang lebih kecil daripada pangsi pergi ke satu sisi dan yang lebih besar ke yang lain.
• Proses diulang secara rekursif untuk setiap bahagian sehingga tatasusunan diisih sepenuhnya.

Quicksort

QSDemo

Atas ialah kandungan terperinci Cuba Isih Pantas Ini. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!