数据结构和算法之插入排序

一、插入排序

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

这个流程图描述了插入排序的过程。初始数组经过选择一个待插入元素的步骤，并判断是否有元素。如果有元素，则将它插入到已排序区间，并重新确定未排序区间。如果没有元素，则排序完成。

js实现：

function insertionSort(arr) {// 循环每个元素，从第二个元素开始for (let i = 1; i < arr.length; i++) {// 当前元素let current = arr[i];// 设置当前元素的前一个元素的下标let j = i - 1;// 当前元素与它前面的元素比较，如果前面的元素较大，则向右移动while (j >= 0 && arr[j] > current) {arr[j + 1] = arr[j];j--;}// 将当前元素插入到正确的位置arr[j + 1] = current;}// 返回排序后的数组return arr;
}let array = [5, 3, 8, 2, 1, 4];
console.log(insertionSort(array));  // 输出：[1, 2, 3, 4, 5, 8]

这里使用插入排序算法对数组 [5, 3, 8, 2, 1, 4] 进行排序。首先，第一个元素 5 被标记为已排序序列，从第二个元素开始，依次与已排序序列中的元素比较，找到合适的位置插入。在每一轮循环中，当前元素会与已排序序列中的元素从后向前依次比较，直到找到插入位置。

初始数组：[8, 3, 5, 1, 4]

插入元素	过程描述	排序后的数组
8	初始状态	[8, 3, 5, 1, 4]
3	将3插入到前面比它大的数之前	[3, 8, 5, 1, 4]
5	将5插入到前面比它大的数之前	[3, 5, 8, 1, 4]
1	将1插入到前面比它大的数之前	[1, 3, 5, 8, 4]
4	将4插入到前面比它大的数之前	[1, 3, 4, 5, 8]

最终排序结果：[1, 3, 4, 5, 8]

插入排序的过程可以类比现实生活中整理扑克牌的过程。初始时，我们手里有一摞乱序的扑克牌。我们从第二张牌开始，将其与前面的牌依次比较，找到合适的位置插入。重复这个过程，直到所有的牌都被按照顺序放置在手上。每次比较时，左手持有的牌都是已排序的，右手持有的牌都是未排序的。这个过程就是插入排序的模拟。

二、使用二分法优化插入排序

可以使用二分法优化上述插入排序算法。二分法优化的思想是将插入排序中的线性查找部分改为二分查找，从而减少比较的次数，提高排序效率。

以下是使用二分法优化的插入排序算法：

function insertionSort(arr) {for (let i = 1; i < arr.length; i++) {let current = arr[i];let left = 0; // 排序部分的起始位置let right = i - 1; // 排序部分的结束位置// 使用二分查找找到插入位置while (left <= right) {let mid = Math.floor((left + right) / 2);if (arr[mid] > current) {right = mid - 1;} else {left = mid + 1;}}// 将大于current的元素右移for (let j = i - 1; j >= left; j--) {arr[j + 1] = arr[j];}// 插入到正确的位置arr[left] = current;}return arr;
}

使用二分法优化后，排序效率会有所提高，但在数据量较小时可能没有明显的优势。因此，在实际应用中需要根据具体情况选择是否使用二分法优化。