快捷導(dǎo)航

詳解js中常用4個(gè)基礎(chǔ)算法

更新時(shí)間：2023年05月25日 12:09:51 作者：逆風(fēng)起飛

本文主要介紹了JS中常用的四個(gè)基礎(chǔ)算法，主要介紹了冒泡排序，選擇排序，插入排序和快速排序這四種算法,需要的朋友可以參考下

冒泡排序

原理

相鄰兩個(gè)數(shù)據(jù)的按條件交換排序，然后遍歷式的交換排序。
何為冒泡？每次遍歷為一次 冒泡，一次遍歷完成，冒泡結(jié)束至少會(huì)讓一個(gè)元素移動(dòng)到正確的位置。
列：

const arr = [3, 2, 1];
// 第1次冒泡后[2, 1，3] 3移動(dòng)到正確位置
// 第2次冒泡后[1，2，3] 2移動(dòng)到正確位置

它排序需要兩次循環(huán)來(lái)設(shè)計(jì)：
第一層循環(huán)控制排序arr.length - 1次
第二層循環(huán)負(fù)責(zé)每次交換遍歷數(shù)據(jù)的相鄰數(shù)據(jù)交換, 共arr.length - 1 - i次，i第一層循環(huán) 已循環(huán)次數(shù)。

代碼

export const mySort = arr => {
  for (let i = 0; i < arr.length - 1; i++) {
    // 控制循環(huán)次數(shù)
    for (let j = 0; j < arr.length - i - 1; j++) {
      // 數(shù)據(jù)交換
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
};

實(shí)現(xiàn)array.sort:

export const mySort = (arr, fn) => {
  for (let i = 0; i < arr.length - 1; i++) {
    // 控制循環(huán)次數(shù)
    for (let j = 0; j < arr.length - i - 1; j++) {
      // 數(shù)據(jù)交換
      if (fn(arr[j], arr[j + 1])) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
};
mySort([1, 5, 3, 8, 2, 4], (a, b) => a > b); // ?[1, 2, 3, 4, 5, 8]
mySort([1, 5, 3, 8, 2, 4], (a, b) => a < b); // [8, 5, 4, 3, 2, 1]

選擇排序

原理

對(duì)數(shù)組遍歷后選取符合條件（最大或最?。┑臄?shù)，與數(shù)組對(duì)應(yīng)位置的數(shù)進(jìn)行交換。
何為選擇？每次遍歷為一次 選擇，一次遍歷完成結(jié)束會(huì)得出一個(gè)符合條件的元素并交換位置。
列：

const arr = [3, 2, 1];
// 第1次選擇后[1, 2，3] 1與3交換位置
// 第2次選擇后[1, 2，3]

它與冒泡排序不同的是它不會(huì)頻繁的發(fā)生交換，第一層循環(huán)結(jié)束后，看條件是否滿足需要交換。
它排序需要兩次循環(huán)來(lái)設(shè)計(jì)：
第一層循環(huán)控制排序arr.length - 1次
第二層循環(huán)負(fù)責(zé)找出交換下標(biāo)index, j = ij前面已排好。

代碼

export const mySort = (arr, fn) => {
  for (let i = 0; i < arr.length - 1; i++) {
    // 控制循環(huán)次數(shù)
    let index = i;
    for (let j = i; j < arr.length; j++) {
      // 找出下標(biāo)
      if (fn(arr[j], arr[index])) {
        index = j;
      }
    }
    // 交換數(shù)據(jù)
    if (index !== i) {
      const copy = arr[index];
      arr[index] = arr[i];
      arr[i] = copy;
    }
  }
  return arr;
};
mySort([9, 5, 3, 4], (a, b) => a > b); // [9, 5, 4, 3]

插入排序

原理

以下內(nèi)容來(lái)自參考文章：@插入排序通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。
一般來(lái)說(shuō)，插入排序都采用 in-place 在數(shù)組上實(shí)現(xiàn)：

從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
如果該元素（已排序）大于新元素，將該元素移到下一位置；
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
將新元素插入到該位置后；
重復(fù)步驟2~5。

動(dòng)圖展示

代碼

const insertion = arr => {
  const len = arr.length;
  let preIndex;
  let current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && current < arr[preIndex]) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
};
insertion([3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37]);
// ?[0, 1, 3, 4, 5, 7, 8, 9, 12, 25, 37, 42, 56, 78]

快速排序

原理

快速排序使用分治法策略來(lái)把一個(gè)數(shù)組分為兩個(gè)數(shù)組，再重復(fù)把這兩個(gè)數(shù)組變成四個(gè)，直至length <= 1。思路：

從數(shù)組中挑出一個(gè)元素，稱為 "基準(zhǔn)"。
重新排序數(shù)組，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面(left)，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面(right),相同的數(shù)可以到任一邊。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)操作。
遞歸地把小于基準(zhǔn)值元素的數(shù)組和大于基準(zhǔn)值元素的數(shù)組排序，重復(fù)1～2。

代碼

const quickSort = arr => {
  const len = arr.length;
  if (len <= 1) return arr;
  // 基準(zhǔn)
  const num = arr[0];
  // 左右分區(qū)
  const left = [];
  const right = [];
  for (let index = 1; index < arr.length; index++) {
    arr[index] <= num ? left.push(arr[index]) : right.push(arr[index]);
  }
  // 遞歸
  return quickSort(left).concat([num], quickSort(right));
};
console.log(quickSort([3, 2, 6, 8, 99, 2, 3]));//?[2, 2, 3, 3, 6, 8, 99]

以上就是詳解js中常用4個(gè)基礎(chǔ)算法的詳細(xì)內(nèi)容，更多關(guān)于js基礎(chǔ)算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: