插入排序(Insertion Sort)是一种简单直观的排序算法,其核心思想是逐步构建有序序列,对于每个未排序的元素,在已排序部分找到合适的位置插入。本文将深入研究插入排序的原理、实现方式等
插入排序是一种基于比较的排序算法,其基本思想是通过构建有序序列,不断将未排序的元素插入到已排序部分的适当位置。插入排序的实现过程类似于我们整理扑克牌的方式,逐个将牌插入到已有的有序牌中。
以下是一个基于 JavaScript
的插入排序实现:
js// 插入排序函数
function insertionSort(arr) {
const n = arr.length;
for (let i = 1; i < n; 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;
}
// 示例
const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = insertionSort(unsortedArray);
console.log(sortedArray); // 输出 [11, 12, 22, 25, 64]
通过逐步将未排序的元素插入到已排序的部分,插入排序不断构建有序序列。
尽管插入排序在最坏情况下的时间复杂度较高,但在实际应用中,当数据集较小时,插入排序表现出色。同时,插入排序的实现相对简单,适用于小规模数据或已经基本有序的数据。
插入排序的平均时间复杂度为O(n^2)
,其中n是数组的长度。最好情况下是O(n)
,当数组已经有序时。
插入排序是一种原地排序算法,不需要额外的空间来存储临时数据,因此其空间复杂度为O(1)
。
插入排序是一种直观简单的排序算法,通过构建有序序列逐步插入未排序元素。尽管其时间复杂度不如一些高级排序算法,但在某些场景下具有良好的性能表现。在实际应用中,需要根据数据规模和性能需求选择合适的排序算法,权衡算法的优劣。
本文作者:CreatorRay
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!