头图来源:やっと、見つけた-あるみっく-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
    }
}

希尔排序的时间复杂度取决于gap的选择

归并排序

  • 平均时间复杂度: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)
    mid := qsort(nums, i, j, pivot, isLess)
    quickSort(nums, i, mid-1)
    quickSort(nums, mid+1, j)
}

func qsort(nums []int, i, j, pivot int, isLess func(int, int) bool) 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
    }
}

快速排序的时间复杂度取决于pivot的选取,如果每次选取的pivot的最终位置均位于数组的中间则快速排序的效率最高,反之,若位于数组的两端则效率将降低

最后修改:2022 年 06 月 19 日 10 : 46 PM
如果觉得我的文章对你有用,请随意赞赏