javascript中排序算法的詳細介紹

這篇文章給大家分享的是有關(guān)javascript中排序算法的詳細介紹的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

排序算法是面試中的高頻考察點，我們需要熟練掌握。本文整理了最經(jīng)典、最常用的排序算法并且搭配了動圖和視頻，希望能夠幫助你更加輕松的拿下它們。

首先，根據(jù)排序算法的特性可以分成如下兩類：

• 比較類排序

• 非比較類排序

顧名思義，比較類排序是通過元素間的比較進行排序的，非比較類則不涉及元素之間的比較操作。

比較類排序的時間復(fù)雜度不能突破 O(nlogn)，也被稱為非線性排序。

非比較類排序的時間復(fù)雜度可以突破 O(nlogn)，能夠以線性的時間運行，也被稱為線性排序。

如果你還不了解時間復(fù)雜度的話，可以移步我的這篇專欄JavaScript算法時間、空間復(fù)雜度分析。

01 冒泡排序 Bubble Sort

冒泡排序，簡單粗暴，一句話解釋:

冒泡排序在每次冒泡操作時會比較相鄰的兩個元素，看是否滿足大小關(guān)系要求，不滿足就將它倆互換。一直迭代到不再需要交換，也就是排序完成。

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

• 時間復(fù)雜度: O(n^2)

• 空間復(fù)雜度: O(1)

• 穩(wěn)定

注意：這里的穩(wěn)定是指，冒泡排序是穩(wěn)定的排序算法。

什么是穩(wěn)定的排序算法呢？

排序算法的穩(wěn)定性

僅僅用執(zhí)行效率和內(nèi)存消耗來判斷排序算法的優(yōu)劣是不夠的，針對排序算法，還有一個重要的度量指標(biāo)，穩(wěn)定性。

意思是說，如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。

舉個：

比如我們有一組數(shù)據(jù)：1，9，2，5，8，9。按照大小排序之后就是 1，2，5，8，9，9。

這組數(shù)據(jù)中有兩個 9，經(jīng)過某種排序算法排序后，如果兩個 9 的前后順序沒有改變，我們就把這種排序算法稱為 穩(wěn)定的排序算法。
否則，就是不穩(wěn)定的排序算法。

冒泡排序優(yōu)化

上面的代碼還可以進行優(yōu)化，當(dāng)某次冒泡操作已經(jīng)沒有數(shù)據(jù)交換時，說明已經(jīng)達到完全有序，不需要再繼續(xù)執(zhí)行后續(xù)的冒泡操作了。

const bubbleSort = function(arr) {
  const len = arr.length
  let flag = false
  if (len < 2) return arr
  for (let i = 0; i < len; i++) {
      flag = false // 提前退出冒泡循環(huán)的標(biāo)志
      for (let j = 0; j < len - i - 1; j++) {
          if (arr[j] > arr[j + 1]) {
              const temp = arr[j]
              arr[j] = arr[j + 1]
              arr[j + 1] = temp
              flag = true // 表示有數(shù)據(jù)交換
          }
      }
      if (!flag) break // 沒有數(shù)據(jù)交換，提前退出
  }
  return arr
}

02 插入排序 Insertion Sort

插入排序顧名思義，對于未排序的數(shù)據(jù)，在已排序的序列中從后往前掃描，找到相應(yīng)的位置進行插入，保持已排序序列中元素一直有序。

從 i 等于 1 開始遍歷，拿到當(dāng)前元素 curr，與前面的元素進行比較。

如果前面的元素大于當(dāng)前元素，就把前面的元素和當(dāng)前元素進行交換，不斷循環(huán)直到未排序序列中元素為空，排序完成。

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

• 時間復(fù)雜度: O(n^2)

• 空間復(fù)雜度: O(1)

• 穩(wěn)定

03 選擇排序 Selection Sort

選擇排序可視化視頻：

https://www.reddit.com/r/programming/comments/e5md13/selection_sort_visualization/

選擇排序和插入排序有些類似，也分已排序序列和未排序序列。

但是選擇排序是將最小的元素存放在數(shù)組起始位置，再從剩下的未排序的序列中尋找最小的元素，然后將其放到已排序的序列后面。以此類推，直到排序完成。

const selectSort = function(arr) {
    const len = arr.length
    let temp, minIndex
    for (let i = 0; i < len - 1; i++) {
        minIndex = i
        for (let j = i + 1; j < len; j++) {
            if (arr[j] <= arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = temp
    }
    return arr
}

• 時間復(fù)雜度: O(n^2)

• 空間復(fù)雜度: O(1)

• 不穩(wěn)定

04 歸并排序 Merge Sort

分治法典型應(yīng)用，分治算法思想很大程度上是基于遞歸的，也比較適合用遞歸來實現(xiàn)。

處理過程是由下到上的，先處理子問題，然后再合并。

如果感覺自己對遞歸掌握的還不是很透徹的同學(xué)，可以移步我的這篇專欄你真的懂遞歸嗎？。

顧名思義，分而治之。一般分為以下三個過程：

• 分解：將原問題分解成一系列子問題。

• 解決：遞歸求解各個子問題，若子問題足夠小，則直接求解。

• 合并：將子問題的結(jié)果合并成原問題。

歸并排序就是將待排序數(shù)組不斷二分為規(guī)模更小的子問題處理，再將處理好的子問題合并起來，這樣整個數(shù)組就都有序了。

const mergeSort = function(arr) {
    const merge = (right, left) => {
    const result = []
    let i = 0, j = 0
    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        result.push(left[i++])
      } else {
        result.push(right[j++])
      }
    }
    while (i < left.length) {
      result.push(left[i++])
    }
    while (j < right.length) {
      result.push(right[j++])
    }
    return result
    }
    const sort = (arr) => {
        if (arr.length === 1) { return arr }
        const mid = Math.floor(arr.length / 2)
        const left = arr.slice(0, mid)
        const right = arr.slice(mid, arr.length)
        return merge(mergeSort(left), mergeSort(right))
    }
    return sort(arr)
}

