Chinaunix首页 | 论坛 | 博客
  • 博客访问: 664386
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2016-02-16 22:51:50

在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较小的数往下沉,较大的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
简单实现:

点击(此处)折叠或打开

  1. void bubbleSort(int list[], int len)
  2. {
  3.     int i,j;
  4.     int temp;

  5.     for (i = 0; i < len; i++)
  6.     {
  7.         for(j = 0; j < len - 1; j++)
  8.         {
  9.             if (list[j] > list[j+1])
  10.             {
  11.                 temp = list[j];
  12.                 list[j] = list[j + 1];
  13.                 list[j + 1] = temp;
  14.             }

  15.         }
  16.     }
  17. }
见上面程序段,第一个for循环中循环次数是len 次,但实际上,大多数情况下,不需要比较完len趟,序列已经处于有序状态了;因此,一个常见的改进是,在比较过程中加入一个flag,记录某一趟比较中是否发生了交换,如果没有交换发生,表明已经有序了,完成排序。另一方面,第二个for循环中,循环次数也是len-1次,但实际上,随着每一趟完成,队尾的数都是有序状态,因此不必要重复比较;另一个改建就是加入一个“有序队列”的标记,之后的数据都是有序的,无需比较。
改进算法实现如下:

点击(此处)折叠或打开

  1. void bubbleSort2(int list[], int len)
  2. {
  3.     int flag;
  4.     int sortedIdx = len - 1;
  5.     int temp;

  6.     int i;

  7.     // force to run at first
  8.     flag = 1;
  9.     while (flag == 1)
  10.     {
  11.         flag = 0;

  12.         for(i = 0; i < sortedIdx; i++)
  13.         {
  14.             if (list[i] > list[i + 1])
  15.             {
  16.                 temp = list[i];
  17.                 list[i] = list[i+1];
  18.                 list[i+1] = temp;

  19.                 flag = 1;
  20.             }
  21.         }
  22.         sortedIdx--;
  23.     }

  24. }

阅读(1793) | 评论(0) | 转发(0) |
0

上一篇:堆排序

下一篇:归并排序

给主人留下些什么吧!~~