改进的冒泡排序

rosynirvana

1. #include <stdio.h>
   
2. 
   
3. void swap(int*, int*);
   
4. void bubble_sort(int*, int);
   
5. 
   
6. int main()
   
7. {
   
8.         int data[5] = {3, 7, 4, 1, 9};
   
9.         int i;
   
10.         bubble_sort(data, 5);
    
11. 
    
12.         for(i=0; i!=5; ++i)
    
13.                 printf("%d ", data[i]);
    
14. 
    
15.         return 0;
    
16. }
    
17. 
    
18. void swap(int* a, int* b)
    
19. {
    
20.         int temp = *a;
    
21.         *a = *b;
    
22.         *b = temp;
    
23. }
    
24. 
    
25. void bubble_sort(int* ary, int length)
    
26. {
    
27.         int i, j;
    
28.         int changed;
    
29. 
    
30.         for(i=0; i<length-1 && changed; ++i){
    
31.                 changed = 0;
    
32.                 for(j=0; j<length-i; ++j)
    
33.                         if(ary[j] > ary[j+1]){
    
34.                                 changed = 1;
    
35.                                 swap(&ary[j], &ary[j+1]);
    
36.                         }
    
37.         }
    
38. }

复制代码

一句话简介：用一个变量(changed)来记录在某一轮比较中有没有发生交换，如果没有，那么排序已经完成

很明显，如果一个数组的a[1] < a[2] a[2] < a[3] ....都成立，那么这个数组就是排好序的

如果要用冒泡排序，强烈建议加上这个判断，否则冒泡排序就要和选择排序做同样次数的比较，而且由于选择排序少的缘故，必然是选择排序比较好。
另外，选择排序要比冒泡排序稍微好写一点

后面的实际例子也是如此，人名是个字符串，一般占的内存较多，让两个占很大内存空间的结构体进行交换是比较低效的事情。
有两种解决方法，第一是给每个人编号，然后实际排序的结构体中记录人的编号和分数，例如

编号 人名
0 huhu
1 haha
2 xixi
3 hengheng
4 gaoshou

然后结构体中的数据是
0 5 （对应huhu 5)
1 3 （对应haha 3）
2 5
3 2
4 8

这样保证排序进行交换的时候只交换8个字节的数据，然后输出的时候再根据编号输出人名

另外一种方法是结构体中保存分数和姓名字符串的指针，这样保证每次交换的时候只有8字节或12字节（64位系统）
可以试着自己研究一下

福华

给每个人编号来提高交换效率，比较简单实用

王萍萍

经常把选择排序当成冒泡来写，当必须写冒泡时，写不出来了

超神级

{:soso_e121:}