Penyortiran cepat mungkin terasa sangat cepat ketika Anda mendengar nama ini, tetapi kasus terburuk dari kompleksitas waktu algoritmanya sama dengan penyortiran penyisipan. Alasan mengapa itu menjadi jenis yang cepat adalah karena efisiensi rata -rata lebih cepat dari penyortiran yang cepat. Perlu membuka ruang penyimpanan baru secara langsung di array asli. Gagasan penyortiran cepat sangat sederhana, yaitu memilih kata kunci K untuk membagi array asli menjadi dua bagian G1 dan G2. untuk k. Metode sortir dalam kode adalah deskripsi pernyataan itu sekarang. Algoritma utama adalah menemukan lokasi K dan membagi array asli menjadi dua bagian. Metode GetPlocation adalah inti dari penyortiran cepat. Prinsip implementasinya sedikit seperti menyisipkan penyortiran tetapi sedikit seperti. Setiap kali, elemen pada posisi akhir di peta digunakan sebagai kata kunci. dan J lebih besar dari inti. maju. Setelah melingkar seperti ini, awal hingga akhir dipisahkan berdasarkan ukuran.
Salinan kode adalah sebagai berikut:
Quicksort kelas publik {
Public int getPlocation (int [] peta, int start, int end) {
int core = peta [end];
int i = start-1;
untuk (int j = start; j <= end-1; j ++) {
if (peta [j] <= core) {
i ++;
int cache = peta [j];
peta [j] = peta [i];
peta [i] = cache;
}
}
i ++;
peta [end] = peta [i];
peta [i] = core;
Kembalikan i;
}
public void sort (int [] peta, int start, int end) {
if (mulai <end) {
int p = getplocation (peta, start, end);
urutkan (peta, mulai, p-1);
urutkan (peta, p+1, end);
}
}
public static void main (string [] args) {
int [] peta = int baru [] {4,1,5,3,7,12,65,7};
Quicksort qs = quicksort baru ();
qs.sort (peta, 0, peta.length-1);
untuk (int i = 0; i <map.length; i ++) {
System.out.println (peta [i]);
}
}
}