排序算法性能分析

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

目录

实现插入排序、冒泡排序、选择排序、合并排序、快速排序算法(从小到大)

①插入排序

②冒泡排序

③选择排序

⑥快速排序

五种排序

现在有10亿的数据(每个数据四个字节),请快速挑选出最大的十个数,并在小规模数据上验证算法的正确性。

方法一:规模为10的插入排序

方法二:规模为10的堆排序


实现插入排序、冒泡排序、选择排序、合并排序、快速排序算法(从小到大)

首先介绍各个排序算法的设计思路以及给出各个算法的伪代码,再通过伪代码具体实现每个排序算法。

①插入排序

设计思路:

假设前N-1个数已经是有序序列了,那么将第N个数插入其中仍使其有序的方法是依次和前N-1个数进行比较,找到合适的位置安放即可。

开始时,将第一个数作为有序序列,先从第2个数开始插入,重复操作,直到排序完成。

将1,2,3,4,4,9作为插入排序的例子,如图1所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图1 插入排序图示

伪代码:

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

matlab代码

result=[];
for power=1:5
    scale=power*10000;
    count=0;
    for times=1:20
        number=randi(scale,1,scale);
        tic;
        for i=1:scale-1
            for j=i+1:-1:2
                if number(j)>number(j-1)
                    break
                else
                    temp=number(j);
                    number(j)=number(j-1);
                    number(j-1)=temp;
                end
            end
        end
        count=count+toc;           
    end
    count=count/20;
    result=[result,count];
end

算法复杂度分析:

最坏时间复杂度:O(n^2)

最好时间复杂度:O(n)

平均时间复杂度:O(n^2)

实际效率:

随机生成数据规模分别为10000,20000,30000,40000,50000的测试数据,每个数据规模记录20组的平均排序时间,数据记录如表1所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

表1 插入排序

其中取第一个实验值作为理论值基准计算出理论值,如图2所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图2 插入排序

解释与分析:

由图2可知,在不同的数据规模下,插入排序的实验数据和理论计算基本一致。

②冒泡排序

设计思路:

比较相邻两个元素的大小,如果大小顺序不对则交换位置,这样一趟下来,最大的或者最小的就可以被分离出来,如此重复下去,直到排序完成。

将8,16,21,25,27,49作为冒泡排序的例子,如图3所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图3 冒泡排序图示

伪代码:

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

matlab代码

result=[];
for power=1:5
    scale=power*100;
    count=0;
    for times=1:20
        number=randi(scale,1,scale);
        tic;
        for i=scale:-1:1
            for j=1:i-1
                if number(j)>number(j+1)
                    temp=number(j);
                    number(j)=number(j+1);
                    number(j+1)=temp;
                end
            end
        end
        count=count+toc;           
    end
    count=count/20;
    result=[result,count];
end

算法复杂度分析:

最坏时间复杂度:O(n^2)

最好时间复杂度:O(n^2)

平均时间复杂度:O(n^2)

实际效率:

随机生成数据规模分别为10000,20000,30000,40000,50000的测试数据,每个数据规模记录20组的平均排序时间,数据记录如表2所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

表2 冒泡排序

其中取第一个实验值作为理论值基准计算出理论值,如图4所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图4 冒泡排序

解释与分析:

由图4可知,冒泡排序的实验数据比理论计算要大,并且随着数据规模的增大,这个差距也在增大,初步分析是数据规模小,所取的理论值基准较小,加上运行环境影响所致。

③选择排序

设计思路:

每次在序列中找出最小的元素,将它与第一个元素交换位置,接着找剩下序列中最小的元素,将它与第二个元素交换位置,如此重复,直到排序完成。

将8,16,21,25,27,49作为选择排序的例子,如图5所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图5 选择排序图示

伪代码:

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

matlab代码

result=[];
for power=1:5
    scale=power*10000;
    count=0;
    for times=1:20
        number=randi(scale,1,scale);
        tic;
        for i=1:scale-1
            for j=i+1:scale
                if number(i)>number(j)
                    temp=number(j);
                    number(j)=number(i);
                    number(i)=temp;
                end
            end
        end
        count=count+toc;           
    end
    count=count/20;
    result=[result,count];
end

算法复杂度分析:

最坏时间复杂度:O(n^2)

最好时间复杂度:O(n^2)

平均时间复杂度:O(n^2)

实际效率:

