Gagasan "penyortiran cepat" sangat sederhana, dan seluruh proses penyortiran hanya membutuhkan tiga langkah:
(1) Dalam dataset, pilih elemen sebagai "basis" (pivot).
(2) semua elemen yang lebih kecil dari "referensi" dipindahkan ke kiri "referensi"; Semua elemen yang lebih besar dari "referensi" dipindahkan ke kanan "referensi".
(3) Untuk dua himpunan bagian di sebelah kiri dan kanan "baseline", ulangi langkah pertama dan kedua sampai hanya ada satu elemen yang tersisa di semua subset.
Misalnya, sekarang ada dataset {85, 24, 63, 45, 17, 31, 96, 50}. Bagaimana cara mengurutkannya?
Pada langkah pertama, pilih elemen menengah 45 sebagai "basis". (Nilai referensi dapat dipilih secara sewenang -wenang, tetapi memilih nilai perantara lebih mudah dipahami.)
Langkah kedua adalah membandingkan setiap elemen dengan "basis" untuk membentuk dua himpunan bagian, satu adalah "kurang dari 45" dan yang lainnya "lebih besar dari atau sama dengan 45".
Langkah ketiga adalah mengulangi langkah pertama dan kedua untuk dua himpunan bagian sampai hanya ada satu elemen yang tersisa di semua subset.
Berikut ini adalah referensi untuk informasi online (di sini dan di sini) untuk mengimplementasikan algoritma di atas dalam bahasa JavaScript.
Pertama, tentukan fungsi quicksort yang parameternya adalah array.
var quicksort = function (arr) {};Kemudian, periksa jumlah elemen dalam array, dan jika kurang dari atau sama dengan 1, itu akan dikembalikan.
var quicksort = function (arr) {if (arr.length <= 1) {return arr; }};Selanjutnya, pilih "pivot" dan pisahkan dari array asli, dan kemudian tentukan dua array kosong untuk menyimpan dua himpunan bagian dari satu kiri dan satu kanan.
var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var left = []; var right = [];};Kemudian, mulailah melintasi array, masukkan elemen lebih kecil dari "pangkalan" ke dalam subset di sebelah kiri, dan elemen lebih besar dari pangkalan ke dalam subset di sebelah kanan.
var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var left = []; var right = []; untuk (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }}};Akhirnya, ulangi proses ini secara terus -menerus menggunakan rekursi untuk mendapatkan array yang diurutkan.
var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var left = []; var right = []; untuk (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} return quicksort (kiri) .concat ([pivot], quicksort (kanan));};Saat menggunakannya, cukup hubungi QuickSort ().
Di atas adalah penjelasan terperinci tentang contoh algoritma quicksort dari seri algoritma JavaScript yang diperkenalkan oleh editor. Saya harap ini akan membantu semua orang. Jika Anda memiliki pertanyaan, silakan tinggalkan saya pesan dan editor akan membalas semua orang tepat waktu. Terima kasih banyak atas dukungan Anda ke situs web Wulin.com!