插入排序的实现原理是什么？怎样实现插入排序

发布时间：

2023-04-06
版权所有：

云和教育
分享：

插入排序是冒泡排序的优化，是一种直观的简单排序算法。它的实现原理是，通过构建有序数组元素的存储，对于未排序的数组元素，在已排序的数组中从最后一个元素向第一个元素遍历，找到相应位置并插入。其中，待排序数组的第1个元素会被看作是一个有序的数组，从第2个至最后一个元素会被看作是一个无序数组。如按照从小到大的顺序完成插入排序，如图3-10所示。

图3-10插入排序从图3-10可以看出，插入排序比较的次数与无序数组的长度相等，每次无序数组元素与有序数组中的所有元素进行比较，比较后找到对应位置插入，最后即可得到一个有序数组。了解插入排序实现的原理后，下面使用JavaScript实现插入排序。具体如例3-5所示。

【例3-5】demo05.html

< script >
    var arr = [89, 56, 100, 21, 87, 45, 1, 888]; // 待排序数组
console.log('待排序数组：' + arr);
// 按照从小到大的顺序排列5for (vari = 1; i < arr.length; ++i) {// 遍历无序数组下标
for (var j = i; j > 0; --j) { // 遍历并比较一个无序数组元素与所有有序数组元素
    if (arr[j - 1] > arr[j]) {
        [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
    }
}
}
// 输出从小到大排序后的数组
console.log('排序后的数组：' + arr); 
</script>

在上述代码中，我们假设待查找的数组arr的第1个元素是一个按从小到大排列的有序数组，arr剩余的元素为无序数组。然后通过第5~11行代码完成插入排序。其中，第7~9行代码用于无序数组元素与有序数组中的元素进行比较，若无序元素arr[j]小于有序数组中的元素，则进行插入。效果如图3-11所示。

图3-11插入排序法

插入排序的实现原理是什么？怎样实现插入排序

最新开班信息

课程咨询

云和热门培训课程

推荐阅读