网站开发培训-高端面授网站开发培训机构
云和教育:云和数据集团高端IT职业教育品牌
  • 华为
    授权培训中心
  • 腾讯云
    一级认证培训中心
  • 百度营销大学
    豫陕深授权运营中心
  • Oracle甲骨文
    OAEP中心
  • Microsoft Azure
    微软云合作伙伴
  • Unity公司
    战略合作伙伴
  • 普华基础软件
    战略合作伙伴
  • 新开普(股票代码300248)
    旗下丹诚开普投资
  • 中国互联网百强企业锐之旗
    旗下锐旗资本投资

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

  • 发布时间:
    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插入排序法