数据结构第一章讨论了一些有关算法的问题.在这一部分再次引入了那个经典的算法--冒泡排序法。
如果让我来描述一下这个算法的过程的话，我会这样描述：
从第一个元素开始和依次进行比较，大的那个放在后面，一直到最后一个元素。这样最后一个元素就会成为最大的那个；除刚才产生的最大的那个元素外，再次从头开始比较，一直到第一个元素没得可比为止。
这是我的理解。进而通过这个理解，我可以写出这个算法来。这没有问题。但是当我看到原版的算法的时候，我立即就感觉出差别来了：
1 void bubble_sort(int a[],int n)
2 {
3 for(i=n-1,change=TRUE;i>1&&change;--i)
4 {
5 change=FALSE;
6 for(j=0;j<i;++j)
7 if(a[j]>a[j+1]{a[j]<-->a[j+1];change=TRUE;}
8 }
9 }
注意变量change。这里体现的思路是：如果在某一次比较过程中没有移动任何元素，那么就没有必要再从头比较一次了。因为实际上已经得到了一个排好序的数组。
这样对于相当多的情况来讲，减少了很多的不必要操作，自然平均时间复杂程度就降低了。
因为我往往只考虑到比较坏甚至极端的情况（比如完全逆序），所以自然就会忽略这些看上去不太坏，甚至是非常好的情况，这样一个直接的结果就是让那些好的情况下的操作也变得繁琐异常，而仅仅是为了照顾那些比较难于出现的个别异常情况，现在想想，这样做不可取。日后应当注意。
posted on 2007-06-10 22:34
littlegai 阅读(507)
评论(0) 编辑 收藏 引用 所属分类:
我的读书笔记