likes
comments
collection
share

🥳每日一练-插入排序和优化-JS简单版

作者站长头像
站长
· 阅读数 30

今天分享的内容是一种排序算法--插入排序。插入排序是一个基本难度的算法，相较于其他的更快的算法，像快速排序算法，有个优点，就是稳定。稳定是一个很重要的性质。如果两个数值相等的元素，在排序之后，这两个元素的相对位置不会发生变化，那么这个算法就是稳定的。这是很重要的。

假设现在有这么一个场景，现在多条学生成绩的数据，最初是按照学生的姓名首字母排序的，现在按照学生的成绩排序，要求相同成绩的学生之间，依旧按照字母排序。如果排序不是稳定的，那么这种要求就难以保证，除非相同成绩的学生之间再来一次排序😄

什么是插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。具体来说，插入排序的实现思路如下：

  1. 将第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
  3. 如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。（稳定性的考量）

实现快速排序

const data = [23, 54, 2, 23, 1, 2, 65, 343, 9, 213];

const insertSort = (array) => {
    for (let i = 1; i < array.length; i++) {
        if (array[i - 1] > array[i]) { // 如果前一个元素大于当前元素
            const temp = array[i]; // 保存当前元素
            let j = i - 1;
            for (; j >= 0 && array[j] > temp; j--) { // 从右向左搜索放置项目的正确位置
                array[j + 1] = array[j]; // 将前一个元素复制到后一个元素上
            }
            array[j + 1] = temp; // 找到当前元素应处于的位置
        }
    }
};

这是一段插入排序的代码。插入排序就是从选择其中一个数，插入前面的有序数组。

代码中从数组中的第二个位置开始遍历，往前面的有序数组进行插入。假设遍历到了第 k 个， 第 k-1 个元素比第 k 个大，就需要发生数据的挪动。接下来的 for 循环就是找前面所有的比第 k 个元素大的元素，有一个算一个，全部往后移一位。虽然会覆盖第 k 个位置，不过没关系，第 k 个元素用 temp 保存了起来。等找完了，就将第 k 个元素，放到前面空出来的位置。这样有序数组的长度就增加了一。

接着 i++，继续遍历下一个元素，即将 k+1 个元素插入到前面的有序数组中

等将所有的元素都插入到有序数组中，array 数组自然就是有序的了

测试代码：

insertSort(data);
console.log(data);
// [
//    1,  2,  2,   9,  23,
//   23, 54, 65, 213, 343
// ]

测试成功，输出结果是有序的

有个关键的地方需要注意：在判断array[j] > temp 中，>不能写成>=， 如果加了=，就会使得大小相同的元素的相对位置会发生变化，算法就不稳定了

优化

在插入时，需要找到第 k 个元素插入的位置。查找的对象是有序的，那就可以在此做文章了。

查找有序的数组，可以使用折半查找的算法。折半查找，又称二分查找，实现思路如下：

  1. 初始状态下，搜索区域为整个查找表，用 left 记录搜索区域内第一个元素的位置，用 right 记录搜索区域内最后一个元素的位置。
  2. 借助 ⌊ (left + right) / 2⌋ 公式，找到搜索区域内的中间元素。
  3. 如果中间元素等于目标元素，则查找成功；否则，根据中间元素与目标元素的大小关系，确定新的搜索区域，重复步骤 2 直到查找成功或失败。
const halfFind = (array, value, left, right) => {
	if (left > right) return left;
	const mid = Math.floor((left + right) / 2);
	if (value < array[mid]) {
		right = mid - 1;
		return halfFind(array, value, left, right);
	}
	if (array[mid] <= value) {
		left = mid + 1;
		return halfFind(array, value, left, right);
	}
};

const insertSortHalf = (array) => {
	for (let i = 1; i < array.length; i++) {
		if (array[i - 1] > array[i]) {
			const temp = array[i];
			const mid = halfFind(array, temp, 0, i - 1);
			for (let j = i - 1; j >= mid; j--) {
				array[j + 1] = array[j];
			}
			array[mid] = temp;
		}
	}
};

这里定义了insertSortHalf，接收一个数组作为参数，函数中会利用折半查找对数组 array 进行排序。

排序的过程和上面一样，不同的是找插入位置的过程，假设已经利用halfFind找到了，就将 mid`` 到 i-1 的所有元素，都往后移动一位，然后将 第 k 个元素放到 mid 的位置上。

halfFind，作用是找到第 k 个元素插入的位置。过程很简单，代码也很简单，就不啰嗦了。和上面描述折半查找的步骤不同的，我们需要找的是**最后一个大于第 k 个元素的位置，而不是等于第 k 个元素的位置。**所以当array[mid] == value 时，我仍然对halfFind 进行递归调用，直到left > right，才返回 left。

这个地方有些难理解，可以自己举个例子

这是和一般折半查找不同的地方需要注意。

算法复杂度分析

对于一个混乱序列的数组，遍历的每个数都要查找在前面有序数组的位置，查找和挪动元素的复杂度 n, 又因为有 n 个元素，所以插入排序的复杂度是 O(n^2)；对于一个有序（升序）数组，查找和挪动元素的复杂度 1，又因为有 n 个元素，所以插入排序的复杂度是 O(n)；对于一个有序（降序）的数组，是最差的情况，插入排序的复杂度是 O(n^2)。

所以平均而言，插入排序的复杂度就是O(n^2)

总结

这篇文章分享了一个基础的排序算法--插入排序，讲解了两种版本的代码，两种版本都要注意算法的稳定性。文末分析了算法的复杂度，虽然介绍地有些粗糙，但大致过程就是这样了

你觉得这篇文章怎么样？我每天都会分享一篇算法小练习，喜欢就点赞+关注吧