常用的排序算法

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

总结

常用的排序算法

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

冒泡排序

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日
    浏览(49)
  • 内部排序算法比较-数据结构C语言课设

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

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

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

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

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

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

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

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

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

    2024年02月15日
    浏览(48)
  • 几大常用的排序算法

    直接插入排序是一种简单的插入排序法,其基本思想是: 在待排序的元素中,假设 第一个元素已有序 ,现将后面的元素与第一个元素作比较,比第一个元素小插入到前面已经排好的序列中,使得前面的元素有序。按照此法对所有元素进行插入,直到整个序列有序为止 动图演

    2024年03月17日
    浏览(39)
  • 【C++】常用排序算法

    2024年02月09日
    浏览(34)
  • 常用排序算法汇总

    内部排序 将所有数据加载到内部存储器中排序 外部排序 数据量过大,需要借助外部存储进行排序 时间复杂度 是用来描述算法运行时间的,那么该如何估计程序运行时间呢,通常会估算算法的操作单元数量来代表程序消耗的时间,也可以这样考虑,时间复杂度就是操作一个

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

    归并排序的时间复杂度为O(nlogn),在使用递归程序时,其额外空间复杂度为O(nlogn) 归并排序使用了一种叫做分而治之(Divide and conquer)的策略,将原本很庞大的数组排序问题分割成更小的子问题,在每一个子问题得到解决后,再合并它们。下面我们以数组arr[8]={9,2,4,6,3,

    2024年01月25日
    浏览(26)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包