A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 行我福 中级黑马   /  2015-1-20 21:46  /  1493 人查看  /  6 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 行我福 于 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, 下载次数: 11)

冒泡排序改进版截图

冒泡排序改进版截图

评分

参与人数 1黑马币 +5 收起 理由
张文文 + 5 神马都是浮云

查看全部评分

6 个回复

倒序浏览
泡排序就是这样的啊
回复 使用道具 举报
谢谢楼主分享经验。受益了。
回复 使用道具 举报
嗯 ,不错的。学习了
回复 使用道具 举报
感谢楼主分享!
回复 使用道具 举报
想得周到
回复 使用道具 举报
谢楼主分享
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马