快捷導(dǎo)航

前端必須掌握的五種常用排序算法總結(jié)大全

更新時(shí)間：2024年10月24日 10:46:53 作者：子羽bro

前端開(kāi)發(fā)中掌握排序算法對(duì)于數(shù)據(jù)處理至關(guān)重要,本文介紹五種基本排序算法,冒泡排序、選擇排序、插入排序、快速排序和歸并排序,幫助開(kāi)發(fā)者選擇合適的方法優(yōu)化性能,需要的朋友可以參考下

前言

在前端開(kāi)發(fā)中，對(duì)數(shù)據(jù)進(jìn)行排序是一項(xiàng)基本且常見(jiàn)的任務(wù)。掌握排序算法不僅可以幫助我們更有效地處理數(shù)據(jù)，還能提升代碼的執(zhí)行效率。本文將介紹五種基礎(chǔ)且常用的排序算法：冒泡排序、選擇排序、插入排序、快速排序和歸并排序。通過(guò)理解這些算法的原理和邏輯，我們可以更好地選擇合適的排序方法來(lái)優(yōu)化應(yīng)用性能。

1. 冒泡排序（Bubble Sort）

冒泡排序是一種簡(jiǎn)單的排序算法，它重復(fù)地遍歷待排序的數(shù)列，一次比較兩個(gè)元素，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。遍歷數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。

原理和邏輯：

比較相鄰的兩個(gè)元素，如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
對(duì)每一對(duì)相鄰元素做同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)；
針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

代碼實(shí)現(xiàn)

// 1. 冒泡排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

const bubbleSort = (arr) => {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
  return arr;
};
console.log("bubbleSort:",bubbleSort(arr));
//bubbleSort: [1, 2, 3, 5, 6, 7, 8, 9]

2. 選擇排序（Selection Sort）

選擇排序是一種簡(jiǎn)單直觀的排序算法。它的工作原理是首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。

原理和邏輯：

從未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置；
再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾；
重復(fù)第二步，直到所有元素均排序完畢。

代碼實(shí)現(xiàn)

// 2. 選擇排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

const selectSort = (arr) => {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let maxIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j;
      }
    }
    let tmp = arr[i];
    arr[i] = arr[maxIndex];
    arr[maxIndex] = tmp;
  }
  return arr;
};
console.log("selectSort:",selectSort(arr));
//selectSort: [1, 2, 3, 5, 6, 7, 8, 9]

3. 插入排序（Insertion Sort）

插入排序的工作方式是通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。

原理和邏輯：

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

代碼實(shí)現(xiàn)

// 3. 插入排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

const insertSort = (arr) => {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let current = arr[i];
    let prev = i - 1;
    while (prev >= 0 && current < arr[prev]) {
      arr[prev + 1] = arr[prev];
      prev--;
    }
    arr[prev + 1] = current;
  }
  return arr;
};

console.log("insertSort:", insertSort(arr));
//insertSort: [1, 2, 3, 5, 6, 7, 8, 9]

4. 快速排序（Quick Sort）

快速排序是一種分而治之的算法，它通過(guò)一個(gè)基準(zhǔn)值將數(shù)據(jù)分為兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)要小，然后再遞歸地對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序。

原理和邏輯：

選擇一個(gè)基準(zhǔn)值，通常選擇第一個(gè)元素或者中間元素；
重新排序數(shù)組，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)組的中間位置；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)組和大于基準(zhǔn)值元素的子數(shù)組排序。

代碼實(shí)現(xiàn)

// 4. 快速排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

function quickSort(arr){
  if(arr.length <2 ) return arr
  let first = arr[0]
  let left = [], right=[]
  for(let i = 1 ; i <arr.length; i++){
    if(first > arr[i]){
      right.push(arr[i])
    }else{
      left.push(arr[i])
    }
  }
  return [...quickSort(left) , first , ...quickSort(right)]
} 

console.log('quickSort:',quickSort(arr));
//quickSort: [1, 2, 3, 5, 6, 7, 8, 9]

5. 歸并排序（Merge Sort）

歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。

原理和邏輯：

把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
對(duì)這兩個(gè)子序列分別采用歸并排序；
將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。

代碼實(shí)現(xiàn)

// 5. 歸并排序
let arr = [2, 5, 8, 1, 3, 9, 6, 7];

function mergeSort(arr) {
  if (arr.length < 2) return arr;
  let middle = Math.floor(arr.length / 2);
  let left = arr.slice(0, middle);
  let right = arr.slice(middle, arr.length);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(left.shift());
    }
  }
  // 這也可以采用 while
  if (left.length) {
    result.push(...left);
  }

  if (right.length) {
    result.push(...right);
  }
  return result;
}

console.log("mergeSort:", mergeSort(arr));
//mergeSort: [1, 2, 3, 5, 6, 7, 8, 9]