go 快速排序 归并排序

快速排序

package main

import "fmt"

func main() {
    a := []int{3,12,3,5,12,3,123,1,5,0}
    QuickSort(a, 0, len(a) - 1)
    fmt.Println("a: ", a)
}

func QuickSort(nums []int,begin, end int)  {
    // 快速排序的 思想
    if begin >= end {
        return
    }

    low, hight, mid := begin, end, nums[begin]
    // 用一个哨兵 去和 其他的 数字进行比较
    for low < hight {
        // 比较高位
        for low < hight && mid <= nums[hight] {
            hight --
        }
        nums[low] = nums[hight]

        // 比较低位
        for low < hight && mid > nums[low] {
            low ++
        }
        nums[hight] = nums[low]
    }

    nums[low] = mid
    QuickSort(nums, begin, low - 1)
    QuickSort(nums, low + 1, end)
}

归并排序

package main

import "fmt"

func  main() {
    a := []int{2,1,3,6,1,3,1}
    ParseLst(a, 0, len(a) - 1)
    fmt.Println(a)
}

// 此函数 为拆分函数
func ParseLst(nums []int, begin, end int) {
    if begin >= end {
        return
    }
    // 二分 中间值
    mid := (begin + end) / 2
    ParseLst(nums, begin, mid)
    ParseLst(nums, mid + 1, end)
    MergeSort(nums,  begin, mid, end)
}



// 此函数进行 比较
func MergeSort(nums []int, begin, mid, end int) {

    var tmp []int
    s1, s2 := begin, mid + 1

    for s1 <= mid && s2 <= end {
        if nums[s1] > nums[s2] {
            tmp = append(tmp, nums[s2])
            s2 ++
        } else {
            tmp = append(tmp, nums[s1])
            s1 ++
        }
    }

    if s1 <= mid {
        tmp = append(tmp, nums[s1: mid + 1]...)
    }

    if s2 <= end {
        tmp = append(tmp, nums[s2:end + 1]...)
    }

    for index, val := range tmp {
        nums[begin + index] = val
    }
}