Go 归并排序

• By Admin
• 4个月前

该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并

package main

import (
    "fmt"
    "time"
    "math/rand"
)

func merge(numArr []int, L int, M int, R int){
    // 重新准备一个临时数组，用于存放要排序的数据
    temp := make([]int, R-L+1)
    for i := L; i <= R; i++ {
        temp[i-L] = numArr[i]
    }

    // 标记两部分起点
    left := 0
    right := M+1-L

    for i := L ; i <= R; i++ {
        if left+L > M {
            // 左边越过中线，说明只剩右边的数据
            numArr[i] = temp[right]
            right++
        }else if right+L > R {
            // 右边越过边界，说明只剩左边的数据
            numArr[i] = temp[left]
            left++
        }else if temp[left] < temp[right]{
            // 左小右大，取右边
            numArr[i] = temp[right]
            right++
        }else {
            // 左大右小，取左边
            numArr[i] = temp[left]
            left++
        }
    }
}

func mergeSort(numArr []int, L int, R int){
    if( L == R ){
        return
    }
    var M int
    M = (L+R)/2

    mergeSort(numArr,L,M)

    mergeSort(numArr,M+1,R)

    merge(numArr, L, M, R)
}

// 归并排序 类似于后序遍历二叉树
func main(){

    rand.Seed(time.Now().UnixNano())

    numArr := make([]int,10)
    for i := range numArr{
        numArr[i] = rand.Intn(100)
    }
    fmt.Println(numArr)
    // fmt.Println(numArr[3:9])
    mergeSort(numArr,0,len(numArr)-1)
    fmt.Println(numArr)
}