博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【算法-排序之一】冒泡排序
阅读量:5830 次
发布时间:2019-06-18

本文共 889 字,大约阅读时间需要 2 分钟。

hot3.png

算法-排序之冒泡排序

      
         如果数据按照一定的顺序进行排序,数据处理的效率将显著的提高。算法是编程的精髓,一个高效而合适的算法能极大的减少时间消耗与空间消耗,提到“合适”是因为没有哪个算法可以在所有情况下都表现出色,同样是排序,在不同数据规模下各种排序算法有不同的效能表现,选择合适的解决算法的才能最大限度地提高效率。
         1.冒泡算法BubbleSort是常用排序算法之一,它的核心是让大(或小)的数据像水泡一样冒到最上端,这是通过不断地比较两个相邻数据的大小,前者大于后者则交换位置来实现冒泡。
          如下示例:
          
          图解如下:
                                            排序一遍后变成   
                                     依次类推,效果犹如把最大数“冒”上去。
            需要注意的细节是,对于n个数据,只需要排n-1次,故控制排序遍数的i起始值为1而不是0.在每次排序中,上次排好的数不需要再进行比较,故控制每次排序结束位置变了j的上限是num-i,随着排序次数i增加,需要排序的位置越靠前。
 
void BubbleSort ( int Array [], int num ){
int i ; //i控制排序的遍数
int j ; //j控制每次排序结束的位置
int temp ;
for ( i = 0 ; i < num ; i ++ ){
for ( j = 1 ; j < num - i ; j ++ ){
if ( Array [ j - 1 ] > Array [ j ]){
temp = Array [ j - 1 ];
Array [ j - 1 ] = Array [ j ];
Array [ j ] = temp ;
}
}
}
}
BuBBleSort.c
 
              
2. 
时间复杂度
           冒泡排序的主要时间消耗是比较,第一趟序比较n-1次,随后依次递减n-2....1,则总比较(n-1)+(n-2)+...+3+2+1=(n*2-n)/2,故其时间复杂度为O(n*2).
           3.空间复杂度
           整个排序过程需要一个temp的空间用于交换数据,故为空间复杂度为O(1).
           

转载于:https://my.oschina.net/winnsay/blog/633509

你可能感兴趣的文章
Linux/windows P2V VMWare ESXi
查看>>
Windows XP倒计时到底意味着什么?
查看>>
tomcat一步步实现反向代理、负载均衡、内存复制
查看>>
运维工程师在干什么学些什么?【致菜鸟】
查看>>
Linux中iptables详解
查看>>
java中回调函数以及关于包装类的Demo
查看>>
maven异常:missing artifact jdk.tools:jar:1.6
查看>>
终端安全求生指南(五)-——日志管理
查看>>
Nginx 使用 openssl 的自签名证书
查看>>
创业维艰、守成不易
查看>>
PHP环境安装套件:快速安装LAMP环境
查看>>
CSS3
查看>>
ul下的li浮动,如何是ul有li的高度
查看>>
C++ primer plus
查看>>
python mysqlDB
查看>>
UVALive 3942 Remember the Word Tire+DP
查看>>
从微软的DBML文件中我们能学到什么(它告诉了我们什么是微软的重中之重)~目录...
查看>>
被需求搞的一塌糊涂,怎么办?
查看>>
c_数据结构_队的实现
查看>>
jquery 选择器总结
查看>>