프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)-JS 튜토리얼-php.cn

이 글에서는 6가지 고전적인 정렬 알고리즘의 구현 방법을 정리하고 공유할 것입니다. 도움이 필요한 친구들이 모두 참고할 수 있기를 바랍니다.

프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

정렬 알고리즘은 면접에서 자주 나오는 점검 포인트인데, 이에 능숙해야 합니다. 이 기사에서는 가장 고전적이고 일반적으로 사용되는 정렬 알고리즘을 편집하고 이를 애니메이션 및 비디오와 결합하여 더 쉽게 얻을 수 있도록 도움을 드리고자 합니다.

먼저 정렬 알고리즘의 특성에 따라 다음 두 가지로 나눌 수 있습니다.

프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

비교 정렬
비비교 정렬

이름에서 알 수 있듯이 > 비교 정렬은 요소 간의 비교를 통해 정렬하는 것이며, 비비교 클래스에는 요소 간의 비교 작업이 포함되지 않습니다. 比较类排序是通过元素间的比较进行排序的，非比较类则不涉及元素之间的比较操作。

比较类排序的时间复杂度不能突破 O(nlogn)，也被称为非线性排序。

非比较类排序的时间复杂度可以突破 O(nlogn)，能够以线性的时间运行，也被称为线性排序。

프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

如果你还不了解时间复杂度的话，可以移步我的这篇专栏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

프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

插入排序顾名思义，对于未排序的数据，在已排序的序列中从后往前扫描，找到相应的位置进行插入，保持已排序序列中元素一直有序。

从 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

프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

分治法典型应用，分治算法思想很大程度上是基于递归的，也比较适合用递归来实现。

处理过程是由下到上的，先处理子问题，然后再合并。

비교 정렬의 시간 복잡도는 O(nlogn)을 초과할 수 없습니다. 이를 비선형 정렬이라고도 합니다. 🎜🎜비비교 정렬의 시간 복잡도는 O(nlogn)을 초과할 수 있으며 선형 정렬이라고도 하는 선형 시간으로 실행될 수 있습니다. 🎜🎜 프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

🎜🎜아직 시간 복잡도를 이해하지 못했다면 내 칼럼의 JavaScript 알고리즘 시간 및 공간 복잡도 분석으로 이동하면 됩니다. 🎜

01 버블 정렬

🎜버블 정렬 시각화 동영상: 🎜🎜https://www.reddit.com/r/programming/comments/e55j0i /bubble_sort_visualization/🎜

🎜버블 정렬, 간단하고 조잡한, 한 문장으로 설명:🎜🎜버블 정렬은 각 버블 작업 중에 인접한 두 요소를 비교하여 크기 관계 요구 사항이 충족되는지, 그렇지 않은 경우, 그들은 교환될 것이다. 더 이상 교환이 필요하지 않을 때까지, 즉 정렬이 완료될 때까지 반복합니다. 🎜

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(n^2)🎜🎜공간 복잡도: O(1)🎜🎜Stable🎜🎜🎜참고: 여기서 안정은 버블 정렬이 안정적인 정렬 알고리즘임을 의미합니다. 🎜🎜안정적인 정렬 알고리즘이란 무엇인가요? 🎜

정렬 알고리즘의 안정성

🎜정렬 알고리즘의 품질을 판단하려면 실행 효율성과 메모리 소비만 사용하세요. . 이것이 충분하지 않다면 정렬 알고리즘에 대한 또 다른 중요한 지표인 안정성이 있습니다. 🎜🎜

정렬할 순서에 동일한 값을 갖는 요소가 있으면 정렬 후에도 동일한 요소 간의 원래 순서는 변경되지 않는다는 의미입니다.

🎜🎜예: 🎜

예를 들어 1, 9, 2, 5, 8, 9라는 데이터 세트가 있습니다. 사이즈별로 정렬해 보면 1, 2, 5, 8, 9, 9 입니다.

🎜이 데이터 집합에는 두 개의 9가 있으며 특정 정렬 알고리즘에 의해 정렬된 후 두 개의 9의 순서가 변경되지 않으면 이 정렬 알고리즘을 안정 정렬 알고리즘</ 코드라고 합니다. >. 🎜그렇지 않으면 <code>불안정한 정렬 알고리즘입니다. 🎜

버블 정렬 최적화

🎜위 코드도 최적화할 수 있습니다. 특정 버블 작업에 데이터 교환이 없음이 있으면 도달했음을 의미합니다. 완전히 정렬되었으므로 후속 버블링 작업을 계속 수행할 필요가 없습니다. 🎜

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
}

로그인 후 복사

02 삽입 정렬

🎜

🎜🎜이름에서 알 수 있듯이 정렬되지 않은 데이터에 대해 Scanforward에서 정렬된 순서로 삽입 정렬합니다. 정렬된 순서의 요소를 순서대로 유지하면서 삽입할 해당 위치를 찾습니다. 🎜🎜i가 1인 것부터 탐색을 시작하고 현재 요소 curr를 가져와서 이전 요소와 비교합니다. 🎜🎜이전 요소가 현재 요소보다 큰 경우 이전 요소를 현재 요소로 바꾸고 정렬되지 않은 시퀀스의 요소가 비어 있고 정렬이 완료될 때까지 계속 반복합니다. 🎜

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(n^2)🎜🎜공간 복잡도: O(1)🎜🎜Stable🎜🎜

03 선택 정렬

🎜선택 정렬 시각화 영상: 🎜🎜https://www.reddit.com/r/programming/comments/e5md13/selection_sort_visualization/🎜

🎜선택 정렬과 삽입 정렬은 다소 비슷하며 정렬된 시퀀스와 정렬되지 않은 정렬로도 나뉩니다. 시퀀스 정렬 순서. 🎜🎜하지만 선택 정렬은

배열의 시작 부분에 가장 작은 요소를 저장한 다음 정렬되지 않은 나머지 시퀀스에서 가장 작은 요소를 찾아 정렬된 시퀀스 뒤에 배치

하는 것입니다. 정렬이 완료될 때까지 계속됩니다. 🎜rrreee🎜🎜시간 복잡도: O(n^2)🎜🎜공간 복잡도: O(1)🎜🎜Unstable🎜🎜

04 병합 정렬

🎜

🎜🎜분할 정복 알고리즘의 대표적인 응용 방식은 분할 정복 알고리즘의 아이디어가 크게 재귀에 기반을 두고 있으며, 재귀를 사용하여 구현하는 것이 더 적합합니다. 🎜🎜처리 프로세스는 아래에서 위로, 하위 문제를 먼저 처리한 다음 병합합니다. 🎜

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

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

分解：将原问题分解成一系列子问题。
解决：递归求解各个子问题，若子问题足够小，则直接求解。
合并：将子问题的结果合并成原问题。

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

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

프론트엔드 인터뷰: 6가지 고전적인 정렬 알고리즘 구현, 얼마나 알고 계시나요? (첨부된 애니메이션 + 영상)

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

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

堆是一个完全二叉树
堆中每一个节点的值都必须大于等于(或小于等于)其子树中的每个节点的值

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

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

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

堆如果用一个数组表示的话，给定一个节点的下标 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
}

로그인 후 복사