Penjelasan terperinci tentang algoritma untuk melaksanakan Quicksort dalam kemahiran Javascript_javascript

Pada masa ini, terdapat kira-kira tujuh atau lapan algoritma pengisihan yang paling biasa, antaranya "Quicksort" adalah yang paling banyak digunakan dan lebih pantas. Ia telah dicadangkan oleh pemenang Anugerah Turing C. A. R. Hoare (1934--) pada tahun 1960.

Idea "isih cepat" sangat mudah Seluruh proses pengisihan hanya memerlukan tiga langkah:

(1) Dalam set data, pilih elemen sebagai "pangsi".

(2) Semua elemen yang lebih kecil daripada "base" dialihkan ke kiri "base"; semua elemen yang lebih besar daripada "base" dialihkan ke kanan "base".

(3) Ulang langkah pertama dan kedua untuk dua subset di sebelah kiri dan kanan "garis dasar" sehingga hanya satu elemen kekal dalam semua subset.

Sebagai contoh, terdapat set data {85, 24, 63, 45, 17, 31, 96, 50}.

Langkah pertama ialah memilih elemen tengah 45 sebagai "garis dasar". (Nilai asas boleh dipilih sewenang-wenangnya, tetapi memilih nilai di tengah lebih mudah difahami.)

Langkah kedua ialah membandingkan setiap elemen dengan "garis dasar" untuk membentuk dua subset, satu "kurang daripada 45" dan satu lagi "lebih besar daripada atau sama dengan 45".

Langkah ketiga ialah mengulangi langkah pertama dan kedua untuk dua subset sehingga hanya satu elemen kekal dalam semua subset.

Yang berikut merujuk kepada maklumat di Internet dan menggunakan bahasa Javascript untuk melaksanakan algoritma di atas.

Pertama, tentukan fungsi quickSort yang parameternya ialah tatasusunan.

var quickSort = function(arr) {
};

Kemudian, semak bilangan elemen dalam tatasusunan, dan jika kurang daripada atau sama dengan 1, kembalikannya.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
};

Seterusnya, pilih "pivot" dan pisahkannya daripada tatasusunan asal, kemudian tentukan dua tatasusunan kosong untuk menyimpan dua subset, 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, mula melintasi tatasusunan, meletakkan elemen yang lebih kecil daripada "garis dasar" ke dalam subset kiri dan elemen yang lebih besar daripada "garis dasar" ke dalam subset 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 = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
};

Akhir sekali, gunakan rekursi untuk mengulangi proses ini untuk mendapatkan tatasusunan yang diisih.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1);
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat(pivot, quickSort(right));
};
 
var dataArray = [85,24,63,45,17,31,96,50];
console.log(dataArray.join(","));
console.log(quickSort(dataArray).join(","));

Saya harap artikel ini akan membantu reka bentuk pengaturcaraan JavaScript semua orang.