Laksanakan isihan sisipan menggunakan JavaScript untuk mengisih tatasusunan nombor dalam tertib menaik

Seni pengisihan tatasusunan adalah penting dalam dunia pengaturcaraan kerana ia membolehkan organisasi dan manipulasi data yang cekap. Apabila ia datang untuk melaksanakan algoritma pengisihan yang boleh dipercayai, isihan sisipan menjadi pilihan yang serba boleh dan cekap. Dalam artikel ini, kami menyelidiki dunia JavaScript yang kompleks dan meneroka proses melaksanakan isihan sisipan untuk mengisih tatasusunan nombor dalam tertib menaik. Dengan memahami mekanisme asas algoritma dan memanfaatkan kuasa JavaScript, pembangun boleh membuka kunci potensi untuk mengisih dan menyusun data berangka dengan cekap, dengan itu meningkatkan prestasi aplikasi dan kebolehgunaan.

Pernyataan Masalah

Cabaran semasa melibatkan tugas melaksanakan algoritma isihan sisipan menggunakan JavaScript untuk mengisih tatasusunan nombor dalam tertib menaik. Matlamat utama adalah untuk mereka bentuk atur cara yang bijak boleh menyusun semula elemen tatasusunan yang diberikan, memastikan setiap elemen berikutnya diletakkan pada kedudukan yang betul berbanding dengan elemen sebelumnya berdasarkan nilai berangkanya. Sebagai contoh, katakan kami menyediakan tatasusunan

[9, 2, 7, 4, 1]

Selepas melaksanakan algoritma isihan sisipan, hasil yang dijangkakan ialah tatasusunan mengikut susunan yang semakin meningkat, seperti

[1, 2, 4, 7, 9]

Kaedah

Dalam artikel ini kita akan melihat beberapa cara berbeza untuk menyelesaikan masalah di atas dalam JavaScript -

• Isihan sisipan asas

• Isihan sisipan binari

• Isihan sisipan rekursif

Kaedah 1: Isihan sisipan asas

Algoritma isihan sisipan asas mengekalkan sub-tatasusunan yang diisih dalam tatasusunan. Bermula dengan elemen kedua, setiap elemen dibandingkan dengan elemen sebelumnya dalam subarray dan dialihkan ke kanan jika lebih kecil. Proses ini berterusan sehingga kedudukan yang betul ditemui dan elemen dimasukkan. Proses ini diulang untuk semua elemen, menghasilkan tatasusunan yang diisih sepenuhnya.

Contoh

Fungsi insertionSort mengambil susunan tatasusunan sebagai input dan mengembalikan tatasusunan yang diisih menggunakan algoritma isihan sisipan. Ia berulang bermula dari elemen kedua dan menyimpannya dalam pembolehubah semasa. Gelung while membandingkan elemen semasa dengan elemen sebelumnya dalam subarray yang diisih, menggerakkan elemen yang lebih besar ke kanan. Gelung berterusan sehingga permulaan tatasusunan dicapai atau elemen yang lebih kecil ditemui. Elemen semasa kemudiannya dimasukkan ke dalam subarray yang diisih pada kedudukan yang betul. Proses ini diulang untuk semua elemen, menghasilkan tatasusunan yang diisih.

function insertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let j = i - 1;
      while (j >= 0 && arr[j] > current) {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));

Output

Berikut ialah output konsol -

[ 1, 2, 4, 7, 9 ]

Kaedah 2: Isihan sisipan binari

Algoritma isihan sisipan binari meningkatkan kecekapan isihan sisipan asas dengan menggunakan carian binari dalam subray yang diisih untuk menentukan kedudukan yang betul bagi setiap elemen. Daripada carian linear, carian binari dilakukan dengan membandingkan elemen semasa dengan elemen tengah subarray, dan melaraskan sempadan carian dengan sewajarnya. Setelah titik sisipan ditentukan, elemen dialihkan ke kanan untuk memberi ruang, dan elemen semasa dimasukkan. Proses ini diulang untuk semua elemen, menghasilkan tatasusunan yang diisih sepenuhnya.

Contoh

