首页 > 编程语言 >常见的排序算法——冒泡排序

常见的排序算法——冒泡排序

时间:2024-04-12 18:55:33浏览次数:27  
标签:__ ... 4.0 int 冒泡排序 算法 time 排序

本文记述了冒泡排序的基本思想和一份参考实现代码,并在说明了算法的性能后用随机数据进行了验证。

◆ 思想

(把水平陈列的数组逆时针旋转90°后,有助于理解后续的内容。)

将包含顶层以下的所有元素作为待排序范围,将该范围以上的所有元素作为已排序范围。通过一一比较相邻的两个元素,自底向上地将待排序范围内的最大元素放到顶层。然后将包含次顶层以下的所有元素作为待排序范围,重复以上的比较和交换,直至待排序范围中只剩一个元素为止。如要得到逆序的结果,则仅需改变比较的方向即可。

◆ 实现

排序代码采用《算法(第4版)》的“排序算法类模板”实现。(代码中涉及的基础类,如 Array,请参考算法文章中涉及的若干基础类的主要API

// bubble.hxx

...

class Bubble
{

    ...

    template
    <
        class _T,
        class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
    >
    static
    void
    sort(Array<_T> & a)
    {
        int N = a.size();
        for (int i = N-1; i > 0; --i)           // #1
            for (int j = 0; j < i; ++j)           // #2
                if (__less__(a[j+1], a[j]))
                    __exch__(a, j+1, j);
    }
    
    ...
    
    template
    <
        class _T,
        class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
    >
    static
    bool
    __less__(_T const& v, _T const& w)
    {
        return v.compare_to(w) < 0;         // #3
    }

    ...
    
    template
    <
        class _T,
        class = typename std::enable_if<std::is_base_of<Comparable<_T>, _T>::value>::type
    >
    static
    void
    __exch__(Array<_T> & a, int i, int j)
    {
        _T t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    ...

反复处理待排序范,直至待排序范围中只剩一个元素(#1)。通过一一比较相邻的两个元素,自底向上地将待排序范围内的最大元素放到顶层(#2)。将 '<' 改为 '>',即得到逆序的结果(#3)。

◆ 性能

时间复杂度 空间复杂度 是否稳定
N^2 1

◆ 验证

测试代码采用《算法(第4版)》倍率实验方案,用随机数据验证其正确性并获取时间复杂度数据。

// test.cpp
    
...

time_trial(int N)
{
    Array<Double> a(N);
    for (int i = 0; i < N; ++i) a[i] = Std_Random::random();    // #1
    Stopwatch timer;
    Bubble::sort(a);                     // #2
    double time = timer.elapsed_time();
    assert(Bubble::is_sorted(a));            // #3
    return time;
}

...

test(char * argv[])
{
    int T = std::stoi(argv[1]);          // #4
    double prev = time_trial(512);
    Std_Out::printf("%10s%10s%7s\n", "N", "Time", "Ratio");
    for (int i = 0, N = 1024; i < T; ++i, N += N) {            // #5
        double time = time_trial(N);
        Std_Out::printf("%10d%10.3f%7.1f\n", N, time, time/prev);   // #6
        prev = time;
    }
}

...

用 [0,1) 之间的实数初始化待排序数组(#1),打开计时器后执行排序(#2),确保得到正确的排序结果(#3)。整个测试过程要执行 T 次排序(#4)。每次执行排序的数据规模都会翻倍(#5),并以上一次排序的时间为基础计算倍率(#6),

此测试在实验环境一中完成,

$ g++ -std=c++11 test.cpp std_out.cpp std_random.cpp stopwatch.cpp type_wrappers.cpp

$ ./a.out 8

     N      Time  Ratio
  1024     0.298    4.1
  2048     1.187    4.0
  4096     4.731    4.0
  8192    18.910    4.0
 16384    75.692    4.0
 32768   303.032    4.0
 65536  1211.159    4.0
131072  4874.049    4.0

可以看出,随着数据规模的成倍增长,排序所花费的时间将是上一次规模的 4 倍。将数据反映到以 2 为底数的对数坐标系中,可以得到如下图像,

test_data

O(N^2) 代表了平方级别复杂度下的理论排序时间,该行中的数据是以 Time 行的第一个数据为基数逐一乘 4 后得到的结果(因为做的是倍率实验,所以乘 (2)^2 即 4)。

◆ 最后

完整的代码请参考 [gitee] cnblogs/18131080

写作过程中,笔者参考了《算法(第4版)》一书中的“排序算法类模板”和倍率实验。致作者 Sedgwick,Wayne 及译者谢路云。

标签:__,...,4.0,int,冒泡排序,算法,time,排序
From: https://www.cnblogs.com/green-cnblogs/p/18131080

相关文章

  • Java如何自行实现正向地理编码算法(不依赖api,不联网)
    政务场景中经常会遇到地址落图,或者三维挂接的场景。如何将文本地址转化为gps坐标是实现要解决的核心问题。addresstool为正向地理编码提供了非常简单、高效的算法。如何实现正向地理编码,只需要3步就行:第一步:带有坐标的标准地址加载到addresstool中。第二部:以业务地址作为参数,使......
  • TSINGSEE青犀AI智能分析网关V4叉车载货出入库检测算法介绍及应用
    随着物流行业的快速发展,叉车作为物流运输的重要设备,其安全性和效率性越来越受到人们的关注。然而,在实际操作中,由于人为因素和操作环境的复杂性,叉车事故时有发生,给企业和个人带来了巨大的损失。为了提高叉车运输的安全性和效率,近年来,人工智能技术逐渐应用于叉车运输领域,其中,叉车载......
  • 算法技巧_二叉树
    算法技巧(二叉树)目录算法技巧(二叉树)两种解题思路最简单的遍历二叉树代码遍历二叉树的方式前中后序遍历的区别以及各自场景技巧典型问题常见题目以及解题思路两种解题思路遍历一遍树是否可以解决问题如果可以,用一个traverse函数配合外部变量来实现。分解问题是否可以定......
  • TSINGSEE青犀AI智能分析网关V4人员睡岗检测算法介绍及应用
    人员睡岗AI算法是一种通过人工智能技术来检测和预警人员是否处于睡眠状态的算法。它主要通过分析人员的行为、姿势和身体特征等信息来判断人员是否已经进入睡眠状态。该算法通过对监控摄像头捕捉的画面进行实时分析,利用卷积神经网络(CNN)对图像进行特征提取,进而判断画面中的人员是否......
  • TSINGSEE青犀AI智能分析网关V4吸烟/抽烟检测算法介绍及应用
    抽烟检测AI算法是一种基于计算机视觉和深度学习技术的先进工具,旨在准确识别并监测个体是否抽烟。该算法通过训练大量图像数据,使模型能够识别出抽烟行为的关键特征,如烟雾、手部动作和口部形态等。在原理上,抽烟检测AI算法主要依赖卷积神经网络(CNN)进行图像特征提取和分类。CNN能够自......
  • 常用快排算法实现
    快速排序voidquick_sort(intq[],intl,intr){if(l>=r)return;inti=l-1,j=r+1,x=q[l+r>>1];while(i<j){doi++;while(q[i]<x);doj--;while(q[j]>x);if(i<j)......
  • Java stream sorted使用 Comparator 进行多字段排序
    摘要:介绍使用JavaStream流排序器Comparator对List集合进行多字段排序的方法,包括复杂实体对象多字段升降序混合排序方法。综述​ Java8的Stream使用了函数式编程模式,人如其名,它可以被用来对集合或数组进行链状流式的排序、过滤和统计等操作,从而让我们更方便的对集合或数组......
  • lloyd-max 最优标量量化算法分析
    变限积分求导公式假设有函数定义为:\[K(x)=\int_{\phi(x)}^{\Psi(x)}f(t)dt\\\frac{dK(x)}{dx}=f[\Psi(x)]\Psi(x)^{\prime}-f[\phi(x)]\phi(x)^{\prime}\]量化失真与最优标量量化对于N个量化区间的失真定义为:\[D=\sum_{i=1}^{N}(\int_{t_i}^{t_{i+1}}(x-\hat{x_i......
  • OR-TOOL 背包算法
    起因:最近公司要发票自动匹配,比如财务输入10000W块,找到发票中能凑10000的。然后可以快速核销。 废话不多, 一官方文档https://developers.google.cn/optimization/pack/knapsack?hl=zh-cn 二POM文件<!--google算法包--><dependency><......
  • 补充:基于项目的协同过滤推荐算法(Item-Based Collaborative Filtering Recommendation
    前言继续上篇博客,继续读论文。想看上篇论文的同学可以点击这里相关工作Inthissectionwebrieflypresentsomeoftheresearchliteraturerelatedtocollaborativefiltering,recommendersystems,dataminingandpersonalization.在本节中,我们简要介绍了一些与协同......