随机生成数据规模分别为10000,20000,30000,40000,50000的测试数据,每个数据规模记录20组的平均排序时间,数据记录如表3所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

表3 选择排序

其中取第一个实验值作为理论值基准计算出理论值,如图6所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图6 选择排序

解释与分析:

由图6可知,在不同的数据规模下,选择排序的实验数据和理论计算基本一致。

(4)归并排序

设计思路:

把序列分成很多的子序列,先每两个元素合并成一个有序序列,再每四个元素合并成一个有序序列,如此下去,直到整个序列有序。

将8,16,21,25,25*,49作为归并排序的例子,如图7所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图7 归并排序图示

伪代码:

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

matlab代码

result=[];
for power=1:5
    scale=power*100000;
    count=0;
    for times=1:20
        number=randi(scale,1,scale);
        done=zeros(1,scale);
        tic;
        step=1;
%         number=MergeSort(1,scale,number,done);
        while step<scale
            for low=1:2*step:scale
                mid=low+step-1;
                if mid>scale
                    break
                end
                high=low+2*step-1;
                if high>scale
                    high=scale;
                end
                done=Merge(low,mid,high,number,done);
            end
            step=step*2;
            number=done;
        end
        count=count+toc;           
    end
    count=count/20;
    result=[result,count];
end
% function[number]=MergeSort(low,high,number,done)
%     if low<high
%         mid=floor((low+high)/2);
%         number=MergeSort(low,mid,number,done);
%         number=MergeSort(mid+1,high,number,done);
%         number=Merge(low,mid,high,number,number);
%     end
% end
function[done]=Merge(low,mid,high,number,done)
    i=low;
    j=mid+1;
    k=low;
    while i<=mid&&j<=high
        if number(i)<=number(j)
            done(k)=number(i);
            i=i+1;
        else
            done(k)=number(j);
            j=j+1;
        end
        k=k+1;
    end
    while i<=mid
        done(k)=number(i);
        k=k+1;
        i=i+1;
    end
    while j<=high
        done(k)=number(j);
        k=k+1;
        j=j+1;
    end
end

算法复杂度分析:

最坏时间复杂度:O(nlogn)

最好时间复杂度:O(nlogn)

平均时间复杂度:O(nlogn)

实际效率:

随机生成数据规模分别为10000,20000,30000,40000,50000的测试数据,每个数据规模记录20组的平均排序时间,数据记录如表4所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

表4 归并排序

其中取第一个实验值作为理论值基准计算出理论值,如图8所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图8 归并排序

解释与分析:

由图8可知,归并排序的实验数据比理论计算要大,并且随着数据规模的增大,这个差距也在增大,初步分析是数据规模较小,所取的理论值基准较小,加上运行环境影响所致。

⑥快速排序

设计思路:

先取一个中轴元素,比如第一个元素,然后根据这个中轴元素将序列分成两个子序列,一个子序列里面的元素都比中轴元素小,另一个子序列里面的元素都比中轴元素大,然后再对子序列进行这样的操作,如此重复,直到排序完成。

将8,16,21,25,25*,49作为快速排序的例子,如图9所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图9

伪代码:

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

matlab代码

result=[];
for power=1:5
    scale=power*10000;
    count=0;
    for times=1:20
        number=randi(scale,1,scale);
        tic;
        number=Quick(1,scale,number);
        count=count+toc;           
    end
    count=count/20;
    result=[result,count];
end
function[number]=Quick(low,high,number)
    i=low;
    j=high;
    pivot=number(low);
    while low<high
        while low<high&&pivot<=number(high)
            high=high-1;
        end
        if low<high
            number(low)=number(high);
            low=low+1;
        end
        while low<high&&pivot>number(low)
            low=low+1;
        end
        if low<high
            number(high)=number(low);
            high=high-1;
        end
    end
    number(low)=pivot;
    if i<low-1
        number=Quick(i,low-1,number);
    end
    if high+1<j
        number=Quick(high+1,j,number);
    end
end

算法复杂度分析:

最坏时间复杂度:O(n^2)

最好时间复杂度:O(nlogn)

平均时间复杂度:O(nlogn)

实际效率:

随机生成数据规模分别为10000,20000,30000,40000,50000的测试数据,每个数据规模记录20组的平均排序时间,数据记录如表5所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

表5 快速排序

其中取第一个实验值作为理论值基准计算出理论值,如图10所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图10 快速排序

解释与分析:

