Pelaksanaan mudah beberapa algoritma pengisihan dalam pengetahuan JavaScript_Basic

Pelaksanaan algoritma pengisihan

Kemahiran JS saya lemah, jadi saya menggunakan kaedah yang serupa dengan JAVA dan C untuk menulis algoritma pengisihan JavaScript.

Dan saya tidak akan bercakap tentang prinsip algoritma di sini, hanya pelaksanaan kod, mungkin terdapat pepijat, semua orang dialu-alukan untuk mengulas di blog untuk panduan.
Isihan sisipan

Penerangan algoritma bagi Insertion-Isih ialah algoritma pengisihan yang mudah dan intuitif. Ia berfungsi dengan membina urutan tersusun Untuk data yang tidak diisih, ia mengimbas dari belakang ke hadapan dalam urutan yang diisih, mencari kedudukan yang sepadan dan memasukkannya. Dalam pelaksanaan isihan sisipan, pengisihan di tempat biasanya digunakan (iaitu, pengisihan yang hanya menggunakan ruang tambahan O(1) Oleh itu, semasa proses pengimbasan dari belakang ke hadapan, ia perlu berulang kali dan beransur-ansur beralih mengisih elemen ke belakang , menyediakan ruang sisipan untuk elemen terkini.

Kod pelaksanaan adalah seperti berikut:

function insertSort(arr) {
  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 1, len = arr.length; i < len; i ++) {
    var stand = arr[i];
    for (var j = i - 1; j >= 0; j --) {
      if (arr[j] > stand) {
        arr[j + 1] = arr[j];
      } else {
        arr[j + 1] = stand;
        break;
      }
    }
  }

  return arr;
}

Kerumitan masa ialah: O(n^2)

Sudah tentu, terdapat ruang untuk pengoptimuman algoritma ini, seperti menukar algoritma kedudukan carian dan penggantian kepada carian binari.
Isih gelembung

Algoritma pengisihan klasik, saya berasa patah hati apabila bercakap tentang isihan gelembung. Semasa saya seorang sarjana, saya menulis tesis yang diperlukan tentang penambahbaikan algoritma isihan gelembung Akibatnya, saya tidak dapat melaksanakan sepenuhnya algoritma isihan gelembung selepas saya selesai menulis tesis.

  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 0; i < len; i ++) {
    for (var j = 0; j < len - i - 1; j ++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = tmp;
      }
    }
  }

  return arr;
}

Kerumitan masa ialah: O(n^2)
Isih Pantas

Algoritma pengisihan yang sangat klasik Proses pengisihan terbahagi terutamanya kepada tiga langkah:

1. Pilih elemen daripada jujukan, dipanggil "pangsi"
2. Susun semula jujukan supaya semua elemen yang lebih kecil daripada nilai garis dasar diletakkan di hadapan garis dasar, dan semua elemen yang lebih besar daripada nilai garis dasar diletakkan di belakang garis dasar (nombor yang sama boleh diletakkan pada kedua-dua sisi). Selepas partition ini keluar, pangkalan berada di tengah-tengah jujukan. Ini dipanggil operasi partition;
Susun subarray unsur yang lebih kecil daripada nilai asas dan subarray unsur yang lebih besar daripada nilai asas secara rekursif.

Kod pelaksanaan adalah seperti berikut:

function quickSort(arr, bt, ed) {
  if (bt < ed) {
    var pivot = findPartition(arr, bt, ed);
    quickSort(arr, bt, pivot - 1);
    quickSort(arr, pivot + 1, ed);
  }
}

function findPartition(arr, bt, ed) {
  var stand = arr[bt];

  while (bt < ed) {
    while (bt < ed && arr[ed] >= stand) {
      ed --;
    }
    if (bt < ed) {
      arr[bt ++] = arr[ed];
    }
    while (bt < ed && arr[bt] <= stand) {
      bt ++;
    }
    if (bt < ed) {
      arr[ed --] = arr[bt]; 
    }
  }

  arr[bt] = stand;
  return bt;
}

Kerumitan masa ialah: O(nlogn).

Gabung isihan

Ia juga merupakan algoritma pengisihan yang sangat klasik. Saya mengambil peluang mempelajari js untuk menyemak algoritma pengisihan klasik. Untuk idea tentang isihan gabungan, anda boleh rujuk blog saya: Isih Gabung. Saya hanya menulis pelaksanaan js di sini.

function mergeSort(arr, bt, ed) {
  if (bt < ed) {
    var mid = bt + parseInt((ed - bt) / 2);
    mergeSort(arr, bt, mid);
    mergeSort(arr, mid + 1, ed);
    mergeArray(arr, bt, mid, ed);    
  }
}

function mergeArray(arr, bt, mid, ed) {
  var mArr = [];
  var i = bt, j = mid + 1;
  while (i <= mid && j <= ed) {
    if (arr[i] <= arr[j]) {
      mArr.push(arr[i++]);
    } else {
      mArr.push(arr[j ++]);
    }
  }

  if (i <= mid) {
    mArr = mArr.concat(arr.slice(i, mid + 1));
  }

  if (j <= ed) {
    mArr = mArr.concat(arr.slice(j, ed + 1));
  }

  for (var h = 0; h < mArr.length; h ++) {
    arr[bt + h] = mArr[h];
  }
}

Terdapat satu lagi episod kecil semasa menulis isihan gabungan: js tidak dapat dibundarkan secara automatik, jadi saya kemudiannya menggunakan kaedah parseInt, yang sangat comel.