《C语言冒泡排序法的简单程序》由会员分享，可在线阅读，更多相关《C语言冒泡排序法的简单程序（3页珍藏版）》请在金锄头文库上搜索。
1、求一个C语言冒泡排序法的简单程序養悬赏分:50-解决时间：2007-9-411:16我不明白怎么写随便给我个就行谢谢了提问者：redangel0002-助理二级最佳答案main()inti,j,temp;inta10;for(i=0;i10;i+)scanf(%d,&ai);for(j=0;j=9;j+)for(i=0;ia【i+1)temp=ai;ai=ai+1;ai+1=temp;for(i=1;i11;i+)printf(%5d,ai);printf(n);冒泡算法冒泡排序的算法分析与改进交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的
2、记录为止。应用交换排序基本思想的主要排序方法有：冒泡排序和快速排序。冒泡排序1、排序方法将被排序的记录数组R1.n垂直排列，每个记录R看作是重量为R.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R:凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。初始R1.n为无序区。第一趟扫描从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(Rn,Rn-1),(Rn-1,Rn-2)，(R2,R1);对于每对气泡(Rj+1,Rj)，若Rj+1.keyRj.key则交换Rj+1和Rj的
3、内容。第一趟扫描完毕时，”最轻”的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R1上。第二趟扫描扫描R2.n。扫描完毕时，次轻的气泡飘浮到R2的位置上最后，经过n-1趟扫描可得到有序区R1.n注意：第i趟扫描时，R1.i-1和Ri.n分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R上，结果是R1.i变为新的有序区。2、冒泡排序过程示例对关键字序列为4938659776132749的文件进行冒泡排序的过程3、排序算法(1)分析因为每一趟排序都使有序区增加了一个气泡，在经过n-1趟排序之后，有序区中就有n-1个气泡，而无序区
4、中气泡的重量总是大于等于有序区中气泡的重量，所以整个冒泡排序过程至多需要进行n-1趟排序。若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，冒泡排序过程可在此趟排序后终止。为此，在下面给出的算法中，引入一个布尔量exchange，在每趟排序开始前，先将其置为FALSE。若排序过程中发生了交换，则将其置为TRUE。各趟排序结束时检查exchange，若未曾发生过交换则终止算法，不再进行下一趟排序。(2)具体算法voidBubbleSort(SeqListR)R(l.n)是待排序的文件，采用自下向上扫描，对R做冒泡排序inti，j;Boole
5、anexchange；/交换标志for(i=1;i=i；j-)/对当前无序区Ri.n自下向上扫描if(Rj+1.keyRj.key)交换记录R0=Rj+1;R0不是哨兵，仅做暂存单元Rj+1=Rj；Rj=R0；exchange=TRUE;/发生了交换，故将交换标志置为真if(!exchange)/本趟排序未发生交换，提前终止算法return；/endfor(外循环)/BubbleSort4、算法分析(1)算法的最好时间复杂度若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin=n-1Mmin=O。冒泡排序最好的时间复杂度为0(n)。(2)
6、算法的最坏时间复杂度若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1i二1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：Cmax=n(n-1)/2=O(n2)Mmax=3n(n-1)/2=O(n2)冒泡排序的最坏时间复杂度为0(n2)。算法的平均时间复杂度为0(n2)虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。算法稳定性冒泡排序是就地排序，且它是稳定的。5、算法改进上述的冒泡排序还可做如下的改进：记住最后一次交换发生位置lastExchange的冒泡排序在每趟
7、扫描中，记住最后一次交换发生的位置lastExchange，(该位置之前的相邻记录均已有序)。下一趟排序开始时，R1.lastExchange-1是有序区，RlastExchange.n是无序区。这样，一趟排序可能使当前有序区扩充多个记录，从而减少排序的趟数。具体算法【参见习题】。改变扫描方向的冒泡排序冒泡排序的不对称性能一趟扫描完成排序的情况：只有最轻的气泡位于Rn的位置，其余的气泡均已排好序，那么也只需一趟扫描就可以完成排序。【例】对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描。需要n-1趟扫描完成排序情况：当只有最重的气泡位于R1的位置，其余的气泡均已排好序
8、时，则仍需做n-1趟扫描才能完成排序。【例】对初始关键字序列：94，10，12，18，42，44，45，67就需七趟扫描。造成不对称性的原因每趟扫描仅能使最重气泡下沉一个位置，因此使位于顶端的最重气泡下沉到底部时，需做n-1趟扫描。改进不对称性的方法在排序过程中交替改变扫描方向，可改进不对称性。回答者：cicihsk-助理二级9-411:08评价已经被关闭目前有4个人评价EZ不好好25%(1)75%（3）其他回答共3条main()inti,j,n,a10;printf(”输入10个数:);for(i=0;i10;i+)scanf(%d,&ai);记得输入的时候后面加:”for(i=0;in-1
9、;i+)for(j=i;jaj)/改成(aiaj)可按大到小排序n=ai;ai=aj;aj=ai；printf(n由小到大排序结果为：”)；for(i=0;i10;i+)printf(%d,ai);回答者：TANK006-经理四级9-411:06转载自非常代码网/*FunctionPrototypes*/voidBubbleSort(intArray,constintSize);voidPrintArray(intArray,constintSize);intmain(void)inti;constintSize=20;intArraySize;/*FilltheArraywithrandom
10、valuesbetween0and99*/for(i=0;iSize;i+)Arrayi=random()%100;/*PrinttheRandomArraytoScreen*/clrscr();printf(TheArraywithrandomorder:nn);PrintArray(Array,Size);/*WaitforkeyPress.*/printf(nPressanykey.);getch();/*SorttheArrayusingBubbleSort*/BubbleSort(Array,Size);/*PrinttheSmallest-to-LargestOrderArray*
11、/clrscr();printf(TheArrayafterBubbleSort:nn);PrintArray(Array,Size);/*EndtheProgram*/printf(nPressanykeytoquit.);getch();return0;/*Usestheclassicbubblesortalgorithm*/voidBubbleSort(intArray,constintSize)inti,j,temp;for(i=0;iSize-1;i+)for(j=0;jArrayj+1)temp=Arrayj;Arrayj=Arrayj+1;Arrayj+1=temp;/*PrintsanintegerArraylinebyline*/voidPrintArray(intArray,constintSize)inti;for(i=0;iSize;i+)printf(Array%i=%in,i,Arrayi);
