头图来源：やっと、見つけた-あるみっく-pixiv

默认均为顺序排序

冒泡排序

• 平均时间复杂度：O(n²)
• 最好时间复杂度: O(n)
• 最坏时间复杂度：O(n²)
• 空间复杂度： O(1)
• 稳定性：true

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

选择排序

• 平均时间复杂度：O(n²)
• 最好时间复杂度: O(n²)
• 最坏时间复杂度：O(n²)
• 空间复杂度： O(1)
• 稳定性：false

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

插入排序

• 平均时间复杂度：O(n²)
• 最好时间复杂度: O(n)
• 最坏时间复杂度：O(n²)
• 空间复杂度： O(1)
• 稳定性：true

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

希尔排序

• 平均时间复杂度：O(n²)
• 最好时间复杂度: O(nlogn)
• 最坏时间复杂度：O(n²)
• 空间复杂度： O(1)
• 稳定性：false

func ShellSort(nums []int) {
    gap := 1
    for gap < len(nums)/3 {
        gap = gap*3 + 1
    }
    for gap > 0 {
        for i := gap; i < len(nums); i++ {
            temp := nums[i]
            j := i - gap
            for j >= 0 && nums[j] > temp {
                nums[j+gap] = nums[j]
                j -= gap
            }
            nums[j+gap] = temp
        }
        gap /= 3
    }
}

归并排序

• 平均时间复杂度：O(nlogn)
• 最好时间复杂度: O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 空间复杂度： O(n)
• 稳定性：true

func MergeSort(nums []int)[]int{
    if len(nums)<2{
        return nums
    }
    mid:=len(nums)/2
    left:=nums[:mid]
    right:=nums[mid:]
    return merge(MergeSort(left),MergeSort(right))
}

func merge(left []int,right []int)[]int{
    var res []int
    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
}

堆排序

• 平均时间复杂度：O(nlogn)
• 最好时间复杂度: O(nlogn)
• 最坏时间复杂度：O(nlogn)
• 空间复杂度： O(1)
• 稳定性：false

func HeapSort(arr []int) {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }

    for i := n - 1; i > 0; i-- {
        swap(arr, 0, i)
        heapify(arr, i, 0)
    }
}

func heapify(arr []int, n int, i int) {
    pos := i

    for pos <= n/2-1 {
        old := pos
        left, right := 2*pos+1, 2*pos+2
        if left < n && arr[left] > arr[pos] {
            pos = left
        }
        if right < n && arr[right] > arr[pos] {
            pos = right
        }
        if pos == old {
            return
        }
        swap(arr, pos, i)
        i = pos
    }
}

快速排序

• 平均时间复杂度：O(nlogn)
• 最好时间复杂度: O(nlogn)
• 最坏时间复杂度：O(n²)
• 空间复杂度： O(logn)
• 稳定性：false

func QuickSort(nums []int, i, j int) {
    if i >= j {
        return
    }
    pivot := getPivot(nums, i, j)
    finalIdx := qsort(nums, i, j, pivot)
    QuickSort(nums, i, finalIdx-1)
    QuickSort(nums, finalIdx+1, j)
}

func qsort(nums []int, i, j, pivot int) int {
    swap(nums, pivot, i)
    origin := i
    i++
    for {
        for i <= j && nums[i] <= nums[origin] {
            i++
        }
        for i <= j && nums[j] >= nums[origin] {
            j--
        }
        if i > j {
            break
        }
        swap(nums, i, j)
    }
    swap(nums, origin, j)
    return j
}

func getPivot(nums []int, l, r int) int {
    mid := l + (r-l)>>1
    if (nums[mid]-nums[l])*(nums[mid]-nums[r]) < 0 {
        return mid
    } else if (nums[l]-nums[mid])*(nums[l]-nums[r]) < 0 {
        return l
    } else {
        return r
    }
}