非数值问题的常用算法--冒泡法

冒泡法是一种最简单的排序方法。
　　冒泡排序的过程很简单。首先对n个项目进行扫描，比较相领两个项目的大小，若发现违背大小次序则进行互换，由此可以使n个项目中的最大者换到最后；然后对剩下的未排序好的项目再进行扫描，使它们的最大者换到表的最后；以此类推，直到将表全部排序好为止。在这种排序方法中，每遍扫描以后，都缩短了待排序表的长度，如果在某次扫描过程中，没有发现交换，则排序结束。为了尽量缩短待排序表的长度，避免下一次扫描中可能出现的不必要的比较，在每次扫描过程中，一方面要记录进行元素交换的次数，另一方面要记住在本次扫描中的最后一次进行交换的位置。在这个位置以后没有发生过交换，则说明在这个位置以后的元素实际上已经排好次序。在下面的算法中，用一个工作单元F同时记录这两个信息。

　　例：

　　输入：待排序表L（1:n）。

　　输出：有序表L（1:n）。

　　PROCEDURE LBUBSORT(L,N)

    F←n

    WHILE F>0 DO

       {k←F-1:F←0

           FOR j=1 TO k DO

              {IF L(j)>L(j+1) THEN

                   {L(j)与L(j+1)交换:F←j}

               }

        }

    RETURN

　　在这个算法中，k代表在每次扫描过程中需要进行经较的项目数；当F＞0时，表示还需要进行扫描比较，并且，它的数值表示上一次扫描中发生最后一次交换的位置。由上例中不难看出，在最坏情况下，冒泡排序法需要进行n-1遍扫描，共要作[n(n-1)]/2次比较和元素的交换。但这个工作量并不是必需的，一般情况下要小于这个工作量。

如果想做斑竹，你可以和我联系，说明你的情况，我们希望有创造性的、有激情的朋友加入，帮我们一起建立一个很好的gis网站，多谢支持！