常用的排序算法

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

总结

常用的排序算法

基于比较的排序(从小到大排序)

冒泡排序

GO实现
func MySort( arr []int ) []int {
    // 冒泡
    // 大的往后冒
    for i := 0; i < len(arr); i++{
        for j := 0; j < len(arr) - 1 - i; j++ {
            if arr[j] > arr[j + 1]{
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            }
        }
    }
    return arr
}
另一种实现
func MySort( arr []int ) []int {
    // 小的往前冒
    for i := 0; i < len(arr); i++{
        for j := len(arr) - 1; j > i ; j-- {
            if arr[j] < arr[j - 1]{
                arr[j], arr[j - 1] = arr[j - 1], arr[j]
            }
        }
    }
    return arr
}

选择排序

GO实现
func MySort( arr []int ) []int {
    // 选择排序
    // 不稳定:5 5 1
    for i := 0; i < len(arr); i++{
        minPoi := i
        for j := i + 1; j < len(arr); j++{
            if arr[minPoi] > arr[j] {
                minPoi = j
            }
        }
        arr[i], arr[minPoi] = arr[minPoi], arr[i]
    }
}

直接插入排序

GO实现
func MySort( arr []int ) []int {
    // 稳定:2 2 1
    for i := 1; i < len(arr); i++ {
        if arr[i] < arr[i - 1]{
            temp := arr[i]
            j := i - 1
            for j >= 0 && temp < arr[j] {
                arr[j + 1] = arr[j]
                j--
            }
            arr[j + 1] = temp
        }
    }
}

希尔排序(第一个突破n^2的排序算法)

GO实现
func MySort( arr []int ) []int {
    // 不稳定:相同元素不在同一组,则无法保证相对顺序
    var shell func(int, int)
    shell = func(begin, step int) {
        for i := begin + step; i < len(arr); i += step {
            if arr[i] < arr[i - step] {
                temp := arr[i]
                j := i - step
                for j >= begin && temp < arr[j] {
                    arr[j + step] = arr[j]
                    j -= step
                }
                arr[j + step] = temp
            }
        }
    }
    step := len(arr)/2
    for step > 0 {
        for i := 0; i < step; i++{
            shell(i, step)
        }
        step /= 2
    }
}

归并排序

GO实现
func MySort( arr []int ) []int {
    // 2 2 1 稳定
    if len(arr) < 2 {
        return arr
    }
    mid := len(arr)/2
    left := arr[:mid]
    right := arr[mid:]
    var merge func([]int, []int) []int
    merge = func(left []int, right []int)(ans []int){
        i := 0
        j := 0
        for i < len(left) && j < len(right){
            if left[i] <= right[j] {
                ans = append(ans, left[i])
                i++
            }else{
                ans = append(ans, right[j])
                j++
            }
        }
        ans = append(ans, left[i:]...)
        ans = append(ans, right[j:]...)
        return
    }
    return merge(MySort(left), MySort(right))
}

快速排序

GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 2,2,1 不稳定
    var quicSort func(int, int)
    quicSort = func(begin, end int) {
        if(end - begin <= 0){
            return
        }
        cur := arr[begin]
        left := begin
        right := end
        isRight := true
        for left != right {
            if isRight {
                if arr[right] < cur {
                    arr[left] = arr[right]
                    isRight = !isRight
                }else{
                    right--
                }
            } else {
                if arr[left] > cur {
                    arr[right] = arr[left]
                    isRight = !isRight
                }else{
                    left++
                }
            }
        }
        arr[left] = cur
        quicSort(begin, left - 1)
        quicSort(left + 1, end)
    }
    quicSort(0, len(arr) - 1)
}

堆排序

有两种建堆方式:从顶向下O(n)(已知堆的大小),从底向上O(nlogn)(堆的大小动态调整)
参考博文:【堆/排序】堆排序的两种建堆方法

GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 不稳定 2 2 1
    // 从小到大排序,用大顶堆,每次把根节点放最后,然后end - 1
    var down func(int, int) 
    down = func(start int, end int){
        for start < end {
            fmt.Println(start)
            left := 2 * start + 1
            right := 2 * start + 2
            if left > end {
                break
            }
            max := arr[left]
            if right <= end && arr[right] > max{
                max = arr[right]
            }
            if max > arr[start] {
                if max == arr[left] {
                    arr[start], arr[left] = arr[left], arr[start]
                    start = left
                } else {
                    arr[start], arr[right] = arr[right], arr[start]
                    start = right
                }
            }else{
                break
            }
        }
    }
    end := len(arr) - 1
    // 先建堆
    // end的父节点是:(end - 1)/2
    for i := (end - 1)/2; i >= 0; i-- {
        down(i, end)
    }
    fmt.Println(arr[end])
    // 再排序
    for end >= 1 {
        arr[0], arr[end] = arr[end], arr[0]
        end--
        down(0, end)
    }
}

非比较排序(基于桶排序思想)

计数排序(适合数据跨度小,重复数据多的情况)

相当于为每个数字安排一个桶

GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    minArr := math.MaxInt
    maxArr := -1
    for _, v := range arr {
        if minArr > v {
            minArr = v
        }
        if maxArr < v {
            maxArr = v
        }
    }
    record := make([]int, maxArr - minArr + 1)
    for _, v := range arr {
        record[v - minArr]++
    }
    cur := 0
    for i, v := range record {
        for v > 0 {
            arr[cur] = i + minArr
            cur++
            v--
        }
    }
}

基数排序(桶排序的变种)

