快速排序

package main

import (
    "fmt"
)

func main() {
    arr := []int{12, 4, 5, 6, 7, 3, 1, 15}
    fmt.Println("原始数组:", arr)

    mergeSort(arr)

    fmt.Println("排序后数组:", arr)
}

// mergeSort 使用双路归并快速排序算法对切片进行排序
func mergeSort(arr []int) {
    // 创建一个临时数组用于归并过程
    tmp := make([]int, len(arr))
    sort(arr, tmp, 0, len(arr)-1)
}

// sort 是递归调用的归并排序函数
func sort(arr, tmp []int, left, right int) {
    if left < right {
        // 计算中间位置
        mid := (left + right) / 2

        // 对左半部分进行递归排序
        sort(arr, tmp, left, mid)

        // 对右半部分进行递归排序
        sort(arr, tmp, mid+1, right)

        // 合并左右两部分
        merge(arr, tmp, left, mid, right)
    }
}

// merge 用于归并两个有序的部分
func merge(arr, tmp []int, left, mid, right int) {
    i := left    // 左半部分的起始位置
    j := mid + 1 // 右半部分的起始位置
    k := left    // 归并后的位置

    // 归并过程，将两部分按顺序合并到临时数组 tmp 中
    for i <= mid && j <= right {
        if arr[i] <= arr[j] {
            tmp[k] = arr[i]
            i++
        } else {
            tmp[k] = arr[j]
            j++
        }
        k++
    }

    // 处理剩余的元素，可能存在左半部分或右半部分有剩余的情况
    for i <= mid {
        tmp[k] = arr[i]
        i++
        k++
    }

    for j <= right {
        tmp[k] = arr[j]
        j++
        k++
    }

    // 将归并后的结果复制回原数组 arr
    for i := left; i <= right; i++ {
        arr[i] = tmp[i]
    }
}