Go 排序算法实现

这篇具有很好参考价值的文章主要介绍了Go 排序算法实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.冒泡排序

从头开始两两互比然后进行交换。将最大值/最小值 冒到最后一位。依次循环

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]{       // 交换条件
                nums[j],nums[j+1]=nums[j+1],nums[j]  // 元素交换
            }
        }
    }
}

2.选择排序

在未排序序列中找到最小(大)元素,存放到排序序列的起始位置;
再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;
(一次在元素中选择符合需求的元素,然后交换。每个元素只移动一次)

func selectSorted(nums []int) {
    for i := 0; i < len(nums)-1; i++ {  // 从第一个元素开始
        min := i                        // 默认当前元素为最小元素。保存对应下标
        for j := i + 1; j < len(nums); j++ {    
            if nums[min] > nums[j] {    // 找到最小的元素
                min = j                 // 保存最小的值min(下标)
            }
        }
        nums[i], nums[min] = nums[min], nums[i] //交换元素
    }
}

3.插入排序

可以假设前面的已经有序,随机在后面抽取一个元素,插入到前面,并保持有序;
已排好序的依次后移!!!
(扑克牌:每拿起一张,插入到合适的位置。之前的已经有序)

func insertSorted(nums []int) {
    for i := 1; i < len(nums); i++ {
        preIndex := i - 1       // 记录当前值对应前一个元素的下标
        nowNum := nums[i]       // 记录当前值
        for nums[preIndex] > nowNum {           // 循环到前面的值不小于当前值为止
            nums[preIndex+1] = nums[preIndex]   // 将小于当前值的数后移
            preIndex--
        }
        nums[preIndex+1] = nowNum   // 找到了不小于当前置的位置并赋值
    }
}

4.希尔排序

本质是 分组+插入排序
也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是 非稳定 排序算法。
实践中:数据的交换次数远远小于插入排序的交换次数

func shellSorted(nums []int) {
    lens := len(nums)
    tag := 1
    // 选取合适的分组树(即:每组的数据个数)
    for tag < lens/3 {  
        tag = 3*tag + 1     // 比较合适的分组数
    }
    for tag > 0 {
        for i := tag; i < lens; i++ {   // 依旧采用插入算法逻辑,只是跨度变大,以分组为间隔
            j := i - tag
            temp := nums[i]
            for j >= 0 && nums[j] > temp {
                nums[j+tag] = nums[j]
                j -= tag
            }
            nums[j+tag] = temp
        }
        tag /= 3    // tag逐渐缩小,最后为 1
    }
}

5.归并排序

乱序数组,单个元素为一组,两两对比排序;然后已排序数据2个为一组,两两对比排序,以此类推
总结:先分后合(合的时候排好序)

func mergeSorted(nums []int) []int {
    length := len(nums)
    if length < 2 {
        return nums
    }
    left := nums[:length/2]
    right := nums[length/2:]

    return merge(mergeSorted(left), mergeSorted(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:]
        }
    }
    // left或者right其中一个未添加完毕
    if len(left) > 0 {
        res = append(res, left...)
    }
    if len(right) > 0 {
        res = append(res, right...)
    }
    return res
}

6.快速排序

在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较
随机取一个树(一般是第一个数),一次比较,比他小的放左边,大的放右边,依次类推
个人感觉:和归并反着来! 每一次分开,左右都对应已比较完成!
1、从数列中挑出一个元素,称为 “基准”(pivot);
2、重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
3、递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;
优化:
1、机选三个数,取中间的数为 基准
2、当数组比较小的时候采用插入算法,更快

func quickSorted(nums []int) []int {
    return quick(nums, 0, len(nums)-1)
}

func quick(arr []int, left, right int) []int {
    if left < right {   //分次执行
        partitionVal := partition(arr, left, right)
        quick(arr, left, partitionVal-1)    // 先递归把左边的排完
        quick(arr, partitionVal+1, right)   // 再依次由深到浅排序右边
    }
    return arr
}

func partition(arr []int, left, right int) int {
    pivot := left
    index := left + 1
    for i := index; i <= right; i++ {
        if arr[i] < arr[pivot] {
            swap(arr, i, index)     // 调换基数的位置
            index++
        }
    }
    swap(arr, pivot, index-1)       //最后一个空位补上
    return index - 1
}

func swap(arr []int, left, right int) {
    arr[left], arr[right] = arr[right], arr[left]
}

7.堆排序

堆的特点: 完全二叉树、(大顶堆) 所有父节点大于子节点
1、构建一个堆(所有值小于父节点)
2、把堆首和队尾互换
3、堆的大小减一,并重构堆,目的是把最大值放入堆头
4、重复2/3

// 堆排序的实现
// 1、建堆
// 2、堆尾和堆头互换,取出堆头,堆容量缩小一个单位
// 3、重读1/2

