教育行业A股IPO第一股(股票代码 003032)

全国咨询/投诉热线:400-618-4000

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

更新时间:2022年03月25日15时37分 来源:传智教育 浏览次数:

插入排序是冒泡排序的优化,是一种直观的简单排序算法。它的实现原理是,通过构建有序数组元素的存储,对于未排序的数组元素,在已排序的数组中从最后一个元素向第一个元素遍历,找到相应位置并插入。其中,待排序数组的第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插入排序法




猜你喜欢:

什么是冒泡排序?手写一段冒泡排序的代码

JS如何实现数组随机排序?JS数组随机排序的3种方法

Hadoop如何实现二次排序?

列表的排序过渡

传智教育web前端培训课程

0 分享到:
和我们在线交谈!