Prinsip Java Quicksort dan Kode Implementasi

Quicksort adalah algoritma penyortiran yang umum digunakan, lebih efisien, dan sering disebutkan selama proses wawancara. Mari kita jelaskan prinsip -prinsipnya secara rinci dan berikan implementasi versi Java.

Ide penyortiran cepat:

Dua bagian independen dibagi dengan menyortir elemen data set RN dalam satu perjalanan. Salah satu bagian dari kata kunci lebih kecil dari bagian lain. Kemudian urutkan kata kunci dari dua bagian satu per satu sampai hanya ada satu elemen independen, dan seluruh koleksi elemen sedang berurutan.

Proses Penyortiran Cepat - Metode menggali lubang dan nomor pengisian (ini adalah nama yang sangat jelas), untuk set elemen r [rendah ... tinggi], pertama -tama ambil angka (biasanya r [rendah]) sebagai referensi , dan R [rendah] mengatur ulang semua elemen sebagai tolok ukur.

Semua yang lebih kecil dari R [rendah] ditempatkan di depan, semua yang lebih besar dari r [rendah] ditempatkan di belakang, dan kemudian r [rendah] digunakan sebagai batas, dan r [rendah ... tinggi] dibagi menjadi dua himpunan bagian dan kemudian dibagi. Sampai rendah> = tinggi.

Sebagai contoh: Proses melakukan penyortiran r = {37, 40, 38, 42, 461, 5, 7, 9, 12} adalah sebagai berikut (Catatan: Tabel elemen berikut yang dijelaskan di bawah ini dimulai dari 0):

Mulailah memilih basis dasar = 37, tabel di bawah ini rendah = 0, tinggi = 8, mulai dari tinggi = 8, jika r [8] <base, tulis konten di posisi tinggi ke R [rendah], dan kemudian tinggi Posisi kosong, rendah = rendah +1;

Mulailah menyelidik dari rendah, karena rendah = 1, r [rendah]> basis, tulis r [rendah] ke r [tinggi], tinggi = tinggi -1;

Rendah <tinggi terdeteksi, jadi penyortiran cepat pertama masih perlu dilanjutkan:

Pada saat ini rendah = 1, tinggi = 7, karena r [tinggi] <base, r [tinggi] ditulis ke dalam r [rendah], rendah = rendah + 1;

Mulai deteksi dari rendah, rendah = 2, r [rendah]> basis, jadi r [rendah] ditulis ke r [tinggi], tinggi = tinggi-1;

Terus mendeteksi rendah kurang dari tinggi

Pada saat ini rendah = 2, tinggi = 6, juga, r [tinggi] <base, tulis r [tinggi] ke r [rendah], rendah = rendah+1;

Lanjutkan untuk mendeteksi dari dasar rendah, rendah = 3, tinggi = 6, r [rendah]> basis, tulis R [rendah] ke r [tinggi], tinggi = tinggi-1;

Terus mendeteksi bahwa rendahnya kurang dari tinggi

Pada saat ini rendah = 3, tinggi = 5, juga, r [tinggi] <base, tulis r [tinggi] ke r [rendah], rendah = rendah +1;

Lanjutkan untuk menyelidiki dari rendah, rendah = 4, tinggi = 5, karena r [rendah]> basis, tulis r [rendah] ke r [tinggi], tinggi = tinggi -1;

Pada saat ini, rendah == tinggi == 4 terdeteksi;

Kemudian lakukan penyortiran cepat rs1 = {12,9,7,5} dan rs2 = {461,42,38,40} sampai hanya ada satu elemen dalam RSI, atau tidak ada elemen.

(Catatan: Dalam bentuk di atas, Anda dapat melihat bahwa ada beberapa data duplikat dalam penyortiran (tidak ada data duplikat dalam data asli). Ini karena data di lokasi itu tidak dihapus. Kami melihat data memori Blokir pada waktu tertentu.

Implementasi Java Sortir Cepat:

Salinan kode adalah sebagai berikut:

private static boolean isEmpty (int [] n) {

return n == null || n.length == 0;

}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///

/**

* Ide Algoritma Penyortiran Cepat - Metode menggali lubang dan mengisi:

*

* @param n array yang akan diurutkan

*/

public static void quicksort (int [] n) {

if (isempty (n))

kembali;

quicksort (n, 0, n.length - 1);

}

public static void quicksort (int [] n, int l, int h) {

if (isempty (n))

kembali;

if (l <h) {

int pivot = partisi (n, l, h);

quicksort (n, l, pivot - 1);

quicksort (n, pivot + 1, h);

}

}

Private Static Int Partition (int [] n, int start, int end) {

int tmp = n [start];

while (mulai <end) {

while (n [end]> = tmp && start <end)

akhir--;

if (mulai <end) {

n [start ++] = n [end];

}

while (n [start] <tmp && start <end)

Mulai ++;

if (mulai <end) {

n [end--] = n [start];

}

}

n [start] = tmp;

Kembalinya Mulai;

}

Ada fungsi seperti ini dalam kode:

Salinan kode adalah sebagai berikut:

public static void quicksortswap (int [] n, int l, int h)

Fungsi ini dapat diimplementasikan untuk mengurutkan elemen data dalam elemen yang ditetapkan antara posisi L dan H tertentu.

Itu saja untuk penyortiran cepat.