Contoh untuk menerangkan beberapa algoritma pengisihan yang biasa digunakan dalam JavaScript

JavaScript ialah bahasa pengaturcaraan popular yang digunakan untuk mencipta interaktiviti pada halaman web. Pengisihan adalah salah satu algoritma penting dalam sains komputer, dan pengisihan dalam JavaScript juga merupakan kemahiran yang mesti dikuasai. Dalam artikel ini, kami akan memperkenalkan beberapa algoritma pengisihan yang biasa digunakan dalam JavaScript dan cara melaksanakannya.

1. Isih gelembung

Isih gelembung ialah algoritma pengisihan yang mudah dan intuitif. Idea asasnya ialah membandingkan dua elemen bersebelahan setiap kali, dan jika susunannya tidak betul, tukar kedudukan mereka. Selepas setiap pusingan pengisihan, elemen terbesar dialihkan ke penghujung tatasusunan. Proses ini diulang sehingga keseluruhan tatasusunan diisih.

Berikut ialah pelaksanaan JavaScript bagi jenis gelembung:

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

Dalam kod di atas, kami menggunakan gelung bersarang untuk membandingkan elemen bersebelahan dalam urutan Jika elemen semasa lebih besar daripada yang seterusnya elemen, kemudian Tukar kedudukan mereka. Dalam setiap lelaran gelung, elemen terbesar dialihkan ke penghujung tatasusunan. Kerumitan masa algoritma ini ialah O(n^2).

2. Isih pilihan

Isih pilihan ialah satu lagi algoritma pengisihan yang mudah ialah memilih elemen terkecil dalam tatasusunan setiap kali dan memasukkannya ke dalam digit terakhir urutan yang disusun. Kerumitan masa isihan pemilihan juga O(n^2).

Berikut ialah pelaksanaan JavaScript bagi isihan pemilihan:

function selectionSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      var temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

Dalam kod di atas, kami menggunakan dua gelung bersarang untuk mencari nilai minimum dan menukarnya ke penghujung tatasusunan yang diisih .

3. Isih sisipan

Isihan sisipan ialah algoritma pengisihan yang mudah tetapi cekap Idea asasnya ialah memasukkan elemen untuk diisih ke dalam unsur yang telah diisih. Untuk urutan tidak tertib, kami sentiasa bermula dari elemen pertama, keluarkan satu elemen dari kiri ke kanan, dan kemudian masukkannya ke dalam kedudukan yang sesuai bagi urutan tertib. Sehingga semua elemen diambil, proses pengisihan selesai.

Berikut ialah pelaksanaan JavaScript bagi isihan sisipan:

function insertionSort(arr) {
  var len = arr.length;
  var current, j;
  for (var i = 1; i < len; i++) {
    current = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

Dalam kod di atas, kami menggunakan gelung sementara untuk mengalihkan elemen yang diisih ke kanan untuk memberi ruang kepada elemen baharu. Lokasi. Kerumitan masa algoritma ini ialah O(n^2).

4. Isih cepat

Isih cepat ialah algoritma pengisihan yang biasa digunakan dan cekap. Idea asas ialah memilih nombor asas dan membandingkan semua nombor dalam urutan dengan nombor asas ini. Letakkan nombor yang lebih kecil daripada nombor asas di sebelah kiri nombor asas, dan nombor yang lebih besar daripada nombor asas di sebelah kanan nombor asas, dan kemudian memproses urutan kiri dan kanan secara rekursif.

Berikut ialah pelaksanaan JavaScript bagi isihan pantas:

function quickSort(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]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

Dalam kod di atas, kami mula-mula memilih nombor rujukan, kemudian melintasi keseluruhan jujukan, dan meletakkan nombor lebih kecil daripada nombor rujukan ke dalam tatasusunan, letakkan nombor yang lebih besar daripada nombor asas ke dalam tatasusunan lain. Akhir sekali, kami memproses tatasusunan kiri dan kanan secara rekursif dan menggabungkannya dengan nombor asas. Kerumitan masa algoritma ini ialah O(nlogn).

Ringkasan

Artikel ini memperkenalkan beberapa algoritma pengisihan biasa dan pelaksanaannya dalam JavaScript. Sama ada isihan gelembung, isihan pemilihan atau isihan sisipan, semuanya adalah algoritma pengisihan yang sangat asas dan mudah difahami, sesuai untuk dipelajari dan difahami oleh pemula. Jika anda mempunyai kajian yang lebih mendalam dan komprehensif tentang algoritma pengisihan, anda juga boleh cuba menggunakan beberapa algoritma pengisihan lanjutan, seperti isihan gabungan, isihan timbunan, dsb.

Atas ialah kandungan terperinci Contoh untuk menerangkan beberapa algoritma pengisihan yang biasa digunakan dalam JavaScript. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!