温习mergesort归并排序

• https://www.nowcoder.com/questionTerminal/2baf799ea0594abd974d37139de27896
  image.png

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
func MySort(arr []int) []int {
    // write code here
    mergeSort(arr, 0, len(arr)-1)
    return arr
}

// 归并排序 O(nlogn)
// 是一种分而治之的算法，其思想是将一个列表分解为几个子列表，
// 直到每个子列表由一个元素组成，然后将这些子列表合并为排序后的列表。
// 先把数组从中间分成前后两部分，然后对前后两部分分别排序，
// 再将排好序的两部分合并在一起，这样整个数组就都有序了。
func mergeSort(arr []int, left, right int) {

    if left < right {
        mid := left + (right-left)>>1
        mergeSort(arr, left, mid)
        mergeSort(arr, mid+1, right)
        merge(arr, left, mid, right) //通过比较2个部分的元素来合并2个部分
    }
}
// 合并2个有序数组
func merge(arr []int, left, mid, right int) {
    tmp := make([]int, right-left+1)
    i, j,k := left, mid+1,0
    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]
        k++
        i++
    }
    for j <= right {
        tmp[k] = arr[j]
        k++
        j++
    }
    copy(arr[left:right+1], tmp)

}

ref

• https://leetcode.cn/problems/sort-an-array/solution/golang-by-xilepeng-2/#%E8%A1%A5%E5%85%85%E9%A2%985-%E6%89%8B%E6%92%95%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
• https://leetcode.cn/circle/article/zeM9YK/