Golang代码搜集-常用排序算法冒泡、选择、插入、希尔、快速

曾经终败给现在 2021-09-14 14:48 312阅读 0赞

排序算法可以说是最基本的算法，下面代码是经过本人反复验证和修改总结，已经忘了出处，某类型只要实现了Interface接口，就可以使用下面的几个算法。

//sdsort.go
    package sdsort
    
    type Interface interface { Len() int Less(i, j int) bool Swap(i, j int) }
    
    /*
    冒泡排序
    基本实现思路:
    假设有data[0]~data[N-1]条数据
    1、i，j两层循环
    2、将data[i]依次与data[i+1,N-1]进行比较，小于则交换，大数在前
    3、i循环完毕，排序完成
    */
    func BubbleSort(data Interface) { n := data.Len() for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { if data.Less(i, j) { data.Swap(i, j) }
            }
        }
    }
    
    /*
    选择排序
    基本实现思路:
    假设有data[0]~data[N-1]条数据
    1、i，j两层循环
    2、i=0时，找出data[1:N-1]中最小的数与a[0]交换
    3、i循环完毕，排序完成
    */
    func SelectSort(data Interface) { n := data.Len() var min int for i := 0; i < n; i++ { //记录最小元素的下标 min = i for j := i + 1; j < n; j++ { if data.Less(j, min) { min = j }
            }
            data.Swap(i, min)
        }
    }
    
    /*
    插入排序
    假设有data[0]~data[N-1]条数据
    1、i，j两层循环
    2、i=4时，j=4,依次将data[j]与前面的进行比较，小于则交换
    3、i循环完毕，排序完成
    */
    func InsertSrot(data Interface) { count := data.Len() for index := 1; index < count; index++ { for j := index; j > 0 && data.Less(j, j-1); j-- { //j>0 做一个边界守护，不让下标小于0 data.Swap(j, j-1) }
        }
    }
    
    /*
    希尔排序
    */
    func ShellSort(data Interface) { N := data.Len() h := 1 for h < N/3 { h = 3*h + 1 }
        for h > 0 {
            for index := h; index < N; index++ {
                for j := index; j >= h && data.Less(j, j-h); j -= h { //j>0 做一个边界守护，不让下标小于0 data.Swap(j, j-h) }
            }
            h = h / 3
        }
    }
    
    /*
    快速排序算法
    基本实现思路：假设有data[0]~data[N-1]条数据
    1、初始low=0，high=N-1,取pivot=data[low]
    2、从右边开始，找出第一个小于pivot的值,high--
    3、从左边开始，找出第一个大于pivot的值,low++
    4、将第2，3步的两个值交换，如果此时low<high,则继续以当前的pivot进行循环第2，3步，否则第5步
    5、将pivot值也low值交换，返回low值
    6、递归调用，处理low值左边的数据和low值右边的数据
    */
    func QuickSort(data Interface) { n := data.Len() qsort(data, 0, n-1) }
    func qsort(data Interface, low, high int) { if low < high { pivotKey := partition(data, low, high) qsort(data, low, pivotKey-1) qsort(data, pivotKey+1, high) }
    }
    
    func partition(data Interface, low, high int) int { pivotKey := low for low < high { //先从右边开始，值不小于pivot则继续循环 for low < high && data.Less(pivotKey, high) { high-- }
            //右边停止后 ，左边开始，值小于pivot继续循环
            for low < high && !data.Less(pivotKey, low) { low++ }
            //把大的交换到右边，把小的交换到左边
            data.Swap(low, high)
            //如果此时 low < high时，则继续以当前pivot为关键值继续进行处理
        }
        //最后把pivot到中间
        data.Swap(low, pivotKey)
        return low
    }

//main.go
    package main
    
    import (
        "fmt"
        "sdsort"
    )
    
    type Slice []int
    
    func (this Slice) Len() int {
        return len(this)
    }
    func (this Slice) Less(i, j int) bool {
        return this[i] < this[j]
    }
    func (this Slice) Swap(i, j int) {
        this[i], this[j] = this[j], this[i]
    }
    
    func main() {
        data := Slice{
       4, 2, 3, 1, 4, 8, 7, 5, 9}
        sdsort.QuickSort(data)
        fmt.Println(data)
    }