冒泡排序 Bubble Sort 最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第 i 遍处理时，不必检查第 i 高位置以上的元素，因为经过前面 i-1遍的处理，它们已正确地排好序。这个算法可实现如下。 procedure Bubble_Sort(var L:List); var i,j:position; begin 1 for i:=First(L) to Last(L)-1 do 2 for j:=First(L) to Last(L)-i do 3 if L[j]>L[j+1] then 4 swap(L[j],L[j+1]); //交换 L[j]和 L[j+1] end; 上述算法将较大的元素看作较重的气泡，每次最大的元素沉到表尾。其中 First(L)和Last(L)分别表示线性表 L 的第一个元素和最后一个元素的位置，swap(x,y)交换变量 x,y的值。上述算法简单地将线性表的位置当作整数用 for 循环来处理，但实际上线性表可能用链表实现；而且上述算法将线性表元素的值当作其键值进行处理。不过这些并不影响表达该算法的基本思想。今后如果不加说明，所有的算法都用这种简化方式表达。 容易看出该算法总共进行了 n(n-1)/2 次比较。如果 swap 过程消耗的时间不多的话，主要时间消耗在比较上，因而时间复杂性为 O(n2)。但是如果元素类型是一个很大的纪录，则Swap 过程要消耗大量的时间，因此有必要分析 swap 执行的次数。 显然算法Bubble_Sort 在最坏情况下调用 n(n-1)/2 次 Swap 过程。我们假设输入序列的分布是等可能的。考虑互逆的两个输入序列 L1=k1,k2,..,kn 和 L2=kn,kn-1,..,k1。我们知道，如果 ki>kj，且 ki 在表中排在 kj 前面，则在冒泡法排序时必定要将 kj 换到 ki 前面，即 kj 向前浮的过程中一定要穿过一次 ki，这个过程要调用一次 Swap。对于任意的两个元素 ki 和 kj，不妨设 ki>kj，或者在 L1 中 ki 排在 kj 前面，或者 L2 在中 ki 排在 kj 前面，两者必居其一。因此对于任意的两个元素 ki 和 kj，在对 L...