fungsi binaryInsertionSort mengambil susunan tatasusunan dan mengembalikan tatasusunan yang diisih menggunakan algoritma isihan sisipan binari. Ia berulang bermula dari elemen kedua, dengan mengandaikan elemen pertama diisih. Elemen semasa disimpan dalam pembolehubah semasa. Algoritma melakukan carian binari dalam subarray yang diisih untuk mencari kedudukan yang betul bagi elemen semasa dengan membandingkannya dengan elemen tengah dan melaraskan sempadan carian. Setelah kedudukan ditemui, algoritma menggerakkan elemen ke kanan dan memasukkan elemen semasa ke kedudukan yang betul. Proses ini diulang untuk semua elemen, menghasilkan tatasusunan yang diisih.

function binaryInsertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let left = 0;
      let right = i - 1;
      while (left <= right) {
         let mid = Math.floor((left + right) / 2);
         if (current < arr[mid]) {
            right = mid - 1;
         } else {
            left = mid + 1;
         }
      }
      for (let j = i - 1; j >= left; j--) {
         arr[j + 1] = arr[j];
      }
      arr[left] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));

Output

Berikut ialah output konsol -

[ 1, 2, 4, 7, 9 ]

Kaedah 3: Isihan sisipan rekursif

Algoritma isihan sisipan rekursif ialah versi rekursif isihan sisipan yang menggunakan rekursif untuk mengisih tatasusunan. Untuk subarray bersaiz 1 atau kurang, ia menganggapnya telah diisih. Untuk subarray yang lebih besar, ia memanggil dirinya secara rekursif untuk mengisih subarray tanpa elemen terakhir. Selepas panggilan rekursif kembali dan subarray diisih, algoritma meletakkan elemen terakhir pada kedudukan yang betul dalam subarray yang diisih. Ini dicapai dengan membandingkan elemen terakhir dengan elemen dalam subarray yang diisih dan mengalihkannya ke kanan jika perlu. Ulangi proses ini sehingga semua elemen dimasukkan ke dalam kedudukan yang betul, menghasilkan tatasusunan yang diisih sepenuhnya.

Contoh

Fungsi rekursifInsertionSort secara rekursif menggunakan algoritma isihan sisipan pada tatasusunan input. Ia menyemak sama ada tatasusunan diisih dan mengembalikannya jika ya. Jika tidak, ia memanggil dirinya secara rekursif pada subarray saiz n - 1. Selepas dipanggil secara rekursif, fungsi menggunakan gelung sementara untuk membandingkan elemen terakhir dengan elemen dalam subarray yang diisih. Jika elemen lebih besar, ia akan dialihkan ke kanan. Proses ini berterusan sehingga gelung mencapai permulaan tatasusunan atau elemen yang lebih kecil ditemui. Akhirnya, elemen terakhir dimasukkan pada kedudukan yang betul. Proses ini diulang untuk semua elemen, menghasilkan tatasusunan yang diisih.

function recursiveInsertionSort(arr, n = arr.length) {
   if (n <= 1) return arr;
 
   recursiveInsertionSort(arr, n - 1);
 
   let last = arr[n - 1];
   let j = n - 2;
 
   while (j >= 0 && arr[j] > last) {
      arr[j + 1] = arr[j];
      j--;
   }
 
   arr[j + 1] = last;
 
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));

Output

Berikut ialah output konsol -

[ 1, 2, 4, 7, 9 ]

结论

最终，使用 JavaScript 实现插入排序算法以升序排列数字数组，对于寻求熟练排序方法的开发人员来说是一个精明的选择。通过迭代地将元素放置在适当的位置，该算法展示了一种组织数值数据的敏锐方法。虽然插入排序可能不像其他排序技术那样广受好评，但它的效率和简单性使其在某些情况下成为非常宝贵的工具。在 JavaScript 中使用此算法使开发人员能够在其编码库中使用鲜为人知但功能强大的工具，从而生成精简且有序的数组。总之，利用 JavaScript 中插入排序算法的强大功能，对于那些在数组排序中寻求精确性和优雅性的人来说，是一种不切实际的努力。

Atas ialah kandungan terperinci Laksanakan isihan sisipan menggunakan JavaScript untuk mengisih tatasusunan nombor dalam tertib menaik. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!