前言

golang实现排序算法

正文

选择排序

func selectSort(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
            }
        }
        swap(arr, i, minIndex)
    }
}

冒泡排序

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

插入排序

func insertInsert(arr []int) {
    for i := 1; i < len(arr); i++ {
        for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
            swap(arr, j, j-1)
        }
    }
}

归并排序

func mergeSort(arr []int) {
    if arr == nil || len(arr) < 2 {
        return
    }
    process(arr, 0, len(arr)-1)
}

func process(arr []int, left, right int) {
    if left == right {
        return
    }
    mid := left + (right-left)>>1
    process(arr, left, mid)
    process(arr, mid+1, right)
    merge(arr, left, mid, right)
}

func merge(arr []int, left, mid, right int) {
    help := make([]int, right-left+1)
    ptr1 := left
    ptr2 := mid + 1
    i := 0
    for ptr1 <= mid && ptr2 <= right {
        if arr[ptr1] <= arr[ptr2] {
            help[i] = arr[ptr1]
            ptr1++
        } else {
            help[i] = arr[ptr2]
            ptr2++
        }
        i++
    }
    for ptr1 <= mid {
        help[i] = arr[ptr1]
        ptr1++
        i++
    }
    for ptr2 <= right {
        help[i] = arr[ptr2]
        ptr2++
        i++
    }
    for j := 0; j < len(help); j++ {
        arr[left+j] = help[j]
    }
}

堆排序1

func heapSort(nums []int) {
    for i := 0; i < len(nums); i++ {
        heapInsert(nums, i)
    }
}
func heapInsert(nums []int, index int) {
    for nums[index] < nums[(index-1)/2] {
        swap(nums, index, (index-1)/2)
        index = (index - 1) / 2
    }
}
func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

堆排序2

func heapSort(nums []int) {
    for i := len(nums) - 1; i >= 0; i-- {
        heapify(nums, i, len(nums))
    }
}
func heapify(nums []int, index, heapSize int) {
    left := index*2 + 1
    for left < heapSize {
        largest := left
        if left+1 < heapSize && nums[largest] < nums[left+1] {
            largest = left + 1
        }
        if nums[largest] < nums[index] {
            break
        }
        swap(nums, index, largest)
        index = largest
        left = index*2 + 1
    }
}
func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

快排

func quickSort(arr []int, l, r int) {
    if l <= r {
        swap(arr, r, rand.Intn(r-l+1)+l)
        mid := partition(arr, l, r)
        quickSort(arr, l, mid[0]-1)
        quickSort(arr, mid[1]+1, r)
    }
}
func partition(arr []int, l, r int) []int {
    less := l - 1
    more := r
    for l < more {
        if arr[l] < arr[r] {
            less++
            swap(arr, less, l)
            l++
        } else if arr[l] > arr[r] {
            more--
            swap(arr, l, more)
        } else {
            l++
        }
    }
    swap(arr, more, r)
    return []int{less + 1, more}
}
func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

记数排序

func countSort(arr []int) {
    if arr == nil || len(arr) < 2 {
        return
    }
    max := math.MinInt64
    for i := 0; i < len(arr); i++ {
        max = int(math.Max(float64(max), float64(arr[i])))
    }
    bucket := make([]int, max+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
            bucket[i]--
            index++
        }
    }
}

基数排序

func process2(arr []int, l, r, digit int) {
    radix := 10
    bucket := make([]int, r-l+1)
    for d := 1; d <= digit; d++ {
        count := make([]int, radix)
        for i := l; i <= r; i++ {
            j := getDigit(arr[i], d)
            count[j]++
        }
        for i := l + 1; i < radix; i++ {
            count[i] += count[i-1]
        }
        for i := len(arr) - 1; i >= l; i-- {
            j := getDigit(arr[i], d)
            bucket[count[j]-1] = arr[i]
            count[j]--
        }
        for i, j := l, 0; i <= r; i, j = i+1, j+1 {
            arr[i] = bucket[j]
        }
    }
}

func getDigit(x, d int) int {
    return x / int(math.Pow(float64(10), float64(d-1))) % 10
}

func radixSort(arr []int) {
    if arr == nil || len(arr) < 2 {
        return
    }
    process2(arr, 0, len(arr)-1, maxBits(arr))
}

func maxBits(arr []int) int {
    max := math.MinInt64
    for i := 0; i < len(arr); i++ {
        max = int(math.Max(float64(max), float64(arr[i])))
    }
    res := 0
    for max != 0 {
        res++
        max /= 10
    }
    return res
}

有疑问加站长微信联系（非本文作者）