C语言冒泡排序法的简单程序
更新时间:2023-10-04 05:37:01 阅读量: 综合文库 文档下载
求一个C语言冒泡排序法的简单程序 悬赏分:50 - 解决时间:2007-9-4 11:16 我不明白怎么写 随便给我个就行 谢谢了
提问者: redangel0002 - 助理 二级
最佳答案
main() {
int i,j,temp; int a[10]; for(i=0;i<10;i++) scanf (\ for(j=0;j<=9;j++) { for (i=0;i<10-j;i++) if (a[i]>a[i+1]) { temp=a[i]; a[i]=a[i+1]; a[i+1]=temp;} }
for(i=1;i<11;i++) printf(\ printf(\ }
-------------- 冒泡算法
冒泡排序的算法分析与改进
交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。
冒泡排序
1、排序方法
将被排序的记录数组R[1..n]垂直排列,每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R:凡扫描到违反本原则的轻气泡,就使其向上\飘浮\。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。 (1)初始 R[1..n]为无序区。
(2)第一趟扫描
从无序区底部向上依次比较相邻的两个气泡的重量,若发现轻者在下、重者在上,则交换二者的位置。即依次比较(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);对于每对气泡(R[j+1],R[j]),若R[j+1].key 则交换R[j+1]和R[j]的内容。 第一趟扫描完毕时,\最轻\的气泡就飘浮到该区间的顶部,即关键字最小的记录被放在最高位置R[1]上。 (3)第二趟扫描 扫描R[2..n]。扫描完毕时,\次轻\的气泡飘浮到R[2]的位置上…… 最后,经过n-1 趟扫描可得到有序区R[1..n] 注意: 第i趟扫描时,R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时,该区中最轻气泡飘浮到顶部位置R上,结果是R[1..i]变为新的有序区。 2、冒泡排序过程示例 对关键字序列为49 38 65 97 76 13 27 49的文件进行冒泡排序的过程 3、排序算法 (1)分析 因为每一趟排序都使有序区增加了一个气泡,在经过n-1趟排序之后,有序区中就有n-1个气泡,而无序区中气泡的重量总是大于等于有序区中气泡的重量,所以整个冒泡排序过程至多需要进行n-1趟排序。 若在某一趟排序中未发现气泡位置的交换,则说明待排序的无序区中所有气泡均满足轻者在上,重者在下的原则,因此,冒泡排序过程可在此趟排序后终止。为此,在下面给出的算法中,引入一个布尔量exchange,在每趟排序开始前,先将其置为FALSE。若排序过程中发生了交换,则将其置为TRUE。各趟排序结束时检查exchange,若未曾发生过交换则终止算法,不再进行下一趟排序。 (2)具体算法 void BubbleSort(SeqList R) { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序 int i,j; Boolean exchange; //交换标志 for(i=1;i exchange=FALSE; //本趟排序开始前,交换标志应为假 for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描 if(R[j+1].key R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元 R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE; //发生了交换,故将交换标志置为真 } if(!exchange) //本趟排序未发生交换,提前终止算法 return; } //endfor(外循环) } //BubbleSort 4、算法分析 (1)算法的最好时间复杂度 若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值: Cmin=n-1 Mmin=0。 冒泡排序最好的时间复杂度为O(n)。 (2)算法的最坏时间复杂度 若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值: Cmax=n(n-1)/2=O(n2) Mmax=3n(n-1)/2=O(n2) 冒泡排序的最坏时间复杂度为O(n2)。 (3)算法的平均时间复杂度为O(n2) 虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均时间性能比直接插入排序要差得多。 (4)算法稳定性 冒泡排序是就地排序,且它是稳定的。 5、算法改进 上述的冒泡排序还可做如下的改进: (1)记住最后一次交换发生位置lastExchange的冒泡排序 在每趟扫描中,记住最后一次交换发生的位置lastExchange,(该位置之前的相邻记录均已有序)。下一趟排序开始时,R[1..lastExchange-1]是有序区,R[lastExchange..n]是无序区。这样,一趟排序可能使当前有序区扩充多个记录,从而减少排序的趟数。具体算法【参见习题】。 (2) 改变扫描方向的冒泡排序 ①冒泡排序的不对称性 能一趟扫描完成排序的情况: 只有最轻的气泡位于R[n]的位置,其余的气泡均已排好序,那么也只需一趟扫描就可以完成排序。 【例】对初始关键字序列12,18,42,44,45,67,94,10就仅需一趟扫描。 需要n-1趟扫描完成排序情况: 当只有最重的气泡位于R[1]的位置,其余的气泡均已排好序时,则仍需做n-1趟扫描才能完成排序。 【例】对初始关键字序列:94,10,12,18,42,44,45,67就需七趟扫描。 ②造成不对称性的原因 每趟扫描仅能使最重气泡\下沉\一个位置,因此使位于顶端的最重气泡下沉到底部时,需做n-1趟扫描。 ③改进不对称性的方法 在排序过程中交替改变扫描方向,可改进不对称性。 回答者:cicihsk - 助理 二级 9-4 11:08 评价已经被关闭 目前有 4 个人评价 好 75% (3) 不好 25% (1) 其他回答 共 3 条 main() {int i,j,n,a[10]; printf(\输入10个数:\ for(i=0;i<10;i++) scanf(\记得输入的时候后面加“,” for(i=0;i if(a[i]>a[j]) //改成(a[i] printf(\由小到大排序结果为:\); for(i=0;i<10;i++) printf(\ } 转载自 非常代码网 /* Function Prototypes */ void BubbleSort( int Array[], const int Size ); void PrintArray( int Array[], const int Size ); int main( void ) { int i; const int Size = 20; int Array[ Size ]; /* Fill the Array with random values between 0 and 99 */ for( i = 0; i < Size; i++ ) Array[i] = random() % 100; /* Print the Random Array to Screen */ 回答者:TANK006 - 经理 四级 9-4 11:06 clrscr(); printf( \ PrintArray( Array, Size ); /* Wait for key Press... */ printf( \ getch(); /* Sort the Array using Bubble Sort */ BubbleSort( Array, Size ); /* Print the Smallest-to-Largest Order Array */ clrscr(); printf( \ PrintArray( Array, Size ); /* End the Program */ printf( \ getch(); return 0; } /* Uses the classic bubble sort algorithm */ void BubbleSort( int Array[], const int Size ) { int i, j, temp; for( i = 0; i < Size - 1; i++ ) for( j = 0; j < Size - i + 1; j++ ) if( Array[j] > Array[j + 1] ) { temp = Array[j]; Array[j] = Array[j + 1]; Array[j + 1] = temp; } } /* Prints an integer Array line by line */ void PrintArray( int Array[], const int Size ) { int i; for( i = 0; i < Size; i++ ) printf(\
正在阅读:
C语言冒泡排序法的简单程序10-04
观看《第一书记》心得体会优选参考模板08-16
24.2.1直线和圆的位置关系106-09
爱心作文800字04-01
铁路工程概预算与工程量计算规则培训08-12
湖北省宜昌市高中英语Unit5Thepowerofnature课课练二无答案新人04-13
国家安监总局88号令安全生产考试试题11-30
皖价服函〔2013〕29省物价局关于重新核定交通建设工程试验检测收费标准的函号解析 - 图文09-20
管理会计应用中存在的问题及对策03-13
侧柏的栽植技术03-10
- 冀教版版五年级科学下册复习资料
- 微生物学复习提纲
- 2013—2014学年小学第二学期教研组工作总结
- 国有土地转让委托服务合同协议范本模板
- 我的固废说明书
- 企业管理诊断报告格式
- 东鼎雅苑施工组织设计
- 谈谈如何做好基层党支部书记工作
- 浮梁县环保局市级文明单位创建工作汇报
- 管理学基础知识
- 大学物理实验报告23 - PN结温度传感器特性1
- 计算机网络实践
- 酒桌上这四种情况下要坐牢,千万别不当回事……
- 国家康居示范工程建设技术要点
- 中国贴布行业市场调查研究报告(目录) - 图文
- 新课标下如何在高中物理教学中培养学生的创新能力初探
- 营养师冬季养生食谱每日一练(7月4日)
- 关注江西2017年第3期药品质量公告
- 建设海绵城市专题习题汇总
- 10万吨年环保净水剂建设项目报告书(2).pdf - 图文
- 冒泡
- 排序
- 语言
- 简单
- 程序
- 全新版大学英语综合教程4课文原文加翻译
- 频点与频段的换算
- 英语复习资料
- 安徽医科大学教职工出国(境)管理实施细则
- 2018造价实习周记4篇
- 北师大版五年级数学上册 数学好玩练习题(2018年秋)
- 第六章采煤技术
- MATLAB程序设计
- 高三下期化学第一次周考
- 易经十讲
- 七年级思想品德(上)人教版新课标单元练习
- ACE计轴事件诊断代码表
- 江苏省东海高级中学期中试卷
- 卫校综合楼(学生公寓)(教学楼)施工组织设计
- 黑龙江科技学院02年工程流体力学试题与答案
- 2019年高考地理热点题型和提分秘籍专题06 光照图的判读与晨昏线应用(题型专练) 含解析
- 陕西师范大学体育运动会精神文明奖、优秀组织奖评选细则(最终)
- 第28章 卵巢性索-间质肿瘤- Welcome to Zheng-GYN
- 组工干部如何做好组工信息工作(资料收集)
- PP中文标准教材(最终装配计划与执行) - 图文