排序算法

列举了十大排序算法

• 冒泡排序

• 插入排序

• 选择排序

• 希尔排序

• 堆排序

• 归并排序

• 计数排序

• 桶排序

• 基数排序

算法复杂度

Golang 代码实现

package main

import (
    "fmt"
    "sort"
)

func main() {
    // nums := []int{2, 6, 4, 8, 10, 9, 15}
    nums := []int{3, 2, 5, 4, 8, 9, 6, 7}
    // nums := []int{2, 1}
    // fmt.Println(findUnsortedSubarray(nums))
    radixSort(nums, 1)

}

func findUnsortedSubarray(nums []int) int {
    start := -1
    end := 0
    numsBack := make([]int, len(nums))
    copy(numsBack, nums)
    sort.Ints(numsBack)
    for i := 0; i < len(nums); i++ {
        if nums[i] != numsBack[i] {
            if start == -1 {
                start = i
            }
            end = i + 1
        }
    }
    if start == -1 {
        return 0
    }
    return end - start
}

// 堆排序
func headSort(nums []int) {
    m := len(nums)
    s := m / 2
    // 调整堆
    for i := s; i > -1; i-- {
        heapify(nums, i, m-1)
    }
    // 把堆顶和最后一个元素交换，再调整堆
    for i := m - 1; i > 0; i-- {
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, 0, i-1)
    }
}
func heapify(nums []int, i, end int) {
    l := 2*i + 1
    if l > end {
        return
    }
    n := l
    r := 2*i + 2
    if r <= end && nums[r] > nums[l] {
        n = r
    }
    if nums[i] > nums[n] {
        return
    }
    nums[n], nums[i] = nums[i], nums[n]
    // 递归调整子节点
    heapify(nums, n, end)
}

// 快速排序 (挖坑法)
func quickSort(nums []int, left, right int) {
    if left < right {
        partitionIndex := partition(nums, left, right)
        quickSort(nums, left, partitionIndex-1)
        quickSort(nums, partitionIndex+1, right)
    }
    fmt.Println(nums)
}
func partition(nums []int, left, right int) int {
    // 从左往右扫描，或者从右往左扫描都是可以的。
    pivot := nums[left]
    j := left + 1
    for i := j; i <= right; i++ {
        if nums[i] < pivot {
            nums[i], nums[j] = nums[j], nums[i]
            j++
        }
    }
    nums[left], nums[j-1] = nums[j-1], pivot
    return j - 1
}

// 快速排序 2
func quickSort2(nums []int, start, end int) {
    if start < end {
        i, j := start, end
        poivt := nums[(i+j)/2]
        for i <= j {
            for nums[i] < poivt {
                i++
            }
            for nums[j] > poivt {
                j--
            }
            if i <= j {
                nums[j], nums[i] = nums[i], nums[j]
                i++
                j--
            }
        }
        if start < j {
            quickSort2(nums, start, j)
        }
        if end > i {
            quickSort2(nums, i, end)
        }
    }
}

// 插入排序
func insertionSort(nums []int) {
    length := len(nums)
    preIndex := 0
    current := 0
    for i := 1; i < length; i++ {
        preIndex = i - 1
        current = nums[i]
        for preIndex >= 0 && current < nums[preIndex] {
            nums[preIndex+1] = nums[preIndex]
            preIndex--
        }
        nums[preIndex+1] = current
    }
    // fmt.Println(nums)
}

// 希尔排序
func shellSort(nums []int) {
    n := len(nums)
    if n < 2 {
        return
    }
    key := n / 2
    for key > 0 {
        for i := key; i < n; i++ {
            temp := nums[i]
            j := i
            for j >= key && nums[j-key] > temp {
                nums[j], nums[j-key] = nums[j-key], nums[j]
            }
        }
        key = key / 2
    }
}

// 选择排序
func selectionSort(nums []int) {
    length := len(nums)
    for i := 0; i < length-1; i++ {
        minIndex := i
        for j := i + 1; j < length; j++ {
            if nums[j] < nums[minIndex] {
                minIndex = j
            }
        }
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    }
    fmt.Println(nums)
}

// 冒泡排序
func bubbleSort(nums []int) {
    length := len(nums)
    for i := 0; i < length-1; i++ {
        for j := i; j < length-1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
    fmt.Println(nums)
}

// 归并排序
func mergeSort(nums []int) []int {
    n := len(nums)
    if n < 2 {
        return nums
    }
    key := n / 2
    left := mergeSort(nums[0:key])
    right := mergeSort(nums[key:])
    return merge(left, right)
}
func merge(left, right []int) []int {
    newArr := make([]int, len(left)+len(right))
    i, j, index := 0, 0, 0
    for {
        if left[i] > right[j] {
            newArr[index] = right[j]
            index++
            j++
            if j == len(right) {
                copy(newArr[index:], left[i:])
                break
            }
        } else {
            newArr[index] = left[i]
            index++
            i++
            if i == len(left) {
                copy(newArr[index:], right[j:])
                break
            }
        }
    }
    return newArr
}

// 桶排序
func bucketSort(nums []int, bucketSize int) {
    if len(nums) == 0 {
        return
    }
    minValue := nums[0]
    maxValue := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] < minValue {
            minValue = nums[i]
        }
        if nums[i] > maxValue {
            maxValue = nums[i]
        }
    }
    bucket := make([][]int, bucketSize)
    for i := 0; i < len(nums); i++ {
        bucket[i] = []int{}
    }
    for i := 0; i < len(nums); i++ {
        key := (nums[i] - minValue) / len(nums)
        bucket[key] = append(bucket[key], nums[i])
    }
    nums = nums[:0]
    for i := 0; i < bucketSize; i++ {
        insertionSort(bucket[i])
        for j := 0; j < len(bucket[i]); j++ {
            nums = append(nums, bucket[i][j])
        }
    }
    fmt.Println(nums)
}

// 计数排序 ,n 是数组的大小
func countingSort(nums []int, n int) {
    if n <= 1 {
        return
    }
    max := nums[0]
    for i := 0; i < len(nums); i++ {
        if max < nums[i] {
            max = nums[i]
        }
    }
    c := make([]int, max+1)
    // 计算每个数组的个数，放入 c 中
    for i := 0; i < len(nums); i++ {
        c[nums[i]]++
    }
    // 依次累加
    for i := 1; i <= max; i++ {
        c[i] = c[i-1] + c[i]
    }
    r := make([]int, n)
    // 计算的关键步骤，不好理解
    for i := n - 1; i >= 0; i-- {
        index := c[nums[i]] - 1
        r[index] = nums[i]
        c[nums[i]]--
    }
    // 将结果拷备给 nums
    for i := 0; i < n; i++ {
        nums[i] = r[i]
    }
    fmt.Println(nums)
}

// 基数排序
func radixSort(nums []int, maxDigit int) {
    counter := make([][]int, 10)
    mod := 10
    dev := 1
    for i := 0; i < maxDigit; i++ {
        for j := 0; j < len(nums); j++ {
            bucket := (nums[j] % mod) / dev
            counter[bucket] = append(counter[bucket], nums[j])
        }
        pos := 0
        for j := 0; j < len(counter); j++ {
            if counter[j] != nil {
                for k := 0; k < len(counter[j]); k++ {
                    nums[pos] = counter[j][k]
                    pos++
                }
            }
        }

        dev *= 10
        mod *= 10
    }
    fmt.Println(nums)
}
func isExist(nums []int, key int) bool {
    for index := range nums {
        if index == key {
            return true
        }
    }
    return false
}

参考

• 十大经典排序算法（动图演示）