JavaScript 알고리즘 병합 정렬 알고리즘(자세한 설명)

이 기사에서는 병합 정렬의 논리를 배우고 이를 JavaScript로 구현합니다. 마지막으로 병합 정렬은 공간 및 시간 복잡도 측면에서 다른 알고리즘과 비교됩니다.

병합 정렬의 논리

병합 정렬은분할 및 정복개념을 사용하여 주어진 요소 목록을 정렬합니다. 문제가 직접 해결될 수 있을 만큼 단순해질 때까지 문제를 더 작은 하위 문제로 나눕니다.

다음은 병합 정렬 단계입니다.

1. 주어진 목록을 두 부분으로 나눕니다(목록의 요소 수가 홀수인 경우 대략 동일하게 만듭니다).

2. 단일 요소 배열만 남을 때까지 동일한 방식으로 하위 배열을 계속 나눕니다.

3. 단일 요소 배열에서 시작하여 병합된 각 하위 배열을 정렬하기 위해 하위 배열을merge합니다.

4. 최종적으로 정렬된 배열을 얻을 때까지 3단계를 반복하세요.

[4, 8, 7, 2, 11, 1, 3]배열을 예로 들어 병합 정렬이 어떻게 작동하는지 살펴보겠습니다.[4, 8, 7, 2, 11, 1, 3]为例，让我们看一下归并排序是如何工作的：

用 JavaScript 实现归并排序

首先实现一个将两个已排序子数组合并为一个已排序数组的函数merge()。要注意着两个子数组是已经被排好序的，这一点非常重要，merge()函数只用于其进行合并。【推荐教程：《JavaScript视频教程》】

可以通过遍历这两个子数组来实现：

function merge(left, right) { let arr = [] // 如果任何一个数组为空，就退出循环 while (left.length && right.length) { // 从左右子数组的最小元素中选择较小的元素 if (left[0] < right[0]) { arr.push(left.shift()) } else { arr.push(right.shift()) } } // 连接剩余的元素，防止没有把两个数组遍历完整 return [ ...arr, ...left, ...right ] }

在这个函数中，通过把两个排好序的子数组（left、right）合并来获得一个排好序的大数组。首先，创建一个空数组。之后在left和right两个子数组中最小元素中的较小的一个，并将其添加到空数组。我们只需要检查left和right子数组中的第一个元素，因为它们是已排好序的。

在这个过程中，从子数组中删除了被选择的元素（通过shift()函数实现）。继续这个过程，直到其中一个子数组变为空。最后把非空子数组的剩余元素（因为它们已经被排序）插入主数组的最后面。

现在有了合并两个已排序数组的代码，接下来为实现归并排序算法的最终代码。这意味着要继续分割数组，直到最终只包含一个元素的数组为止：

function mergeSort(array) { const half = array.length / 2 if(array.length < 2){ return array } const left = array.splice(0, half) return merge(mergeSort(left),mergeSort(array)) }

在代码中先确定中点，并用splice()函数将数组分为两个子数组。如果元素数量为奇数，则左侧的元素数量会少一个。不断的划分数组，直到剩下单个元素的数组（array.length < 2）。然后用之前实现的merge()

array = [4, 8, 7, 2, 11, 1, 3]; console.log(mergeSort(array));

1,2,3,4,7,8,11