Jenis Cepat adalah semacam jenis pertukaran divisi yang diusulkan oleh Crahoare pada tahun 1962. Gagasan dasar metode ini adalah:
1. Pertama ambil angka dari urutan sebagai nomor referensi.
2. Dalam proses partisi, letakkan semua angka lebih besar dari angka ini di sebelah kanannya, dan semua angka lebih kecil dari atau sama dengan kirinya.
3. Ulangi langkah kedua untuk interval kiri dan kanan sampai hanya ada satu angka di setiap interval.
Algoritma memiliki ide yang jelas, tetapi jika nilai batas tidak ditangani dengan baik selama proses divisi interval, mudah untuk menyebabkan bug. Berikut ini adalah dua pemikiran yang lebih jelas untuk memandu penulisan kode divisi interval.
Jenis pemikiran pertama adalah apa yang disebut metode penggalian pit penggalian. Berikut ini adalah menganalisis proses metode penggalian pit dengan menganalisis contoh:
Mengambil array sebagai contoh, ambil nomor pertama dalam interval sebagai nomor referensi.
Awalnya, kiri = 0; benar = 9; X = a [kiri] = 72
Karena angka dalam [0] telah disimpan ke X, itu dapat dipahami sebagai menggali lubang di array A [0], dan data lain dapat diisi di sini.
Mulai dari kanan dan cari sejumlah <= x. Jelas, ketika kanan = 8, jika kondisinya terpenuhi, gali [8] dan isi ke dalam lubang sebelumnya [kiri]. Pit A [0] dipecahkan, tetapi lubang baru [8] terbentuk. Apa yang harus saya lakukan? Sederhana, temukan nomornya untuk mengisi lubang A [8]. Kali ini, mulailah dari kiri dan temukan angka lebih besar dari X. Ketika kiri = 3, memenuhi syarat, gali [3] dan isi di lubang sebelumnya [kanan];
Array menjadi:
Ulangi langkah -langkah di atas dan array terakhir akan menjadi bentuk berikut:
Dapat dilihat bahwa angka -angka sebelum [5] lebih kecil dari itu, dan angka setelah [5] lebih besar dari itu. Isi x ke dalam lubang [5] dan data menjadi:
Oleh karena itu, ulangi langkah-langkah di atas untuk dua sub-interval A [0 ... 4] dan [6 ... 9].
Ringkasan jumlah lubang yang digali
1. I = l; j = r; Gali nomor referensi untuk membentuk lubang pertama [i].
2. J-Dari belakang ke depan, temukan angka yang lebih kecil dari itu, gali nomor ini dan isi lubang sebelumnya [i].
3. I ++ menemukan angka lebih besar dari itu dari depan ke belakang, dan setelah menemukannya, gali angka ini dan isi di lubang sebelumnya [j].
4. Ulangi langkah 2 dan 3 sampai i == J, dan isi nomor referensi ke dalam [i].
Ikuti metode partisi ini, kode Java dengan cepat diurutkan sebagai berikut:
Partisi kelas publik { / ** * Berdasarkan divisi dasar, yang kecil ada di sebelah kiri dan yang besar ada di sebelah kanan, dan seluruh urutan tidak perlu dipesan * * @param ary * @param base * / sort void statis (int [] ary, int basis) {int kiri = 0; int right = ary.length - 1; int leftpoint = kiri, kanan = kanan; while (true) {// Bagilah ke kiri dan kanan ke kanan pada saat yang sama untuk membandingkan, dari kiri ke kanan, sementara (titik kiri <kanan && ary [leftpoint ++] <base); // titik kiri lebih besar dari kanan atau [titik kiri]> basis berhenti melingkar sementara (rightpoint> = kiri && ary [rightpoint--]> base); // sebaliknya System.out.println ("Indeks yang perlu ditukar di sebelah kiri:" + (LeftPoint-1)); System.out.println ("Indeks yang perlu ditukar di sebelah kanan:"+ (RightPoint+ 1)); // Dua indeks yang tidak memenuhi kondisi diperoleh di atas, yaitu dua indeks yang perlu ditukar jika (titik kiri - 1 <rightpoint + 1) {// swap (ary, titik kiri - 1, titik kanan + 1); Util.printarray (ary); titik kiri = kiri; RightPoint = benar; } else {break; }}} private static void swap (int [] ary, int a, int b) {int temp = ary [a]; ary [a] = ary [b]; ary [b] = temp; } public static void main (string [] args) {int [] ary = util.generateInray (10); System.out.println ("Urutan Asli:"); Util.printarray (ary); sortir (ary, 5); System.out.println ("Diurutkan:"); Util.printarray (ary); }} hasil:
Urutan asli: [2, 8, 4, 3, 7, 5, 1, 9, 0, 6] Indeks untuk pertukaran di sebelah kiri: 1 indeks ke pertukaran di sebelah kanan: 8 [2, 0, 4, 3, 7, 5, 1, 9, 8, 6] indeks ke kiri: indeks ke kanan di sebelah kanan: 6 [2, 0, 4, 3, 1, 5, 7, 9, 9, 9, 9, 6, 6, 6 [2, 0, 0, 4, 3, 1, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 yang bertukar yang bertukar yang tepat yang di sebelah kanan ””. Penyortiran: [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
Pemikiran lain pemikiran divisi interval:
Gunakan elemen pertama dari array sebagai nilai interval, partisi dari elemen kedua sampai hasil yang ditunjukkan pada gambar terbentuk.
Kemudian pertukaran nilai batas kanan dan t dari interval L <t untuk membentuk hasil berikut:
Dengan cara ini, Anda dapat menulis kode sortir cepat sebagai berikut:
public void qsort (int array [], int kiri, int kanan) {if (kiri <kanan) {int key = array [kiri]; int tinggi = kanan; int low = kiri+1; while (true) {while (rendah <= high && array [rendah] <= key) rendah ++; while (rendah <= high && array [tinggi]> = key) tinggi--; if (rendah> high) break; swap (array, rendah, tinggi); } swap (array, kiri, tinggi); printarray (array); qsort (array, kiri, tinggi-1); qsort (array, tinggi+1, kanan); }}