冒泡排序

TIP

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端

算法描述

• 步骤 1: 比较相邻的元素。如果第一个比第二个大，就交换它们两个
• 步骤 2: 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
• 步骤 3: 针对所有的元素重复以上的步骤，除了最后一个
• 步骤 4: 重复步骤 1~3，直到排序完成

动图演示

代码编写

// 冒泡排序
function bubbleSort(arr) {
	// 1. 获取数组的长度
	var length = arr.length

	// 2. 外层循环控制冒泡趟数：越来越少
	for (var j = length - 1; j >= 0; j--) {
		// 3. 内层循环控制每趟比较的次数：根据j的次数, 比较循环到j位置
		for (var i = 0; i < j; i++) {
			// 4. 相邻元素两两比较：如果i位置比i+1位置的数据大, 那么就交换
			if (arr[i] > arr[i + 1]) {
				// 交互两个数据
				var tmp = arr[i]
				arr[i] = arr[i + 1]
				arr[i + 1] = tmp
			}
		}
	}
	// 5. 返回数组
	return arr
}

代码解析

文字说明

• 第一步：获取数组长度
• 第二步：使用反向遍历，编写外层循环控制冒泡趟数，为了越遍历越少：
  1. 第一次：j = length - 1，比较到倒数第一个位置
  2. 第二次：j = length - 2，比较到倒数第二个位置
• 第三步：编写内层循环控制每趟比较的次数：
  1. 第一次比较： i = 0，比较 0 和 1 位置的两个数据，如果 0 位置大于 1 位置的数据，就交换
  2. 最后一次比较：i = length - 2,比较 length - 2 和 length - 1 两个数据

图解分析

代码测试

// 测试冒泡排序
var arr = [3, 6, 4, 2, 11, 10, 5]
console.log(bubbleSort(arr).join("-"))
// 2-3-4-5-6-10-11

排序效率

• 上面所讲的对于 7 个数据项，比较次数为：6 + 5 + 4 + 3 + 2 + 1
• 对于 N 个数据项，比较次数为：(N - 1) + (N - 2) + (N - 3) + ... + 1 = N * (N - 1) / 2，为等差求和公式
• 如果两次比较交换一次，那么交换次数为：N * (N - 1) / 4
• 使用大 O 表示法表示比较次数：O(N * (N - 1) / 2)，交换次数: O( N * (N - 1) / 4)
• 根据大 O 表示法的三条规则都化简为：O(N²);