由图10可知,快速排序的实验数据比理论计算要小,初步分析是数据规模小,所取的理论值基准较小,加上运行环境影响所致。

五种排序

以上五种排序实际运行效率如图11所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图11 五种排序比较

由图可以看出五种排序实际效率最快的是平均时间复杂度为O(nlogn)的快速排序和归并排序,然后是最优时间复杂度为O(n)的插入排序,最后是时间复杂度均为O(n^2)的冒泡排序和选择排序。

现在有10亿的数据(每个数据四个字节),请快速挑选出最大的十个数,并在小规模数据上验证算法的正确性。

算法设计思路:

对于10亿个数据从中挑选出最大的十个数,对10亿个数全部进行排序的方法显然不可取,可以通过选择排序或者冒泡排序进行10趟排序,但是这样需要进行的操作次数大概是100亿次,这里我们采取别的方法。

方法一:规模为10的插入排序

我们首先对前10个数进行降序排序,这样末尾的数是前10个数中最小的数,此后遍历剩下的10亿-10个数,对每一个数都和前10个数进行一趟插入排序,最少比较次数为1次,最多比较次数为10次,这样需要进行的操作次数大概是55亿次,比冒泡排序和选择排序减少了近一半的操作次数。

matlab代码

result=[];
for power=1:1
    scale=power*1000000000;
    count=0;
    for times=1:20
        numbers=randi(scale,1,scale);
        number=numbers(1,1:10);
        tic;
        for i=1:9
            for j=i+1:-1:2
                if number(j)<number(j-1)
                    break
                else
                    temp=number(j);
                    number(j)=number(j-1);
                    number(j-1)=temp;
                end
            end
        end
        for i=11:scale
            for j=10:-1:1
                if number(j)>=numbers(i)
                    break
                else
                    if j<10
                        number(j+1)=number(j);
                    end
                    number(j)=numbers(i);
                end
            end
        end      
        count=count+toc;           
    end
    count=count/20;
    result=[result,count];
end

实际表现:

取数据规模为100W,200W,300W,400W,500W作为测试数据,每个数据规模测试20组,记录平均运行时间,如图12所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图12 规模为10的插入排序

测试一些大数据的运行时间(20组平均时间)如下:

一千万:0.0390s

五千万:0.1832s

一亿:0.3727s

五亿:1.8612s

十亿:5.6923s

方法二:规模为10的堆排序

方法一的规模为10的插入排序效率已经比较高了,但是仍有不足,即将10个最大的数也进行了排序,而实际上只需要将它们挑选出来即可,考虑建立规模为10的堆排序,这样最小比较次数为1次,但最大比较次数降到了3次,挑出10个最大的数理论上大概需要进行20亿次的操作即可。

matlab代码 

result=[];
for power=1:1
    scale=power*1000000000;
    count=0;
    for times=1:20
        numbers=randi(scale,1,scale);
        number=numbers(1,1:10);
        tic;
        for i=5:-1:1
            number=Adjust(i,10,number);
        end
        for i=11:scale
            if numbers(i)>number(1)
                number(1)=numbers(i);
                number=Adjust(1,10,number);
            end
        end      
        count=count+toc;           
    end
    count=count/20;
    result=[result,count];
end
function[number]=Adjust(i,m,number)
    temp=number(i);
    j=2*i;
    while j<=m
        if j<m&&number(j)>number(j+1)
            j=j+1;
        end
        if number(j)>=temp
            break
        end
        number(i)=number(j);
        i=j;
        j=j*2;
    end
    number(i)=temp;
end
% function[number]=HeapSort(number,scale)
%     for i=scale:-1:2
%         temp=number(1);
%         number(1)=number(i);
%         number(i)=temp;
%         number=Adjust(1,i-1,number);
%     end
% end

实际表现:

取数据规模为100W,200W,300W,400W,500W作为测试数据,每个数据规模测试20组,记录平均运行时间,与插入排序相比,效率明显提升,如图13所示。

排序算法性能分析,算法设计与分析,排序算法,算法,数据结构

图13 规模为10的堆排序

测试一些大数据的运行时间(20组平均时间)如下:

一千万:0.0201s

五千万:0.1059s

一亿:0.2001s

五亿:1.0711s

十亿:4.6140s文章来源地址https://www.toymoban.com/news/detail-536935.html

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

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

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

