黑马程序员技术交流社区

标题: 排序学习的心得之一冒泡改进 [打印本页]
作者: 行我福    时间: 2015-1-20 21:46
标题: 排序学习的心得之一冒泡改进
本帖最后由 行我福 于 2015-1-20 22:14 编辑

    说到排序，估计新手首先就会反应出来的是冒泡排序，本贴就以冒泡排序开始说起，在此以升序为例来说明~
    传统的冒泡有一点暇丝，可能在某一轮冒泡的时候就得到结果，但是计算机不知道，它依旧会进行比较操作，为了改进这一缺点，我定义一个标识符flag，在每轮比较结束之前将flag赋值为1，如果该轮比较操作中发现排序没有完成，那么就在该轮结束时赋值为0，否则不改变其flag值，在下一轮开始冒泡前对flag进行判断，如果其值为1，表示在上一轮排序中已经完成了排序功能，那么就结束排序比较，接下来请看代码：
  1. #include <stdio.h>
  2. void bubble_sort(int arr[],int n)
  3. {
  4.         int i,j,flag,temp;
  5.         for(i=0;i<n-1;i++)
  6.         {
  7.                 flag=1;
  8.                 for(j=0;j<n-i-1;j++)
  9.                 {
  10.                         if(arr[j]>arr[j+1])
  11.                         {
  12.                                 temp=arr[j];
  13.                                 arr[j]=arr[j+1];
  14.                                 arr[j+1]=temp;
  15.                                 flag=0;
  16.                         }
  17.                 }
  18.                 if(1==flag) break;
  19.         }
  20.         printf("\n比较操作进行了%d轮",i+1);
  21.         return;
  22. }
  23. int main()
  24. {
  25.         int a[]={12,54,67,89,96};
  26.         int i;
  27.         printf("排序前\n");
  28.         for(i=0;i<5;i++)
  29.         {
  30.                 printf("%d\t",a[i]);
  31.         }
  32.         bubble_sort(a,5);
  33.         printf("\n排序后\n");
  34.         for(i=0;i<5;i++)
  35.         {
  36.                 printf("%d\t",a[i]);
  37.         }
  38.         return 0;
  39. }
复制代码
在上述代码，排序中加了一个打印输出语句，用于输出比较进行多少轮。由于最初给定的数组是一个有序的数组，因此比较操作只进行了一轮，但是如果没有若没有代码中使用flag，那么，即使是对有序的数组进行排序，同样进行5轮操作，使用标志符之后，算法的效率得到了提高。      根据上述，冒泡排序的时间复杂度是O（n^2）;


图片1.png (4.4 KB, 下载次数: 6)

冒泡排序改进版截图

冒泡排序改进版截图
作者: 瀚的回忆    时间: 2015-1-20 22:04
泡排序就是这样的啊
作者: HTC    时间: 2015-1-22 12:38
谢谢楼主分享经验。受益了。
作者: 晓风_残月    时间: 2015-1-22 13:34
嗯 ，不错的。学习了
作者: alin000    时间: 2015-1-24 18:28
感谢楼主分享！
作者: shixichen    时间: 2015-1-24 19:21
想得周到
作者: 87526845    时间: 2015-1-24 19:32
谢楼主分享



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2