Konsep algoritma penyortiran cepat
Penyortiran cepat umumnya didasarkan pada implementasi rekursif. Idenya adalah sebagai berikut:
1. Pilih nilai yang sesuai (nilai ideal adalah yang terbaik, tetapi nilai pertama dalam array umumnya digunakan dalam implementasi), yang disebut "pivot".
2. Berdasarkan nilai ini, bagi array menjadi dua bagian, bagian yang lebih kecil di sebelah kiri dan bagian yang lebih besar di sebelah kanan.
3. Sudah pasti bahwa setelah putaran seperti itu, posisi pivot ini harus berada di posisi akhir.
4. Ulangi proses di atas untuk dua subarray sampai hanya ada satu elemen per array.
5. Penyortiran selesai.
Metode Implementasi Dasar:
public static void quicksort (int [] arr) {qsort (arr, 0, arr.length-1);} private static void qsort (int [] arr, int rendah, int tinggi) {if (rendah <tinggi) {int pivot = partisi (arr, rendah, tinggi); // Bagilah array menjadi dua bagian qsort (arr, rendah, pivot-1); // urutkan qsort subarray kiri (arr, pivot+1, tinggi); // urutkan subarray kanan secara rekursif}} private static int partition (int [] arr, int low, int high) {int pivot = arr [low]; // Pivot Record while (Low <High) {while (Low <high && arr [High]> = pivot) - -High; arr [rendah] = arr [tinggi]; // SWAP Records lebih kecil dari pivot ke kiri sementara (Low <High && arr [Low] <= pivot) ++ Low; arr [tinggi] = arr [rendah]; // Catatan swap lebih kecil dari pivot ke ujung kanan} // scan selesai, dan pivot ada di tempat arr [rendah] = pivot; // Kembalikan posisi pivot ke pengembalian rendah;}Gunakan obat generik untuk mengimplementasikan algoritma pesanan cepat
Di bawah ini adalah kelas quicksort, yang berisi fungsi statis (), yang dapat mengurutkan array jenis apa pun. Jika itu adalah array tipe objek, tipe objek harus mengimplementasikan antarmuka yang sebanding sehingga fungsi perbandingan dapat digunakan untuk perbandingan.
Algoritma penyortiran baris cepat paling dasar digunakan dan tidak ada pemrosesan optimasi yang dilakukan.
Kode sumber adalah sebagai berikut:
impor java.util.linkedlist; impor java.util.list; impor java.util.listiterator; impor java.util.random; Public Class QuickSort {@suppressWarnings ("Uncecked") // Ubah prototipe fungsi baris cepat di atas sehingga dapat mengurutkan array jenis objek apa pun. Fungsi ini digunakan secara internal, dan antarmuka fungsi penyortiran eksternal adalah sort (). Fungsi Sort mensyaratkan bahwa objek harus mengimplementasikan antarmuka yang sebanding, yang dapat memberikan deteksi jenis waktu kompilasi, lihat artikel berikut. private static void quicksort (objek [] di, int begin, int end) {if (begin == end || begin == (end-1)) return; Objek p = di [begin]; int a = mulai +1; int b = a; untuk (; b <end; b ++) {// Array tipe objek ini harus mengimplementasikan antarmuka yang sebanding sehingga Anda dapat menggunakan fungsi compareTo untuk perbandingan if ((((objek> yang sebanding) di [b]). compareTo (p) <0) {if (a == b) {a ++; Lanjutkan;} objek temp = di [a]; di [a] = di [b]; di [b] = temp; a ++; }} di [begin] = di [a-1]; dalam [a-1] = p; if (a-1> begin) {quicksort (dalam, mulai, a); } if (end-1> a) {quicksort (in, a, end); } kembali; } // Gunakan generik untuk mengurutkan array objek apa pun, array tipe objek harus mengimplementasikan antarmuka yang sebanding public static <t meluas sebanding <? super t >> void sort (t [] input) {quicksort (input, 0, input.length); } // Tambahkan fungsi objek daftar penyortiran, lihat fungsi sort () dari kelas java.util.collections di java public static <t meluas sebanding <? super t >> void sort (daftar <t> daftar) {objek [] t = list.toArray (); // Konversi daftar ke array quicksort (t, 0, t.length); // urutkan array // setelah penyortiran array selesai, tulis kembali ke daftar daftar <t> i = list.listiterator (); untuk (int j = 0; j <t.length; j ++) {i.next (); i.set ((t) t [j]); }} // Karena obat generik tidak dapat digunakan dalam java, tipe data primitif (int, ganda, byte, dll.), Anda hanya dapat menggunakan mekanisme kelebihan fungsi untuk mengurutkan array primitif ini (int [], ganda [], byte [], dll.). Untuk berbagi fungsi penyortiran yang sama, mekanisme jenis asli (autoboxing, unboxing) digunakan untuk merangkumnya ke dalam jenis objek yang sesuai, membentuk array objek baru, diurutkan dan kemudian menghilangkannya. Kerugian dari ini adalah bahwa ia membutuhkan langkah konversi tambahan dan ruang tambahan untuk menyimpan array yang dienkapsulasi. Cara lain adalah menyalin kode sortir ke setiap fungsi yang kelebihan beban. Fungsi sort () di kelas java.util.arrays di API resmi menggunakan metode ini, yang dapat dilihat dari kode sumber kelas array. public static void sort (int [] input) {integer [] t = new integer [input.length]; untuk (int i = 0; i <input.length; i ++) {t [i] = input [i]; // enkapsulasi} quicksort (t, 0, t.length); // penyortiran untuk (int i = 0; i <input.length; i ++) {input [i] = t [i];//viroid}} {input [i] = t [i];//publiculation}} {input [i] = t [i];//input. sortir (input [] double) {double [] t = double baru [input.length]; untuk (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); untuk (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // fungsi berlebih dari byte [] array public static void sort (byte [] input) {byte [] t = byte baru [input.length]; untuk (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); untuk (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); untuk (int i = 0; i <input.length); input.length; i ++) {input [i] = t [i]; }} // pendek [] fungsi kelebihan public static void sort (pendek [] input) {short [] t = baru pendek [input.length]; untuk (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); untuk (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // pendek [] fungsi kelebihan public static void sort (char [] input) {karakter [] t = karakter baru [input.length]; untuk (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); untuk (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // fungsi kelebihan float [] array public static void sort (float [] input) {float [] t = new float [input.length]; untuk (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); untuk (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Fungsi utama untuk menguji public static void main (string [] args) {// menghasilkan array int [] yang terdiri dari angka acak untuk menguji int len = 10; int [] input = int new [len]; Acak r = acak baru (); System.out.print ("int [] sebelum menyortir:"); untuk (int i = 0; i <input.length; i ++) {input [i] = r.nextint (10*len); System.out.print (input [i] + ""); } System.out.println (); System.out.print ("int [] setelah penyortiran:"); urutkan (input); untuk (int i: input) {System.out.print (i + ""); } System.out.println (); // menghasilkan array string untuk menguji string [] s = string baru [] {"b", "a", "e", "d", "f", "c"}; System.out.print ("String [] sebelum menyortir:"); untuk (int i = 0; i <s.length; i ++) {System.out.print (s [i]+""); } System.out.println (); System.out.print ("String [] setelah penyortiran:"); sortir; untuk (int i = 0; i <s.length; i ++) {System.out.print (s [i]+""); } System.out.println (); // Hasilkan daftar string ke daftar uji <string> l = LinkedList baru <string> (); s = string baru [] {"b", "a", "e", "d", "f", "c"}; System.out.print ("LinkedList <String> sebelum menyortir:"); untuk (int j = 0; j <s.length; j ++) {l.add (s [j]); System.out.print (S [j] + ""); } System.out.println (); urutkan (l); System.out.print ("LinkedList <String> setelah penyortiran:"); untuk (string ts: l) {system.out.print (ts + ""); } System.out.println (); }}Jalankan tes fungsi utama, dan dari output, Anda dapat melihat bahwa kelas Quicksort berfungsi secara normal:
int[] before sorting: 65 48 92 26 3 8 59 21 16 45int[] after sorting: 3 8 16 21 26 45 48 59 65 92String[] before sorting: baedfc String[] after sorting: abcdef LinkedList<String> before sorting: baedfc LinkedList<String> after sorting: abcdef