1. 参考资料:

1 )谭浩强 c 程序设计》 124

2 )数据结构自考网( very good

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.1.1.htm

 

2. 算法分析:

假如有以下数据: 5 2 4 3 ;人是如何排序的呢?如果按从小到大排序,肯定是每次找出一个最小的数,直到排好序;(注:选择排序就是这个思路,每次找出一个最小值放到合适位置;)类似,计算机实现也是这样的,最简单的冒泡排序方法就是如此,每次找出一个最大的值沉底,第一次 5 沉底,第二此 4 沉底,经过 N-1 次后排序完成。

 

3 .具体编码实现时关键是要确定循环次数:

3.1 思路一:

外层循环: n-1 (每次找出一个最大的)

内层循环: n-i

外层 i=1, 内层需要 n-1 次两两比较才能找出最大值;

外层 i=2, 内层需要 n-2 次两两比较才能找出最大值;

……

归纳得到,内层循环需要 n-i

 

如此反复,直到排好序为止(若在某一趟冒泡过程中,没有发现一个逆序,则可结束冒泡排序),所以 冒泡过程最多进行 n-1 趟。

 

代码实现如下:

				
 1 void  BubbleSort(RecordType r[], int length )
 2 /*对记录数组r做冒泡排序,length为数组的长度*/
 3 {
 4 n=length;    change=TRUE;
 5 for ( i=1 ; i<= n-1 && change ;++i ) 
 6 {
 7      change=FALSE;
 8  for ( j=1 ; j<= n-i ; ++j) 
 9  if (r[j].key> r[j+1].key )  
10 {
11            x= r[j];
12            r[j]= r[j+1];
13            r[j+1]= x;
14 change=TRUE;
15      } 
16 }
17 /*  BubbleSort  */ 
18 

代码来自:

西北大学 数据结构 精品教程

交换类排序法 冒泡排序  

http://jpkc.nwu.edu.cn/datastr/study_online/test_paper.htm

 

3.2 思路二:

以下内容来自:

数据结构自考网

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.1.1.htm

或者

http://www.wjzyzx.com/rjxy/sjjg/gailun/gailun1.3.2.htm

 

提示:注意有序区、无序区的这种思考方法。

冒泡排序

1
、排序方法
   
 将被排序的记录数组 R[1..n] 垂直排列,每个记录 R[i] 看作是重量为 R[i].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].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[i] 上,结果是 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<n;i++){ //
最多做 n-1 趟排序
       exchange=FALSE
// 本趟排序开始前,交换标志应为假
       for(j=n-1;j>=i
j--)  // 对当前无序区 R[i..n] 自下向上扫描
        if(R[j+1].key<R[j].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. 算法分析

冒泡排序算法分析:最坏情况下,待排序记录按关键字的逆序进行排列,此时,每一趟冒泡排序需进行i次比较,3i次移动。经过n-1趟冒泡排序后,总的比较次数为n(n-1)/2;总的移动次数为3 n(n-1)/2 次,因此该算法的时间复杂度为O(n2);空间复杂度为O(1)。另外,冒泡排序法是一种稳定的排序方法。

注:

1) 关键语句总执行次数的计算:

外层i=1:内层j=n-1;

i=2:j=n-2; ……;

所以,交换语句的总执行次数是(n-1+(n-2)+(n-3)++1=n(n-1)/2;

2) 时间复杂度的概念:

一般情况下,算法中基本操作重复执行的次数是问题规模 n 的某个函数,用 T(n) 表示,若有某个辅助函数 f(n), 使得当 n 趋近于无穷大时, T n)/f (n) 的极限值为不等于零的常数,则称 f(n) T(n) 的同数量级函数。记作 T(n)=O(f(n)), O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为 O(1), 另外,在时间频度不相同时,时间复杂度有可能相同,如 T(n)=n2+3n+4 T(n)=4n2+2n+1 它们的频度不同,但时间复杂度相同,都为 O(n2)

3) 空间复杂度:

与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作 :
S(n)=O(f(n))
我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。

 

