Dibandingkan dengan algoritma seperti penyortiran gelembung, penyortiran seleksi, dll., Prinsip algoritma spesifik dan implementasi penyortiran cepat sulit. Untuk lebih memahami penyortiran cepat, kami masih menggambarkan prinsip -prinsip algoritmik penyortiran cepat secara rinci dalam bentuk contoh. Dalam algoritma penyortiran sebelumnya, kami akan menggunakan masalah penyortiran tinggi dari 5 atlet sebagai contoh untuk menjelaskannya. Untuk lebih mencerminkan karakteristik penyortiran cepat, kami akan menambahkan 3 atlet lagi di sini. 8 atlet dan informasi tinggi mereka dalam contoh adalah sebagai berikut (f, g, h adalah atlet baru): a (181), b (169), c (187), d (172), e (163), f (191), g (189), h (182)
Dalam algoritma penyortiran sebelumnya, semua penyortiran ini dilakukan oleh pelatih. Sekarang jumlah atlet telah meningkat, pelatih juga ingin mengambil kesempatan untuk beristirahat, sehingga pelatih memanggil dua asisten dan meminta dua asisten untuk mengurutkan ketinggian 8 atlet dari kiri ke kanan dan rendah ke tinggi dengan cara penyortiran cepat.
Menurut prinsip algoritma dari metode penyortiran cepat, kedua asisten berdiri di kedua sisi pengaturan atlet, seperti yang ditunjukkan pada gambar di bawah ini:
Pertama, Asisten 1 memilih atlet dari pengaturan (biasanya memilih atlet pertama di kiri atau atlet tengah), dan di sini memilih atlet A (181). Karena penyortiran berasal dari kiri ke kanan dan dari rendah ke tinggi, Asisten 1 membutuhkan atlet yang lebih kecil dari A (181) (A (181) yang dipilih digunakan sebagai tolok ukur untuk perbandingan. Semua perbandingan dalam putaran ini dibandingkan dengan atlet A (181)) yang dipilih yang awalnya dipilih (181)):
Mari kita terus merujuk ke diagram terperinci dari putaran pertama penyortiran cepat.
Ketika kedua asisten bertemu selama proses penyortiran dan pencarian, perbandingan putaran saat ini dihentikan dan atlet A (181) yang awalnya dipilih ditempatkan di ruang kosong di mana kedua asisten bertemu:
Dengan cepat, putaran penyortiran ini berakhir ketika dua asisten bertemu. Pada saat ini, kami menemukan bahwa menggunakan posisi A (181) di mana kedua atlet bertemu sebagai titik divisi, yang di sebelah kiri adalah atlet yang lebih kecil dari (181), dan yang di sebelah kanan adalah atlet yang lebih besar dari (181). Pada saat ini, kami akan memisahkan dua jenis di sisi kiri dan kanan A (181). Jika kita terus mengurutkan pengaturan di kedua sisi menggunakan metode penyortiran dua asisten di atas, maka setelah beberapa pengaturan, kita akhirnya akan mendapatkan hasil penyortiran yang kita butuhkan.
Di atas adalah seluruh proses implementasi penyortiran dari penyortiran cepat. Penyortiran cepat adalah menggunakan aturan penyortiran di atas untuk membagi pengaturan menjadi dua pengaturan, dan dua pengaturan menjadi empat pengaturan sampai tidak ada pengaturan untuk dibagi, dan akhirnya kita mendapatkan hasil penyortiran yang kita butuhkan.
Sekarang, kami masih memprogram kode java untuk mengurutkan ketinggian dari 8 atlet di atas menggunakan jenis cepat:
/*** Penyortiran cepat elemen dalam array yang ditentukan dari awal hingga akhir** @param array array yang ditentukan* @param mulai titik yang dihasilkan dari penyelidikan array yang perlu dengan cepat diurut setara dengan posisi asisten 2 int i = mulai, j = end; int pivot = array [i]; // Ambil elemen pertama sebagai elemen referensi int emplementIndex = i; // Indeks posisi ruang kosong ditunjukkan, dan standarnya adalah posisi elemen referensi yang diambil // Jika ada lebih dari 1 elemen untuk mengurutkan, masukkan sortir cepat (selama saya dan j berbeda, itu berarti bahwa setidaknya 2 elemen perlu diurut if (i <j) {// Jika Asisten 2 menemukan elemen yang sesuai sebelum bertemu dengan Asisten 1, itu memberikan elemen pada "lowongan" asisten 1, j menjadi array ruang kosong [kosongIndex] = array [kosongIndex = j]; } // Asisten 1 mulai mencari elemen yang lebih besar dari elemen referensi dari kiri ke kanan (i <j && array [i] <= pivot) i ++; if (i <j) {// Jika Asisten 1 menemukan elemen yang sesuai sebelum bertemu dengan Asisten 2, itu akan memberikan elemen pada "lowongan" asisten 2, dan saya menjadi array kosong [kosongIndex] = array [kosongIndex = i]; }} // Setelah asisten 1 dan asisten 2 pertemuan, loop akan berhenti dan nilai referensi awal dibawa ke array kosong terakhir [emplemIndex] = pivot; // ===== Putaran penyortiran cepat ini selesai ===== // Jika ada lebih dari 2 elemen di sisi kiri titik split I, panggilan rekursif terus dengan cepat mengurutkannya jika (i - mulai> 1) {Quicksort (array, 0, i - 1); } // Jika ada lebih dari 2 elemen di sisi kanan titik split j, panggilan rekursif terus dengan cepat mengurutkannya jika (end - j> 1) {quicksort (array, j + 1, end); }}//Main method public static void main(String[] args) { // =====Sort from low to high using quick sort method to represent the heights of 8 athletes ===== // A(181), B(169), C(187), D(172), E(163), F(191), G(189), H(182) int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182}; // Panggil metode pengurutan cepat Quicksort (Heights, 0, Heights.length - 1); // hasil yang diurutkan output untuk (int height: heights) {System.out.println (tinggi); }}Hasil menjalankan kode java di atas adalah output sebagai berikut:
163169172181182187189191
Catatan: Karena perbedaan pemikiran lokal, mungkin ada beberapa variasi dalam implementasi kode yang diurutkan di atas. Namun, tidak peduli apa varian itu, gagasan inti dari penyortiran cepat tidak akan berubah.
Implementasi lain: pemindaian satu arah
Ada versi pemindaian satu arah lain untuk pengiris array penyortiran cepat. Langkah spesifik adalah memilih elemen terakhir dalam array sebagai elemen pengiris, dan mengatur dua pointer. Pointer I menunjuk ke posisi di depan elemen pertama dalam array, dan J menunjuk ke elemen pertama dalam array. J memindai dari depan ke kanan dan kanan. Saat menemukan elemen pengiris kurang dari atau sama dengan, tambahkan saya ke satu, dan kemudian bertukar elemen yang ditunjukkan oleh i dan j. Akhirnya, bertukar elemen pada posisi i+1 dan elemen pengiris untuk menyelesaikan divisi array. Implementasi kode adalah sebagai berikut:
int partisi (int [] a, int lo, int hi) {int i = lo - 1, j = lo; int v = a [hai]; while (j <hi) {if (a [j] <= v) {swap (a, ++ i, j); } j ++; } swap (a, i + 1, hai); return i + 1;}