个人博客

插入排序

TIP

插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

算法描述

  • 步骤 1：从第一个元素开始，该元素可以认为已经被排序（局部有序）
  • 步骤 2：取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 步骤 3：如果该元素（已排序）大于新元素，将该元素移到下一位置
  • 步骤 4：重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
  • 步骤 5：将新元素插入到该位置后
  • 步骤 6：重复步骤 2~5，直到排序完成

动图演示

sort

代码编写

// 插入排序
function insertionSort(arr) {
	// 1. 获取数组长度
	var length = arr.length

	// 2.外层循环: 从第1个位置开始获取数据，向前面局部有序进行插入
	for (var i = 1; i < length; i++) {
		// 3. 内层循环：获取i位置的元素，和前面的数据依次进行比较
		// 3.1 记录选出的元素和位置
		var tmp = arr[i]
		var j = i

		// 3.2 由于内层循环不确定循环的次数, 最好使用while循环
		while (j > 0 && arr[j - 1] > tmp) {
			arr[j] = arr[j - 1]
			j--
		}
		// 4. 在选出的j位置，放入tmp元素
		arr[j] = tmp
	}

	// 5. 返回数组
	return arr
}

代码解析

文字说明

  • 第一步：获取数组长度
  • 第二步：外层循环, 从 1 位置开始, 因为 0 位置可以默认看成是有序的
  • 第三步：记录选出的 i 位置的元素, 保存在变量 tmp 中，i 默认等于 j
  • 第四步：编写内层循环：
    1. 内层循环的判断 j - 1 位置的元素和 tmp 比较, 并且 j > 0
    2. 如果 j-1 位置的元素大于 tmp，那么就将 j-1 位置的元素放在 j 位置
    3. j 位置向前移
  • 第五步：将目前选出的 j 位置放置 tmp 元素

图解分析

sort

代码测试

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

排序效率

  • 比较次数：N*(N-1)/4, 也就是 O(N²)
    1. 第一趟时, 需要的最多次数是 1, 第二趟最多次数是 2, 依次类推, 最后一趟是 N-1 次
    2. 因此比较次数最多：1 + 2 + 3 + ... + N - 1 = N * (N - 1) / 2
    3. 然而每趟发现插入点之前, 平均只有全体数据项的一半需要进行比较
    4. 可以除以 2 得到 N * (N - 1) / 4. 所以相对于选择排序, 其他比较次数是少了一半的
  • 交换次数：N * (N - 1) / 4, 用大 O 表示法就是 O(N)
    1. 第一趟时, 需要的最多复制次数是 1, 第二趟最多次数是 2, 依次类推, 最后一趟是 N-1 次
    2. 因此复制次数最多：1 + 2 + 3 + ... + N - 1 = N * (N - 1) / 2
    3. 平均次数：N * (N - 1) / 4
  • 选择排序通常认为在执行效率上是高于插入排序和冒泡排序的