【数据结构与算法】排序算法(Go实现)

基础排序算法

插入排序

func InsertSort(nums []int) {
    for i := 1; i < len(nums); i++ {
        val := nums[i]
        j := i
        for j > 0 && nums[j-1] > val {
            nums[j] = nums[j-1]
            j--
        }
        nums[j] = val
    }
}

冒泡排序

func BubbleSort(nums []int) {
    for i := len(nums) - 1; i > 0; i-- {
        for j := 0; j < i; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
}

选择排序

func SelectSort(nums []int) {
    for i := 0; i < len(nums)-1; i++ {
        minJ := i
        for j := i + 1; j < len(nums); j++ {
            if nums[minJ] > nums[j] {
                minJ = j
            }
        }
        nums[i], nums[minJ] = nums[minJ], nums[i]
    }
}

希尔排序

func ShellSort(nums []int) {
    G := make([]int, 0)
    n := len(nums)
    h := 1
    for h < n {
        G = append(G, h)
        h = h*3 + 1
    }
 
    insertSort := func(g int) {
        for i := g; i < n; i++ {
            val := nums[i]
            j := i
            for j >= g && nums[j-g] > val {
                nums[j] = nums[j-g]
                j -= g
            }
            nums[j] = val
        }
    }

    for i := len(G) - 1; i >= 0; i-- {
        insertSort(G[i])
    }
}

高级排序

快速排序

func QuickSort(nums []int, left, right int) {
    if left >= right {
        return
    }
    i, j := left, right
    x := nums[i]
    for i < j {
        for i < j && nums[j] >= x {
            j--
        }
        nums[i] = nums[j]
        for i < j && nums[i] <= x {
            i++
        }
        nums[j] = nums[i]
    }
    nums[i] = x

    QuickSort(nums, left, i-1)
    QuickSort(nums, i+1, right)
}

归并排序

func MergeSort(nums, tmp []int, left, right int) {
    if left >= right {
        return
    }
    mid := left + (right-left)/2
    MergeSort(nums, tmp, left, mid)
    MergeSort(nums, tmp, mid+1, right)

    i, j, k := left, mid+1, 0
    for i <= mid && j <= right {
        if nums[i] < nums[j] {
            tmp[k] = nums[i]
            k++
            i++
        } else {
            tmp[k] = nums[j]
            k++
            j++
        }
    }
    for i <= mid {
        tmp[k] = nums[i]
        k++
        i++
    }
    for j <= mid {
        tmp[k] = nums[j]
        k++
        j++
    }
    for i, j = left, 0; j < k; i, j = i+1, j+1 {
        nums[i] = tmp[j]
    }
}

堆排序

func HeapSort(nums []int) {
    n := len(nums)

    up2down := func(idx int, sz int) {
        for idx < sz {
            j := idx*2 + 1
            if j >= sz {
                break
            }
            if j+1 < sz && nums[j] < nums[j+1] {
                j++
            }
            if nums[idx] < nums[j] {
                nums[idx], nums[j] = nums[j], nums[idx]
            }
            idx = j
        }
    }

    for i := n/2 - 1; i >= 0; i-- {
        up2down(i, n)
    }

    last := n - 1
    for i := len(nums); i > 0; i-- {
        nums[0], nums[last] = nums[last], nums[0]
        last--
        up2down(0, last+1)
    }
}