排序算法

• 参考
• https://www.cnblogs.com/onepixel/articles/7674659.html
• 时间复杂度O(n^2): 冒泡排序、选择排序、插入排序、希尔排序(n^1.3)
• 时间复杂度O(nlog(n)): 快速排序、堆排序、归并排序
• 时间复杂度O(n): 计数排序、桶排序、基数排序
• 不稳定排序：选择排序、希尔排序、快速排序、堆排序

总结

1.冒泡排序

// 依次比较和交换，把最大值或者最小值交换到后面已经排好序数组之前
func bubbleSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
        for j := 0; j < len(arr)-1-i; j++ {
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
}

2.选择排序

// 每次选择未排好序数组的最小值，添加到已经排好序后面
// 序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，破坏稳定性
func selectionSort(arr []int) {
    for i := 0; i < len(arr)-1; i++ {
        minIndex := i
        for j := i + 1; j < len(arr); j++ {
            if arr[j] < arr[minIndex] {
                minIndex = j
            }
        }
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    }
}

3.插入排序

// 依次选择一个数据，插入到前面已经排好序中，需要数据后移
func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        pos := i - 1 // 已经有序的最后一个下标
        cur := arr[i]
        for pos >= 0 && arr[pos] > cur {
            arr[pos+1] = arr[pos] // 后移
            pos--
        }
        arr[pos+1] = cur
    }
}

4.希尔排序

// 选定间隔
func shellSort(arr []int) {
    n := len(arr)
    for gap := n / 2; gap > 0; gap = gap / 2 {
        for i := gap; i < n; i++ {
            j := i
            cur := arr[i]
            for j-gap >= 0 && cur < arr[j-gap] {
                arr[j] = arr[j-gap]
                j = j - gap
            }
            arr[j] = cur
        }
    }
}

5.归并排序

func mergeSort(arr []int) []int {
    n := len(arr)
    if n < 2 {
        return arr
    }
    return merge(mergeSort(arr[:len(arr)/2]), mergeSort(arr[len(arr)/2:]))
}

func merge(left, right []int) []int {
    res := make([]int, 0)
    for len(left) > 0 && len(right) > 0 {
        if left[0] <= right[0] {
            res = append(res, left[0])
            left = left[1:]
        } else {
            res = append(res, right[0])
            right = right[1:]
        }
    }
    if len(left) > 0 {
        res = append(res, left...)
    }
    if len(right) > 0 {
        res = append(res, right...)
    }
    return res
}

6.快排排序

• 依次交换

func quickSort(arr []int) {
    quick(arr, 0, len(arr)-1)
}

func quick(arr []int, left, right int) {
    if left >= right {
        return
    }
    index := partition(arr, left, right)
    quick(arr, left, index-1)
    quick(arr, index+1, right)
}

func partition(arr []int, left, right int) int {
    baseValue := arr[left] // 基准值
    for left < right {
        for baseValue <= arr[right] && left < right {
            right-- // 依次查找大于基准值的位置
        }
        arr[left] = arr[right]
        for arr[left] <= baseValue && left < right {
            left++ // 依次查找小于基准值的位置
        }
        arr[right] = arr[left]
    }
    arr[right] = baseValue
    return right
}

• 顺序交换

func quickSort(arr []int, left, right int) {
    if left >= right {
        return
    }
    index := partition(arr, left, right)
    quickSort(arr, left, index-1)
    quickSort(arr, index+1, right)
}

func partition(arr []int, left, right int) int {
    baseValue := arr[left] // 基准值
    mark := left
    for i := left + 1; i <= right; i++ {
        if arr[i] < baseValue {
            mark++
            arr[mark], arr[i] = arr[i], arr[mark]
        }
    }
    arr[left], arr[mark] = arr[mark], arr[left]
    return mark
}

• 快排-非递归

func quickSort(arr []int, left, right int) {
    queue := make([][2]int, 0)
    queue = append(queue, [2]int{left, right})
    for len(queue) > 0 {
        l, r := queue[0][0], queue[0][1]
        queue = queue[1:]
        index := partition(arr, l, r)
        if l < index-1 {
            queue = append(queue, [2]int{l, index - 1})
        }
        if index+1 < r {
            queue = append(queue, [2]int{index + 1, r})
        }
    }
}

