插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。
算法步骤
步骤一：定义函数
首先，我们需要定义一个插入排序的函数，该函数接收一个数组作为参数，并返回排序后的数组。
// www.javascriptcn.com code example
function insertionSort(arr) {
// 克隆原始数组，避免修改原数组
let arrCopy = arr.slice();
let len = arrCopy.length;
// 从第二个元素开始遍历
for (let i = 1; i < len; i++) {
// 当前需要排序的元素
let key = arrCopy[i];
// 已排序的子数组的最后一个索引
let j = i - 1;
// 将当前元素与已排序部分的元素进行比较
while (j >= 0 && arrCopy[j] > key) {
// 向右移动元素
arrCopy[j + 1] = arrCopy[j];
j--;
}
// 插入当前元素到正确的位置
arrCopy[j + 1] = key;
}
return arrCopy;
}步骤二：测试代码
接下来，我们可以通过一些测试用例来验证插入排序函数的正确性。
// 测试数据
const testArray = [64, 34, 25, 12, 22, 11, 90];
// 调用插入排序函数
const sortedArray = insertionSort(testArray);
console.log("Sorted array is:", sortedArray);步骤三：分析算法的时间复杂度和空间复杂度
时间复杂度
插入排序的时间复杂度在最好情况下为O(n)，因为如果输入数组已经是排序好的，那么每次只需要比较而不需要移动元素。在最坏的情况下，时间复杂度为O(n^2)，这是因为当数组是逆序的时候，每次都需要将每个元素移动到数组的最前端。
空间复杂度
由于插入排序是在原地进行排序，因此它的空间复杂度为O(1)，即只使用了常数级别的额外空间。
插入排序的优点和缺点
优点
- 简单易懂：实现非常简单，容易理解和实现。
- 高效于小规模数据：对于少量元素的数据集，插入排序比更复杂的算法如快速排序或归并排序更有效率。
- 稳定性：插入排序是一个稳定的排序算法，即相等的元素不会改变原有的顺序。
缺点
- 效率低：对于大规模数据集，插入排序的效率很低，因为它的时间复杂度为O(n^2)。
- 不适合随机分布的数据：如果数据是随机分布的，插入排序可能需要进行大量的比较和移动操作。
应用场景
插入排序虽然不是所有情况下的最佳选择，但在某些特定场景下仍然非常有用：
- 小数据集：当处理的数据量较小的时候，插入排序的开销可以忽略不计。
- 部分排序的数据：当输入数组已经接近排序时，插入排序能很好地利用这种局部有序性。
- 在线算法：当数据项是逐个到达，而需要实时更新排序列表时，插入排序可以很好地适应这种情况。
扩展阅读
为了进一步了解插入排序及其变种，你可以参考以下资源：
通过上述步骤，我们不仅学习了如何实现插入排序算法，还掌握了其工作原理、适用场景及性能特点。希望这些知识对你理解JavaScript中的排序算法有所帮助。