死侍开头的说唱:9.3.3 冒泡排序优化

来源：百度文库 编辑：偶看新闻 时间：2024/05/01 10:00:33

9.3.3 冒泡排序优化

这样的冒泡程序是否还可以优化呢？答案是肯定的。试想一下，如果我们待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当i=1时，交换了2和1，此时序列已经有序，但是算法仍然不依不饶地将i=2到9以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了，如图9‐3‐5所示。

图9-3-5

当i=2时，我们已经对9与8，8与7，……，3与2作了比较，没有任何数据交换，这就说明此序列已经有序，不需要再继续后面的循环判断工作了。为了实现这个想法，我们需要改进一下代码，增加一个标记变量flag来实现这一算法的改进。


  1. /* 对顺序表L作改进冒泡算法 */  
  2. void BubbleSort2（SqList *L）  
  3. {  
  4. int i,j;  
  5. Status flag=TRUE; /* flag用来作为标记 */  
  6. for（i=1;ilength && flag;i++） /*若flag为true则退出循环 */  
  7. {  
  8. flag=FALSE; /* 初始为false */  
  9. for（j=L->length-1;j>=i;j--）  
  10. {  
  11. if（L->r[j]>L->r[j+1]）  
  12. {  
  13. swap（L,j,j+1）; /* 交换L->r[j]与L->r[j+1]的值 */  
  14. flag=TRUE; /* 如果有数据交换，则flag为true */  
  15. }  
  16. }  
  17. }  
  18. }

代码改动的关键就是在i变量的for循环中，增加了对flag是否为true的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。

冒泡排序 冒泡排序 冒泡排序 冒泡排序法 VB冒泡法排序 VB怎么用冒泡排序? 选择法 冒泡法 排序 C如何编冒泡排序 C语言冒泡法排序 用指针实现冒泡排序 用指针实现冒泡排序 关于JAVA中的冒泡排序法？？？ vb的冒泡排序法怎么用? 用JAVA写出冒泡排序的算法 链表的冒泡排序算法 冒泡排序与选择选排序有什么样不同 请问冒泡排序和选择排序哪个效率更高? 帮忙做一道题：关于冒泡排序与快速排序。 这个C++冒泡法程序怎么优化？ 在VB中演示过程冒泡法排序 求助:汇编 冒泡排序程序(十进制数输入部分实现) 如何编写一个函数,完成对数组冒泡排序？ 用c语言写冒泡排序！！在线等! VB编程:选择法及冒泡法排序数组