一位一位的来处理数据,桶的数量固定为十个,桶间有序,桶内无序。
有两种处理方式:

  • 从最高位到最低位:每个桶内要再进行桶排序
  • 从最低位到最高位:只要调用最大数的最高位数次排序就行
GO实现
func MySort( arr []int ) []int {
    if len(arr) < 2 {
        return arr
    }
    // 找到最大值
    maxValue := -1
    for _, v := range arr {
        if maxValue < v {
            maxValue = v
        }
    }
    // 找到最高位
    maxBit := 0
    for maxValue != 0 {
        maxValue /= 10
        maxBit++
    }
    // fmt.Println(maxBit)
    // 声明十个桶
    buckets := make([][]int, 10)
    base := 1
    for i := 0; i < maxBit; i++ {
        for _, v := range arr {
            buckets[(v / base) % 10] = append(buckets[(v/base)%10], v)
        }
        index := 0
        for j, bucket := range buckets {
            if len(bucket) == 0 {
                // fmt.Println(len(bucket))
                continue
            }
            for _, v := range bucket{
                arr[index] = v
                index++
            }
            // 清空桶
            buckets[j] = buckets[j][:0]
        }
        base *= 10
    }
    return arr
}
tips

是不是很疑惑我为什么没写桶排序?文章来源地址https://www.toymoban.com/news/detail-642602.html

  • 要使用桶排序算法,首先要确定桶的数量,这一点就很麻烦
  • 由于桶内是无序的,所以往往还需要在桶内调用快排之类的基于比较的排序算法,所以我个人觉得桶排序不能算非比较排序,所以没有写

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

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

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

相关文章

  • 【数据结构与算法】内排序算法比较(C\C++)

    各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间,试通过随机的数据比较各算法的比较次数和移动次数,以取得直观感受。 对以下10种常用的内部排序算法进行比较:直接插入排序、折半插入排序、二路插入排序、希尔排序、

    2024年02月12日
    浏览(46)
  • 内部排序算法比较-数据结构C语言课设

    名称: 内部排序算法比较 内容: 在教科书中,各种内部排序算法的时间复杂的分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各种算法的比较次数和移动次数,以取得直观感受。 任务: (1)对以下7中常会用的内部排序算法进行比较

    2024年02月12日
    浏览(53)
  • 智能优化算法比较:常用的23组测试函数

    在智能优化算法的性能比较过程中,经常会需要用到一些测试函数,进行算法的性能比较。CEC(国际进化计算会议) 测试函数,常用的23组整理如下。

    2024年02月11日
    浏览(41)
  • 【算法】常用排序算法

    需要云服务器等云产品来学习Linux的同学可以移步/--腾讯云--/--阿里云--/--华为云--/官网,轻量型云服务器低至112元/年,新用户首次下单享超低折扣。 目录  一、常见排序算法  二、直接插入排序 1、直接插入排序思想 2、直接插入排序代码 二、希尔排序 1、希尔排序思想 2、

    2024年02月02日
    浏览(32)
  • C++,stl,常用排序算法,常用拷贝和替换算法

    目录 1.常用排序算法 sort random_shuffle merge reverse 2.常用拷贝和替换算法 copy replace replace_if swap 默认从小到大排序  使用的时候要加随机数种子            交换的容器要是同种类型

    2024年02月20日
    浏览(37)
  • 【数据结构与算法】常用排序算法对比

    常用排序算法对比 相关术语解释 : 稳定:如果 a 原本在 b 前面,而 a = b,排序之后 a 仍然在 b 的前面。 不稳定: 如果 a 原本在 b 前面,而 a = b,排序之后 a 可能出现在 b 的后面。 内排序:所有排序操作都在内存中完成。 外排序:由于数据太大,因此把数据放在磁盘中,而

    2024年02月15日
    浏览(45)
  • 常用排序算法的理解

    1.插入排序 插入排序的思想是将一个记录插入到已经排好序的有序表中,从而形成一个新的、记录数加1的有序表。在其实现过程使用双层循环,外层循环是进行插入的次数(也可以理解为比较的轮数),内层循环是当前记录查找插入有序表的位置,并进行移动(可以理解为每

    2024年02月07日
    浏览(34)
  • 软考——常用排序算法

    目录 1,直接插入排序 2,折半插入排序 3,希尔排序 4,冒泡排序 5,快速排序 6,简单选择排序 7,堆排序 8,归并排序  各种排序方法的特性 :   稳定性 : 若在待排序的一个序列中,Ri和Rj的关键码相同,即Ri=Rj,且在排序前Ri领先于Rj,那么当排序后,如果Ri和Rj的相对次序

    2024年02月06日
    浏览(30)
  • 常用的排序算法

    GO实现 另一种实现 GO实现 GO实现 GO实现 GO实现 GO实现 有两种建堆方式:从顶向下O(n)(已知堆的大小),从底向上O(nlogn)(堆的大小动态调整) 参考博文:【堆/排序】堆排序的两种建堆方法 GO实现 相当于为每个数字安排一个桶 GO实现 一位一位的来处理数据,桶的数量固定为十个

    2024年02月13日
    浏览(26)
  • 常用排序算法

    目录 直接插入排序 希尔排序 ​编辑 选择排序 堆排序 冒泡排序 快速排序 hoare版 挖坑法 前后指针法 非递归 归并排序 非递归 计数排序 直接插入排序跟依次模扑克牌一样,将最后一张牌依次与前面的牌比较,最后将牌插入到指定位置 单趟排序: 将最后一个数依次与前面的数

    2024年02月08日
    浏览(32)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包