经典算法巡礼(一) -- 排序之冒泡排序

冒泡排序是一种简单的排序算法，相信绝大多数人学会的第一种排序算法就是她了。

事实上，她重复地遍历需要排序的元素，一次比较相邻的两个元素，如果不满足预先定义的比较条件，则交换；否则继续下一组元素比较，直至遍历完成需要排序的所有元素。当然，遍历需要排序的元素需要重复进行，直到没有需要排序的元素为止。遍历需要排序的元素时，每一次交换不满足顺序条件的元素就如同气泡一样，从元素序列的一端慢慢“上升”到序列的另一端，此现象如同水中冒气泡一样，此排序算法以此得名。

具体实现也较为简单，用golang表示如下：

		// Sort方法从数组头开始冒泡，将最小元素位置上升到最后，直到数组排序完成为止
		// Sort中参数类型Comparable为统一的可比较接口，若为整数数组排序，则Comparable为int即可
		// Sort中参数类型Compare为配合Comparable接口的比较方法，若为整数数组排序，则Compare即满足a int < a int即可
		func (this *BubbleSort) Sort(a []Comparable, compare Compare) {
			for i := 0; i < len(a); i++ {
				for j := 1; j < len(a)-i; j++ {
					if this.less(a[j], a[j-1], compare) {
						this.exch(a, j-1, j)
					}
				}
			}
		}

那么，冒泡排序的效率如何呢？事实上，她不咋滴。且看上述代码中的两重循环吧，这可是复杂度的恶梦啊。当然，很明显，她的时间复杂度是O(N^2)。

为了方便，我们以一次比较作为一次时间复杂度操作。根据冒泡排序的实现的思路，对长度为N的数组进行排序所需要的比较次数为N-1 + N-2 + ... + 1 + 0，即(N-1)/2*N = (N^2-N)/2 ~ N^2。可见，通用简单的数学计算，冒泡排序的时间复杂度确实就是O(N^2)。

换种通俗的方式来说，冒泡排序的时间复杂度是平方级别的。因此，她只适合对少量元素进行排序，而无法用于大规模数据的排序，可谓是中看不中用啊。