美文网首页
常用的排序算法

常用的排序算法

作者: fanlv | 来源:发表于2020-01-16 18:45 被阅读0次

    常用的排序算法

    插入排序

    func insertSort(nums []int) {
        for i := 1; i < len(nums); i++ {
            tmp := nums[i]
            for j := i; j >= 0; j-- {
                if j > 0 && tmp < nums[j-1] {
                    nums[j] = nums[j-1]
                } else {
                    nums[j] = tmp
                    break
                }
            }
        }
    }
    

    折半插入排序

    func binaryInsertSort(nums []int) {
        for i := 1; i < len(nums); i++ {
            left, right := 0, i-1
            mid := 0
            for left < right {
                mid = (left + right) >> 1
                if nums[mid] > nums[i] {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            }
            index := right
            tmp := nums[i]
            if nums[right] < tmp {
                index++
            }
            for j := i; j >= index+1; j-- {
                nums[j] = nums[j-1]
            }
            nums[index] = tmp
    
        }
    }
    

    shell 排序

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

    冒泡排序

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

    选择排序

    func selectSort(a []int) {
        for i := 0; i < len(a); i++ {
            minIndex := i
            for j := i + 1; j < len(a); j++ {
                if a[minIndex] > a[j] {
                    minIndex = j
                }
            }
            a[i], a[minIndex] = a[minIndex], a[i]
        }
    }
    

    快速排序

    func quickSort(arr []int) {
        if len(arr) <= 1 {
            return
        }
        idx := partition(arr)
        quickSort(arr[:idx])
        quickSort(arr[idx+1:])
    }
    
    func partition(a []int) int {
        left := 0
        right := len(a) - 1
        flag := 0
        for left < right {
            for left < right && a[right] >= a[flag] {
                right--
            }
            for left < right && a[left] <= a[flag] {
                left++
            }
            a[left], a[right] = a[right], a[left]
        }
        a[flag], a[right] = a[right], a[flag]
        return right
    }
    

    基数排序

    func radixSort(a []int) {
        n := len(a)
        lists := make([][]int, 10)
        max := a[0]
        for i := 1; i < len(a); i++ {
            if max < a[i] {
                max = a[i]
            }
        }
    
        exp := 1
        for max > 0 {
            //将之前的元素清空
            for i := 0; i < 10; i++ {
                lists[i] = []int{}
            }
            for i := 0; i < n; i++ {
                index := a[i] / exp % 10
                array := lists[index]
                array = append(array, a[i])
                lists[index] = array
            }
            index := 0
            for i := 0; i < 10; i++ {
                arr := lists[i]
                for j := 0; j < len(arr); j++ {
                    a[index] = arr[j]
                    index++
                }
            }
            max /= 10
            exp *= 10
        }
    }
    

    归并排序

    func mergeSort(nums []int) []int {
        if len(nums) <= 1 {
            return nums
        }
        left, right := 0, len(nums)
        mid := (left + right) >> 1
        return merge(mergeSort(nums[:mid]), mergeSort(nums[mid:]))
    
    }
    func merge(left, right []int) []int {
        res := make([]int, 0, len(left)+len(right))
        leftIndex := 0
        rightIndex := 0
        for leftIndex < len(left) || rightIndex < len(right) {
            if leftIndex < len(left) && rightIndex < len(right) {
                if left[leftIndex] < right[rightIndex] {
                    res = append(res, left[leftIndex])
                    leftIndex++
                } else {
                    res = append(res, right[rightIndex])
                    rightIndex++
                }
            } else if leftIndex == len(left) && rightIndex < len(right) {
                res = append(res, right[rightIndex])
                rightIndex++
            } else if rightIndex == len(right) && leftIndex < len(left) {
                res = append(res, left[leftIndex])
                leftIndex++
            }
        }
        return res
    }
    

    堆排序

    func heapSort(a []int) {
        //构建大顶堆
        lenA := len(a)
        for i := len(a)/2 - 1; i >= 0; i-- {
            adjustHead(a, i, lenA)
        }
        for i := len(a) - 1; i > 0; i-- {
            a[0], a[i] = a[i], a[0]
            adjustHead(a, 0, i)
        }
    
    }
    func adjustHead(a []int, i, length int) {
        tmp := a[i]
        //用k := 2*i + 1 的到i子节点的位置
        for k := 2*i + 1; k < length; k = 2*k + 1 {
            // 让k先指向子节点中最大的节点
            if k+1 < length && a[k] < a[k+1] {
                k++
            }
            if a[k] > tmp { //子节点比根节点大
                a[i], a[k] = a[k], a[i]
                i = k
            } else {
                break
            }
        }
    }
    

    KMP查找子串

    func kmp(str string, needle string) int {
        next := makeNext(str)
        j := 0
        for i := 0; i < len(str); i++ {
            for j > 0 && str[i] != needle[j] {
                j = next[j-1]
            }
            if str[i] == needle[j] {
                j++
            }
            if j == len(needle) {
                return i - j + 1
            }
        }
        return -1
    }
    
    func makeNext(s string) []int {
        next := make([]int, len(s))
        next[0] = 0
        k := 0
        for i := 1; i < len(s); i++ {
            for k > 0 && s[k] != s[i] {
                k = next[k-1]
            }
            if s[k] == s[i] {
                k++
            }
            next[i] = k
        }
        return next
    }

    相关文章

      网友评论

          本文标题:常用的排序算法

          本文链接:https://www.haomeiwen.com/subject/hoqqzctx.html