不稳定排序算法

希尔排序

平均时间复杂度O(n^1.3)
最好时间复杂度O(n)
最坏时间复杂度O(n^2)
空间复杂度O(1)

func ShellSort(a []int, n int) {
    dk := n / 2
    for dk >= 1 {
        shellInsertSort(a, n, dk)
        dk /= 2
    }
}
func shellInsertSort(a []int, n int, dk int) {
    for i := dk; i < n; i += dk {
        if a[i] < a[i-dk] {
            j := i - dk
            x := a[i]
            a[i] = a[i-dk]
            for j >= 0 && x < a[j] {
                a[j+dk] = a[j]
                j -= dk
            }
            a[j+dk] = x
        }
    }
}

简单选择排序

平均时间复杂度O(n^2)
最好时间复杂度O(n^2)
最坏时间复杂度O(n^2)
空间复杂度O(1)

func SelectSort(a []int, n int) {
    for i := 0; i < n; i++ {
        key := i
        for j := i + 1; j < n; j++ {
            if a[key] > a[j] {
                key = j
            }
        }
        if key != i {
            tmp := a[i]
            a[i] = a[key]
            a[key] = tmp
        }
    }
}

堆排序

平均时间复杂度O(nlogn)
最好时间复杂度O(nlogn)
最坏时间复杂度O(nlogn)
空间复杂度O(1)

func HeapSort(a []int, n int) {
    buildingHeap(a, n)
    for i := n - 1; i > 0; i-- {
        tmp := a[i]
        a[i] = a[0]
        a[i] = tmp
        heapAdjust(a, 0, i)
    }
}

func heapAdjust(a []int, s int, n int) {
    tmp := a[s]
    child := 2*s + 1
    for child < n {
        if child+1 < n && a[child] > a[child+1] {
            child++
        }
        if a[s] > a[child] {
            a[s] = a[child]
            a[child] = tmp
            s = child
            child = 2*s + 1
        } else {
            break
        }
    }
}
func buildingHeap(a []int, n int) {
    for i := (n - 1) / 2; i >= 0; i-- {
        heapAdjust(a, i, n)
    }
}

快速排序

平均时间复杂度O(nlogn)
最好时间复杂度O(nlogn)
最坏时间复杂度O(n^2)
空间复杂度O(nlogn)

func QuickSort(a []int, l int, r int) {
    if l < r {
        i := l
        j := r
        x := a[l]
        for i < j {
            for i < j && a[j] >= x {
                j--
            }
            if i < j {
                a[i] = a[j]
                i++
            }
            for i < j && a[i] < x {
                i++
            }
            if i < j {
                a[j] = a[i]
                j--
            }
        }
        a[i] = x
        QuickSort(a, l, i-1)
        QuickSort(a, i+1, r)
    }
}

稳定排序算法

冒泡排序

平均时间复杂度O(n^2)
最好时间复杂度O(n)
最坏时间复杂度O(n^2)
空间复杂度O(1)

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

直接插入排序

平均时间复杂度O(n^2)
最好时间复杂度O(n)
最坏时间复杂度O(n^2)
空间复杂度O(1)

func InsertSort(a []int, n int) {
    for i := 1; i < n; i++ {
        if a[i] < a[i-1] {
            j := i - 1
            x := a[i]
            a[i] = a[i-1]
            for j >= 0 && x < a[j] {
                a[j+1] = a[j]
                j--
            }
            a[j+1] = x
        }
    }
}

归并排序

平均时间复杂度O(nlogn)
最好时间复杂度O(nlogn)
最坏时间复杂度O(nlogn)
空间复杂度O(n)

func MergeSort(a []int,f int,l int, tmp []int) {
    if f<l {
        mid := (f+l)/2
        MergeSort(a,f,mid,tmp)
        MergeSort(a,mid+1,l,tmp)
        mergeArray(a,f,mid,l,tmp)
    }
}
func mergeArray(a []int,f int, mid int,l int, tmp []int) {
    i:= f
    j:= mid+1
    m := mid
    n := l
    k := 0
    for i<=m && j<=n {
        if a[i]<=a[j]{
            tmp[k] = a[i]
            k++
            i++
        } else {
            tmp[k] = a[j]
            k++
            j++
        }
    }
    for i<=m{
        tmp[k] = a[i]
        k++
        i++
    }
    for j<=n{
        tmp[k] = a[j]
        k++
        j++
    }
    for i:=0;i<k;i++{
        a[f+i] = tmp[i]
    }
}

比较排序

原文：https://www.cnblogs.com/weiweng/p/12485864.html