【go版本】 常用代码模板1——基础算法+模板题参考实现

快速排序算法模板 —— 模板题 AcWing 785. 快速排序

func quickSort(arr []int, left int, right int) {
    // 递归终止条件，如果左边界大于等于右边界则认为递归结束
    if left >= right {
        return
    }
    // 设定一个分界值，这里是（left + right）/ 2
    pivot := arr[(left+right) >> 1]

    // 分区操作
    i, j := left, right
    for i <= j {
        // 寻找左侧大于等于基准值的元素
        for arr[i] < pivot {
            i++
        }
        // 寻找右侧小于等于基准值的元素
        for arr[j] > pivot {
            j--
        }
        // 交换元素
        if i <= j {
            arr[i], arr[j] = arr[j], arr[i]
            i++
            j--
        }
    }

    // 递归排序左右子数组
    quickSort(arr, left, j)
    quickSort(arr, i, right)
}

归并排序算法模板 —— 模板题 AcWing 787. 归并排序

func mergeSort(arr []int, left int, right int) {
    if left >= right {
        return
    }
    mid := (left + right) >> 1
    mergeSort(arr, left, mid)
    mergeSort(arr, mid+1, right)
    merge(arr, left, mid, right)
}

func merge(arr []int, left int, mid int, right int) {
    temp := make([]int, right-left+1)
    i, j, k := left, mid+1, 0

    // 合并两个有序子数组
    for i <= mid && j <= right {
        if arr[i] <= arr[j] {
            temp[k] = arr[i]
            i++
        } else {
            temp[k] = arr[j]
            j++
        }
        k++
    }

    // 处理剩余元素
    for i <= mid {
        temp[k] = arr[i]
        i++
        k++
    }

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

    // 将临时数组复制回原数组
    copy(arr[left:right+1], temp)
}