# 冒泡排序

TIP

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

# 算法描述

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

# 动图演示

sort

# 代码编写

// 冒泡排序
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 两个数据

图解分析

sort

# 代码测试

// 测试冒泡排序
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²);