冒泡排序的O(1)表示只需要一个辅助的temp存储单元来实现交换数据,所以空间复杂度为常量。

 

4 )平均时间复杂度:

设每种情况的出现的概率为 pi, 则为 sum(pi*f(n))

以下内容来自:

请教关于“平均时间复杂度 T(n) ”的推导

http://topic.csdn.net/t/20031209/21/2546177.html

问题:  
     
今假设 a 中初始输入数据可能出现   n!   种的排列的概率相等,则 关键语句 的平均执行次数为多少?希望给出具体的推导过程!  
 
(书上没给出具体答案,只写了平均时间复杂度 T(n)   =   O(n 平方 )  

解答:

如果 a 中初始输入数据可能出现   n!   种的排列的概率相等  
 
if(   a[j]   >   a[j+1]   ) 句成立的概率为 50%  
 
故内层循环执行次数为 i/2  
 
在不考虑 change 的影响是有 T(n)=(1+2+....+n-1)/(2*2)   =   (n-1)*n/4   =   O(n^2)

 

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 趟扫描。

 
改进不对称性的方法
   
 在排序过程中交替改变扫描方向,可改进不对称性。

  代码实现如下:

代码来源: http://www.goc.ac.cn/liuag/html/algorithms_bibobblesort.html  

  1                 int
  2                  data[10]={4,8,22,79,-2,0,100,13,12,-100};
  3         
  4 
  5                 void
  6                  Bubble_Sort2(int a[],int n);
  7         
  8 
  9                 void
 10                  Print(int a[],int n);
 11         
 12 
 13                 main()
 14         
 15 
 16                 {
 17         
 18 
 19                 
 20                           Print(data,10);
 21         
 22 
 23                 
 24                           Bubble_Sort2(data,10);
 25         
 26 
 27                 
 28                           Print(data,10);
 29         
 30 
 31                 }
 32         
 33 
 34                 void
 35                  Print(int a[],int n)
 36         
 37 
 38                 {
 39         
 40 
 41                 
 42                             
 43                         int i;
 44         
 45 
 46                 
 47                             
 48                         for(i=0;i<n;++i)
 49         
 50 
 51                 
 52                              printf("%4d",a[i]);
 53         
 54 
 55                 
 56                             printf("\n");
 57         
 58 
 59                 }
 60         
 61 
 62                 void
 63                  Bubble_Sort2(int a[ ],int n)
 64         
 65 
 66                 {
 67   
 71                         int low=0,high=n-1;
 72  
 76                         int change=1;
 77
 81                         int i,temp;
 82                             
 86                         while(low<high&&change)
 87
 90                           {
 91 
 94                             change=0;
 95    
 99                         for(i=low;i<high;i++)
100   
104                         if(a[i]>a[i+1])
105    
108                               {
109         
110 
113                         /* a[i]<->a[i+1];*/
114    
118                                 temp=a[i];
119    
122                                 a[i]=a[i+1];
123         
124 
125                 
126                                 a[i+1]=temp;
127         
128 
129                 
130                                 change=1;
131         
132 
133                 
134                               }
135         
136 
137                 
138                             high--;
139         
140 
141                 
142                             
143                         for(i=high;i>low;i--)
144         
145 
146                 
147                               
148                         if(a[i]<a[i-1])
149         
150 
151                 
152                               {
153         
154 
155                 
156                                 
157                         /* a[i]<->a[i-1]; */
158                 
159         
160 
161                 
162                                 temp=a[i];
163         
164 
165                 
166                                 a[i]=a[i-1];
167         
168 
169                 
170                                 a[i-1]=temp;
171         
172 
173                 
174                                 change=1;
175         
176 
177                 
178                               }
179         
180 
181                 
182                             low++;
183         
184 
185                 
186                           }//while
187         
188 
189                 }//Bubble_Sort2
190         

⑤双向冒泡排序真的比单向的快?

其实双向冒泡并不一定比单向的快,只是在排序过程中交替改变扫描方向,可改进冒泡排序的不对称性。

 

Ok

明天学习快速排序法!

Come on