func partition(arr []int, left, right int) int {
    baseValue := arr[left] // 基准值
    mark := left
    for i := left + 1; i <= right; i++ {
        if arr[i] < baseValue {
            mark++
            arr[mark], arr[i] = arr[i], arr[mark]
        }
    }
    arr[left], arr[mark] = arr[mark], arr[left]
    return mark
}

7.堆排序

• 堆排序

package main

import "fmt"

func main() {
    arr := []int{66, 33, 55, 22, 11, 99, 88, 77}
    buildHeap(arr) // 构建堆
    fmt.Println(arr)
    // 插入使用上浮
    arr = append(arr, 1)
    up(arr)
    fmt.Println(arr)
    // 删除使用下沉
    value := pop(arr)
    fmt.Println(value, arr)
}

func pop(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    res := arr[0]
    arr[0] = arr[len(arr)-1]
    arr = arr[:len(arr)-1]
    down(arr, 0, len(arr))
    return res
}

// 构建堆[最小堆为例]
func buildHeap(arr []int) {
    // 从最后一个非叶子节点开始
    for i := (len(arr) - 2) / 2; i >= 0; i-- {
        down(arr, i, len(arr))
    }
}

// 下沉[最小堆为例]
func down(arr []int, parentId int, length int) {
    temp := arr[parentId]
    childId := 2*parentId + 1 // 左节点
    for childId < length {
        // 有右节点且右节点小于左节点，childId+1
        if childId+1 < length && arr[childId+1] < arr[childId] { // 小根堆
            // if childId+1 < length && arr[childId+1] > arr[childId] { // 大根堆
            childId = childId + 1
        }
        if temp <= arr[childId] { // 小根堆
            // if temp >= arr[childId] { // 大根堆
            break
        }
        arr[parentId] = arr[childId]
        parentId = childId
        childId = 2*childId + 1
    }
    arr[parentId] = temp
}

// 上浮[最小堆为例]
func up(arr []int) {
    childId := len(arr) - 1                   // 最后一个节点下标（子节点）
    last := arr[childId]                      // 最后一个节点
    parentId := (childId - 1) / 2             // 父节点
    for childId > 0 && last < arr[parentId] { // 小根堆
        // for childId > 0 && last > arr[parentId] { // 大根堆
        arr[childId] = arr[parentId] //
        childId = parentId           //
        parentId = (childId - 1) / 2 //
    }
    arr[childId] = last
}

• 内置heap

type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    value := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return value
}

func heapSort(arr []int) []int {
    intHeap := make(IntHeap, 0)
    heap.Init(&intHeap)
    for i := 0; i < len(arr); i++ {
        heap.Push(&intHeap, arr[i])
    }
    res := make([]int, 0)
    for i := 0; i < len(arr); i++ {
        value := heap.Pop(&intHeap).(int)
        res = append(res, value)
    }
    return res
}

8.计数排序

func countingSort(arr []int) []int {
    maxValue := 0
    for i := 0; i < len(arr); i++ {
        if arr[i] > maxValue {
            maxValue = arr[i]
        }
    }
    bucket := make([]int, maxValue+1)
    for i := 0; i < len(arr); i++ {
        bucket[arr[i]]++
    }
    index := 0
    for i := 0; i < len(bucket); i++ {
        for bucket[i] > 0 {
            arr[index] = i
            index++
            bucket[i]--
        }
    }
    return arr
}

9.桶排序

func bucketSort(arr []int, bucketSize int) {
    maxValue := arr[0]
    minValue := arr[0]
    for i := 1; i < len(arr); i++ {
        if arr[i] > maxValue {
            maxValue = arr[i]
        }
        if arr[i] < minValue {
            minValue = arr[i]
        }
    }
    d := maxValue - minValue
    bucketList := make([][]int, bucketSize)
    for i := 0; i < bucketSize; i++ {
        bucketList[i] = make([]int, 0)
    }
    for i := 0; i < len(arr); i++ {
        index := (arr[i] - minValue) * (bucketSize - 1) / d
        bucketList[index] = append(bucketList[index], arr[i])
    }
    for i := 0; i < bucketSize; i++ {
        sort.Ints(bucketList[i])
    }
    res := make([]int, 0)
    for i := 0; i < bucketSize; i++ {
        for j := 0; j < len(bucketList[i]); j++ {
            res = append(res, bucketList[i][j])
        }
    }
    copy(arr, res)
}

10.基数排序