// 传入一个数组
func heapSorted(arr []int) []int {
    arrlen := len(arr)
    buildHeap(arr, arrlen)
    fmt.Println(arr)
    // 堆已建造完成,堆头与堆尾交换,堆长减一
    for arrlen > 0 {
        swap(arr, 0, arrlen-1)
        arrlen -= 1
        heapify(arr, 0, arrlen)
    }
    return arr
}

// 将数组建造成堆格式
func buildHeap(arr []int, arrlen int) {
    for i := arrlen / 2; i >= 0; i-- {
        heapify(arr, i, arrlen)
    }
}

// 实际down与swap过程
func heapify(arr []int, i, arrlen int) {
    left := 2*i + 1
    right := 2*i + 2
    parent := i
    // 比较时,找出left与right对应的最大值与之兑换
    if left < arrlen && arr[left] > arr[parent] {
        parent = left
    }
    if right < arrlen && arr[right] > arr[parent] {
        parent = right
    }
    if parent != i {
        swap(arr, i, parent)
        // 用来排除孩子的孩子(第一次建堆时作用可能不大,但是当后面互换后 ,堆顶元素一路向下)
        heapify(arr, parent, arrlen)
    }
}

// 用于两个元素交换
func swap(arr []int, i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}

8.计数排序

1、根据待排序集合中最大元素和最小元素的差值范围,申请额外空间;
2、遍历待排序集合,将每一个元素出现的次数记录到元素值对应的额外空间内;
3、对额外空间内数据进行计算,得出每一个元素的正确位置;
4、将待排序集合每一个元素移动到计算得出的正确位置上。
即:
将相同的数,统计出现次数,然后从小到大,把该数取出对应的次数

// 计数排序(一般用书较集中数据)
// 先确定取值范围
// 创建范围内大小的值,统计
// 注:需要额外空间

func counrSorted(arr []int) []int {
    // 先获取取值范围大小
    // 考虑可能存在负数(两次遍历)
    min, max := 0, 0
    for i := 0; i < len(arr); i++ {
        if arr[i] > max {
            max = arr[i]
        }
        if arr[i] < min {
            min = arr[i]
        }
    }

    // 创建计数器
    blen := max - min + 1
    bucket := make([]int, blen)
    fmt.Println(blen)
    // 统计
    for i := 0; i < len(arr); i++ {
        bucket[arr[i]-min] += 1
    }

    // 原数组中移动
    index := 0
    for i := 0; i < len(bucket); i++ {
        for bucket[i] > 0 {
            arr[index] = i - min
            index++
            bucket[i]--
        }
    }
    return arr
}

9.桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理:
假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)
计数排序时对单个数据,桶排序是对一组数据。分配再排序

func bucketSorted(arr []int){
    vari;
    varminValue = arr[0];
    varmaxValue = arr[0];
    for(i = 1; i < arr.length; i++) {
      if(arr[i] < minValue) {
          minValue = arr[i];               // 输入数据的最小值
      }elseif(arr[i] > maxValue) {
          maxValue = arr[i];               // 输入数据的最大值
      }
    }
    
    // 桶的初始化
    varDEFAULT_BUCKET_SIZE = 5;           // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    varbucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    varbuckets =newArray(bucketCount);
    for(i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }
    
    // 利用映射函数将数据分配到各个桶中
    for(i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }
    
    arr.length = 0;
    for(i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                     // 对每个桶进行排序,这里使用了插入排序
        for(varj = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }

    return arr;
}

10.基数排序

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数
对数字或者字符串进行拆分,单个对比的排序。以此类推文章来源地址https://www.toymoban.com/news/detail-481268.html

// 基数排序
func radixSorted(arr []int) []int {
    // 统计最大子串长度
    max := -1
    length := len(arr)
    // 获取最大数
    for i := 0; i < length; i++ {
        if max < arr[i] {
            max = arr[i]
        }
    }

    // 获取最大位数
    maxlen := 0
    for max > 0 {
        maxlen++
        max /= 10
    }

    // 开始
    bucket := [10][20]int{{0}}
    count := [10]int{0}
    divisor := 1
    for i := 1; i <= maxlen; i++ {
        // 先放入桶中,然后排好序,依次类推
        for j := 0; j < length; j++ {
            tmp := arr[j]
            index := (tmp / divisor) % 10
            bucket[index][count[index]] = tmp
            count[index]++
        }

        // 原数组重新排序
        k := 0
        for m := 0; m < len(bucket); m++ {
            if count[m] == 0 {
                continue
            }
            for n := 0; n < count[n]; n++ {
                arr[k] = bucket[m][n]
                k++
            }
            // 桶清零
            bucket[m] = [20]int{0}
        }
        divisor *= 10
    }
    return arr
}

到了这里,关于Go 排序算法实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包