• 時間復(fù)雜度: O(nlogn)

• 空間復(fù)雜度: O(n)

• 穩(wěn)定

05 快速排序 Quick Sort

快速排序可視化視頻：

https://www.reddit.com/r/dataisbeautiful/comments/e9fb2k/oc_quicksort_visualization/

快速排序也是分治法的應(yīng)用，處理過程是由上到下的，先分區(qū)，然后再處理子問題。

快速排序通過遍歷數(shù)組，將待排序元素分隔成獨立的兩部分，一部分記錄的元素均比另一部分的元素小，則可以分別對這兩部分記錄的元素繼續(xù)進行排序，直到排序完成。

這就需要從數(shù)組中挑選出一個元素作為 基準(zhǔn)(pivot)，然后重新排序數(shù)列，將元素比基準(zhǔn)值小的放到基準(zhǔn)前面，比基準(zhǔn)值大的放到基準(zhǔn)后面。

然后將小于基準(zhǔn)值的子數(shù)組(left)和大于基準(zhǔn)值的子數(shù)組(right)遞歸地調(diào)用 quick 方法，直到排序完成。

const quickSort = function(arr) {
    const quick = function(arr) {
        if (arr.length <= 1) return arr
        const len = arr.length
        const index = Math.floor(len >> 1)
        const pivot = arr.splice(index, 1)[0]
        const left = []
        const right = []
        for (let i = 0; i < len; i++) {
            if (arr[i] > pivot) {
                right.push(arr[i])
            } else if (arr[i] <= pivot) {
                left.push(arr[i])
            }
        }
        return quick(left).concat([pivot], quick(right))
    }
    const result = quick(arr)
    return result
}

• 時間復(fù)雜度: O(nlogn)

• 空間復(fù)雜度: O(nlogn)

• 不穩(wěn)定

06 堆排序 Heap Sort

堆排序相比其他幾種排序代碼會有些復(fù)雜，不過沒關(guān)系，我們先來看一些前置知識，可以幫助我們更好的理解堆排序。

堆排序顧名思義就是要利用堆這種數(shù)據(jù)結(jié)構(gòu)進行排序。堆是一種特殊的樹，滿足以下兩點就是堆：

• 堆是一個完全二叉樹

• 堆中每一個節(jié)點的值都必須大于等于(或小于等于)其子樹中的每個節(jié)點的值

每個節(jié)點的值都大于等于子樹中每個節(jié)點值的堆，叫做大頂堆，每個節(jié)點的值都小于等于子樹中每個節(jié)點值的堆，叫做小頂堆。

也就是說，大頂堆中，根節(jié)點是堆中最大的元素。小頂堆中，根節(jié)點是堆中最小的元素。

如果你對樹這種數(shù)據(jù)結(jié)構(gòu)還不是很了解，可以移步我的這篇專欄“樹”業(yè)有專攻

堆如果用一個數(shù)組表示的話，給定一個節(jié)點的下標(biāo) i (i從1開始)，那么它的父節(jié)點一定為 A[i / 2]，左子節(jié)點為 A[2i]，右子節(jié)點為 A[2i + 1]。

堆排序包含兩個過程，建堆和排序。首先構(gòu)建一個大頂堆，也就是將最大值存儲在根節(jié)點(i = 1)，每次取大頂堆的根節(jié)點與堆的最后一個節(jié)點進行交換，此時最大值放入了有效序列的最后一位，并且有效序列減 1，有效堆依然保持完全二叉樹的結(jié)構(gòu)，然后進行堆化成為新的大頂堆。重復(fù)此操作，直到有效堆的長度為 0，排序完成。

const heapSort = function(arr) {
    buildHeap(arr, arr.length - 1)
    let heapSize = arr.length - 1 // 初始化堆的有效序列長度
    for (let i = arr.length - 1; i > 1; i--) {
        swap(arr, 1, i) // 交換堆頂元素與最后一個有效子元素
        heapSize-- // 有效序列長度減 1
        heapify(arr, heapSize, 1) // 堆化有效序列
    }
    return arr
}

// 構(gòu)建大頂堆
const buildHeap = function(items, heapSize) {
    // 從后往前并不是從序列的最后一個元素開始，而是從最后一個非葉子節(jié)點開始，這是因為，葉子節(jié)點沒有子節(jié)點，不需要自上而下式堆化。
    // 最后一個子節(jié)點的父節(jié)點為 n/2 ，所以從 n/2 位置節(jié)點開始堆化
    for (let i = Math.floor(heapSize / 2); i >= 1; i--) {
        heapify(items, heapSize, i)
    }
}
// 堆化
const heapify = function(arr, heapSize, i) {
    while (true) {
        let maxIndex = i
        if (2 * i <= heapSize && arr[i] < arr[i * 2]) {
            maxIndex = i * 2
        }
        if (2 * i + 1 <= heapSize && arr[maxIndex] < arr[i * 2 + 1]) {
            maxIndex = i * 2 + 1
        }
        if (maxIndex === i) break
        swap(arr, i, maxIndex)
        i = maxIndex
    }
}

// 交換工具函數(shù)
const swap = function(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

• 時間復(fù)雜度: O(nlogn)

• 空間復(fù)雜度: O(1)

• 不穩(wěn)定

為了方便你理解和記憶，我將這 6 種排序算法的復(fù)雜度和穩(wěn)定性匯總成表格如下：

感謝各位的閱讀！關(guān)于“javascript中排序算法的詳細介紹”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！