快速排序 --- 2024-07-04

package main

import (
    "fmt"
)

// merge 合并两个有序数组
func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0

    // 合并两个有序数组
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    // 追加剩余的元素
    for i < len(left) {
        result = append(result, left[i])
        i++
    }
    for j < len(right) {
        result = append(result, right[j])
        j++
    }

    return result
}

// mergeSort 递归排序
func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    // 找到中间点
    mid := len(arr) / 2

    // 递归排序左右两半
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])

    // 合并已排序的两半
    return merge(left, right)
}

func main() {
    arr := []int{10, 7, 8, 9, 1, 5}
    fmt.Println("原数组:", arr)
    sortedArr := mergeSort(arr)
    fmt.Println("排序后的数组:", sortedArr)
}

代码说明：
merge 函数：用于合并两个有序数组。通过比较两个数组的元素，将较小的元素追加到结果数组中，直到一个数组为空。然后，将剩余的元素追加到结果数组中。

mergeSort 函数：递归排序函数。如果数组长度小于等于1，则返回该数组。否则，将数组分成两半，分别对两半进行递归排序，然后合并排序结果。

main 函数：定义一个待排序的数组 arr，调用 mergeSort 函数进行排序，最后打印排序前和排序后的数组。

归并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)，适用于需要稳定排序且对空间复杂度要求不高的场景。