Penyortiran cepat adalah menemukan elemen (awalnya Anda dapat menemukan satu) sebagai referensi (pivot), dan kemudian mempartisi array sehingga nilai elemen di sebelah kiri referensi tidak lebih besar dari nilai referensi, dan nilai elemen di sebelah kanan referensi tidak kurang dari nilai referensi. Sortir cepat secara rekursif, sesuaikan elemen N-1 lainnya ke posisi yang benar setelah menyortir. Akhirnya, setiap elemen berada di posisi yang benar setelah penyortiran dan penyortiran selesai. Oleh karena itu, algoritma inti dari algoritma penyortiran cepat adalah operasi partisi, yaitu bagaimana menyesuaikan posisi tolok ukur dan menyesuaikan posisi akhir dari tolok ukur pengembalian untuk membagi dan menaklukkan rekursi.
Algoritma untuk penyortiran cepat adalah:
1) Tetapkan dua variabel I dan J, ketika penyortiran dimulai: i = 0, j = n-1;
2) Gunakan elemen array pertama sebagai data kunci dan tetapkan ke kunci, yaitu, kunci = a [0];
3) Mulai dari J untuk mencari ke depan, yaitu, mulai dari belakang untuk mencari ke depan (J--), temukan nilai pertama A [j] lebih kecil dari kunci, dan bertukar [j] dan [i];
4) Mulai dari I untuk mencari ke belakang, yaitu, mulai dari depan ke mundur (i ++), temukan yang pertama [i] lebih besar dari kunci, dan bertukar [i] dan [j];
5) Ulangi langkah 3 dan 4 sampai i = j; 4 tidak lebih besar dari perubahan nilai J dan I sehingga j = j-1, i = i+1 sampai ditemukan. tetap tidak berubah.
Izinkan saya memberi Anda sebuah contoh, ini mungkin tidak mudah dimengerti. Asumsikan bahwa urutan yang akan diurutkan adalah
Salinan kode adalah sebagai berikut:
paket com.zc.manythread;
impor java.util.random;
/**
* Sortir cepat
* Administrator @Author
*
*/
QSort kelas publik {
int [] tanggal;
qsort publik (int [] tanggal) {
this.date = tanggal;
}
/**
* Fungsi pertukaran
* @param a
* @param i
* @param J.
*/
swap void pribadi (int a [], int i, int j) {
int t;
T = a [i];
a [i] = a [j];
a [j] = t;
}
/*****************************
* Urutkan fungsi
* @param a
* @param lo0
* @param hi0
* @kembali
*/
int [] quicksort (int a [], int lo0, int hi0) {// metode pembagian dan perawatan adalah untuk membagi array menjadi [lo0..q-1] dan [q+1..hi0]
int lo = lo0;
int hi = hi0;
int mid;
if (hi0> lo0) {
mid = a [(hi0+lo0)/2];
while (lo <= hai) {
while ((lo <hi0) && (a [lo] <mid)) ++ lo;
while ((hai> lo0) && (a [hai]> mid)) --hi;
if (lo <= hai) {
swap (a, lo, hai);
++ lo;
--Hai;
}
}
if (lo0 <hai) {
Quicksort (a, lo0, hai);
}
if (lo <hi0) {
Quicksort (a, lo, hi0);
}
}
mengembalikan a;
}
/******************
*
* Buat data array duplikat
**********************/
private static int [] createTate (int count) {
int [] data = int new [count];
untuk (int i = 0; i <data.length; i ++) {
data [i] = (int) (math.random ()*count);
}
pengembalian data;
}
/**
* Tidak ada data array duplikat
* Hitungan @param
* @kembali
*/
private static int [] createTate1 (int count) {
int [] data = int new [count];
Rand acak = acak baru ();
boolean [] bool = boolean baru [100];
int num = 0;
untuk (int i = 0; i <count; i ++) {
Mengerjakan {
// Jika nomor yang dihasilkannya sama, terus loop
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
data [i] = num;
}
pengembalian data;
}
/************ Fungsi utama *******************/
public static void main (string [] args) {
Hitung int akhir = 10;
int [] data = createdate1 (count);
untuk (int n: data) {
System.out.print (n+"/t");
}
Qsort data1 = qsort baru (data);
System.out.println ();
int [] a = data1.quicksort (data, 0, count-1);
untuk (int n: a) {
System.out.print (n+"/t");
}
}
}
Hasilnya adalah sebagai berikut:
Di atas adalah semua konten yang dijelaskan dalam artikel ini.