相关文章

  • 算法性能分析

          时间复杂度是一个函数,它定性描述该算法的运行时间。假设算法的问题规模为n,那么操作单元数量便用函数f(n)来表示,随着数据规模n的增大,算法执行时间的增长率和f(n)的增长率相同,这称作为算法的渐近时间复杂度,简称时间复杂度,记为 O(f(n)) 算法导论给出的

    2024年02月08日
    浏览(65)
  • 【精选论文 | Capon算法与MUSIC算法性能的比较与分析】

    本文编辑:调皮哥的小助理 【正文】 首先说结论: 当信噪比(SNR)足够大时,Capon算法和MUSIC算法的空间谱非常相似,因此在SNR比较大时它们的性能几乎一样,当不同信号源的入射角度比较接近时,MUSIC算法的性能优于Capon,这也是MUSIC算法(或者说子空间类算法)被称为高分

    2024年02月11日
    浏览(66)
  • 【海量数据挖掘/数据分析】之 决策树模型(决策树模型、决策树构成、决策树常用算法、决策树性能要求、信息增益、信息增益计算公式、决策树信息增益计算实例)

    目录 【海量数据挖掘/数据分析】之 决策树模型(决策树模型、决策树构成、决策树常用算法、决策树性能要求、信息增益、信息增益计算公式、决策树信息增益计算实例) 一、决策树模型 1、常用算法 2、属性划分策略 3、其他算法 三、决策树算法性能要求 四、 决策树模型

    2024年02月13日
    浏览(58)
  • 【数据结构】——常见排序算法(演示图+代码+算法分析)

    目录 1.  常见排序算法 1.2 稳定性 2.  常见排序算法的实现 2.1 插入排序 2.1.1基本思想 2.1.2代码 2.1.4算法分析  2.2 希尔排序 2.2.1基本思想 2.2.2代码 2.2.3演示图  2.2.4算法分析 2.3 选择排序 2.3.1基本思想 2.3.2代码 2.3.3演示图 2.3.4算法分析 2.4 堆排序 2.4.1基本思想  2.4.2代码 2.4.3演示

    2024年02月11日
    浏览(73)
  • Python 进阶指南(编程轻松进阶):十三、性能测量和大 O 算法分析

    原文:http://inventwithpython.com/beyond/chapter13.html 对于大多数小程序来说,性能并不那么重要。我们可能会花一个小时编写一个脚本来自动执行一个只需要几秒钟就能运行的任务。即使需要更长的时间,当我们端着一杯咖啡回到办公桌时,这个项目也可能已经完成了。 有时候花时

    2023年04月09日
    浏览(46)
  • 【数据结构】排序算法的稳定性分析

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 前言: 前面我们已经

    2024年02月08日
    浏览(60)
  • MySQL进阶篇:索引(概述,结构,分类,语法,SQL性能分析,索引使用,设计原则)

    索引(index)是帮助MysQL 高效获取数据的数据结构 ( 有序 )。 在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法,这种数据结构就是索引。 优缺点: MySQL的索引是在存储

    2024年01月20日
    浏览(51)
  • ⑩② 【MySQL索引】详解MySQL`索引`:结构、分类、性能分析、设计及使用规则。

    个人简介:Java领域新星创作者;阿里云技术博主、星级博主、专家博主;正在Java学习的路上摸爬滚打,记录学习的过程~ 个人主页:.29.的博客 学习社区:进去逛一逛~ 索引 : 什么是索引(index) ? 索引(index)是帮助MySQL 高效获取数据的数据结构 (有序):在数据之外,数据库系统

    2024年02月05日
    浏览(51)
  • 你真的会性能测试吗?性能测试需求分析,从业务到数据(详细)...

    产品需求 业务场景: 一个问卷调查的功能,然后产品和业务会不定时通过前端界面去根据筛选条件查询相关问卷问题的答案明细,但是觉得很慢,让测试这边给出一个指标。 系统架构: MySQL数据库,所有问卷问题相关的数据都存储在同一张表,单台服务器,无缓存,通过一

    2024年02月10日
    浏览(60)
  • 数据结构实验任务八:排序算法的实现与分析

    问题描述 统计成绩:给出 n 个学生的考试成绩表,每条信息由姓名和分数组成,试设 计一个算法: 1.按分数高低次序,打印出每个学生在考试中获得的名次,分数相同的为同 一名次; 2.按名次列出每个学生的姓名与分数。 输入要求 输入 n+1 行,前 n 行是 n 个学生的信息(姓

    2024年02月04日
    浏览(69)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包