归并排序

介绍

归并排序是十大经典排序算法之一，它基于分治策略和递归思想。归并排序的时间复杂度是 O(nlogn)，其中 n 是待排序数组的长度。它具有稳定性和可并行化的特点，适用于各种规模的数据集。然而，归并排序需要额外的空间来存储辅助数组，空间复杂度为 O(n)。

基本步骤

1. 将待排序的数组分成两个子数组，每个子数组包含大约一半的元素。可以通过将数组分成两半来实现，直到无法再分割为止。
2. 对每个子数组递归地应用归并排序，直到子数组的长度为 1 或 0，即已经有序或为空。
3. 将两个有序的子数组合并为一个有序的数组。这一步称为”归并”。可以创建一个辅助数组来存储合并后的结果。从两个子数组的开头开始比较元素，将较小的元素放入辅助数组中，并移动相应的指针。重复这个过程，直到某个子数组的所有元素都被放入了辅助数组。然后将另一个子数组剩余的元素依次放入辅助数组。
4. 最后将辅助数组中的结果复制回原始数组的对应位置，完成排序。

js代码实现

function mergeSort(arr) {
    // 如果数组只有一个元素,则已经有序，无须排序
    if (arr.length <= 1) return arr;

    // 将数组分成左右两个子数组
    let mid = Math.floor((arr.length) / 2);
    let leftArr = arr.slice(0, mid)
    let rightArr = arr.slice(mid, arr.length)

    // 递归地对左右两半进行排序
    const leftSorted = mergeSort(leftArr);
    const rightSorted = mergeSort(rightArr);

    return merge(leftSorted, rightSorted);
}

// 合并左右两个有序数组
function merge(leftArr, rightArr) {
    const mergedArr = [];
    let p1 = 0, p2 = 0;
    while (p1 < leftArr.length && p2 < rightArr.length) {
        if (leftArr[p1] < rightArr[p2]) {
            mergedArr.push(leftArr[p1++]);
        } else {
            mergedArr.push(rightArr[p2++]);
        }
    }
    // 将剩余元素添加到合并后的数组中

    // 左边数组有剩余
    while (p1 < leftArr.length) {
        mergedArr.push(leftArr[p1++]);
    }
    // 右边数组有剩余
    while (p2 < rightArr.length) {
        mergedArr.push(rightArr[p2++]);
    }

    return mergedArr
}

const arr = [8, 3, 1, 5, 2, 9, 4, 7, 6];

console.log(mergeSort(arr));

go代码实现

package main

import "fmt"

func merge(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	mid := len(arr) / 2

	return mergeArray(merge(arr[:mid]), merge(arr[mid:]))
}

func mergeArray(leftArr, rightArr []int) []int {
	var mergedArr []int
	p1 := 0
	p2 := 0

	for p1 < len(leftArr) && p2 < len(rightArr) {
		if leftArr[p1] < rightArr[p2] {
			mergedArr = append(mergedArr, leftArr[p1])
			p1++
		} else {
			mergedArr = append(mergedArr, rightArr[p2])
			p2++
		}
	}

	for p1 < len(leftArr) {
		mergedArr = append(mergedArr, leftArr[p1])
		p1++
	}

	for p2 < len(rightArr) {
		mergedArr = append(mergedArr, rightArr[p2])
		p2++
	}
	return mergedArr
}

func main() {
	arr := []int{8, 3, 1, 5, 2, 9, 4, 7, 6}

	fmt.Println(merge(arr))
}