前端面試之6種經典排序演算法的實現，你會幾種？ （ 附動圖+影片）

本篇文章為大家整理分享6種經典排序演算法的實作方法。有一定的參考價值，有需要的朋友可以參考一下，希望對大家有幫助。

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

首先，根據排序演算法的特性可以分成以下兩類：

• 比較類別排序
• #非比較類別排序

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

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

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

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

01 冒泡排序Bubble Sort

冒泡排序視覺化影片：

https://www.reddit.com/r /programming/comments/e55j0i/bubble_sort_visualization/

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

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

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
}

• 時間複雜度: O(n^2)
• 空間複雜度: O(1)

注意：這裡的穩定是指，冒泡排序是穩定的排序演算法。

什麼是穩定的排序演算法呢？

排序演算法的穩定性

僅僅用執行效率和記憶體消耗來判斷排序演算法的優劣是不夠的，針對排序演算法，還有一個重要的度量指標，穩定性。

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

舉個：

例如我們有一組資料：1，9，2，5，8，9。依大小排序之後就是 1，2，5，8，9，9。

這組資料中有兩個9，經過某種排序演算法排序後，如果兩個9 的前後順序沒有改變，我們就把這種排序演算法稱為穩定的排序演算法。
否則，就是不穩定的排序演算法。

冒泡排序最佳化

上面的程式碼還可以進行最佳化，當某次冒泡操作已經沒有資料交換時，表示已經達到完全有序，不需要再繼續執行後續的冒泡操作了。

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 // 提前退出冒泡循环的标志
      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 // 表示有数据交换
          }
      }
      if (!flag) break // 没有数据交换，提前退出
  }
  return arr
}

02 插入排序Insertion Sort

#插入排序顧名思義，對於未排序的數據，在已排序的序列中從後往前掃描，找到對應的位置進行插入，保持已排序序列中元素一直有序。

從 i 等於 1 開始遍歷，拿到目前元素 curr，與前面的元素進行比較。

如果前面的元素大於目前元素，就把前面的元素和目前元素交換，不斷循環直到未排序序列中元素為空，排序完成。

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
}

• 時間複雜度: O(n^2)
• 空間複雜度: O(1)

03 選擇排序Selection Sort

選擇排序視覺化影片：

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

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

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

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
}

• 時間複雜度: O(n^2)
• 空間複雜度: O(1)
• 不穩定性

#04 歸併排序Merge Sort

分治法典型應用，分治演算法思想很大程度上是基於遞歸的，也比較適合用遞迴來實現。

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

如果感觉自己对递归掌握的还不是很透彻的同学，可以移步我的这篇专栏你真的懂递归吗？。

顾名思义，分而治之。一般分为以下三个过程：

• 分解：将原问题分解成一系列子问题。

• 解决：递归求解各个子问题，若子问题足够小，则直接求解。

• 合并：将子问题的结果合并成原问题。

归并排序就是将待排序数组不断二分为规模更小的子问题处理，再将处理好的子问题合并起来，这样整个数组就都有序了。

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)
}

• 时间复杂度: O(nlogn)
• 空间复杂度: O(n)
• 稳定

05 快速排序 Quick Sort

快速排序可视化视频：

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

快速排序也是分治法的应用，处理过程是由上到下的，先分区，然后再处理子问题。

快速排序通过遍历数组，将待排序元素分隔成独立的两部分，一部分记录的元素均比另一部分的元素小，则可以分别对这两部分记录的元素继续进行排序，直到排序完成。

这就需要从数组中挑选出一个元素作为 基准(pivot)，然后重新排序数列，将元素比基准值小的放到基准前面，比基准值大的放到基准后面。

然后将小于基准值的子数组(left)和大于基准值的子数组(right)递归地调用 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
}

• 时间复杂度: O(nlogn)
• 空间复杂度: O(nlogn)
• 不稳定

06 堆排序 Heap Sort

堆排序相比其他几种排序代码会有些复杂，不过没关系，我们先来看一些前置知识，可以帮助我们更好的理解堆排序。

堆排序顾名思义就是要利用堆这种数据结构进行排序。堆是一种特殊的树，满足以下两点就是堆：

• 堆是一个完全二叉树

• 堆中每一个节点的值都必须大于等于(或小于等于)其子树中的每个节点的值

每个节点的值都大于等于子树中每个节点值的堆，叫做大顶堆，每个节点的值都小于等于子树中每个节点值的堆，叫做小顶堆。

也就是说，大顶堆中，根节点是堆中最大的元素。小顶堆中，根节点是堆中最小的元素。

如果你对树这种数据结构还不是很了解，可以移步我的这篇专栏“树”业有专攻

堆如果用一个数组表示的话，给定一个节点的下标 i (i从1开始)，那么它的父节点一定为 A[i / 2]，左子节点为 A[2i]，右子节点为 A[2i + 1]。

堆排序包含两个过程，建堆和排序。首先构建一个大顶堆，也就是将最大值存储在根节点(i = 1)，每次取大顶堆的根节点与堆的最后一个节点进行交换，此时最大值放入了有效序列的最后一位，并且有效序列减 1，有效堆依然保持完全二叉树的结构，然后进行堆化成为新的大顶堆。重复此操作，直到有效堆的长度为 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
}

// 构建大顶堆
const buildHeap = function(items, heapSize) {
    // 从后往前并不是从序列的最后一个元素开始，而是从最后一个非叶子节点开始，这是因为，叶子节点没有子节点，不需要自上而下式堆化。
    // 最后一个子节点的父节点为 n/2 ，所以从 n/2 位置节点开始堆化
    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
    }
}

// 交换工具函数
const swap = function(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

• 时间复杂度: O(nlogn)
• 空间复杂度: O(1)
• 不稳定

为了方便你理解和记忆，我将这 6 种排序算法的复杂度和稳定性汇总成表格如下：

本文讲解了十大经典排序算法中的 6 种排序算法，这 6 种排序算法是平时开发中比较常见的，大家务必要熟练掌握。

更多编程相关知识，请访问：编程视频！！

以上是前端面試之6種經典排序演算法的實現，你會幾種？ （ 附動圖+影片）的詳細內容。更多資訊請關注PHP中文網其他相關文章！