经典算法---插入排序

简介: 插入排序得基本思路是每次插入一个元素,每一趟完成对待插入元素得放置,直到全部插入完成。

插入排序

插入排序介绍

插入排序得基本思路是每次插入一个元素,每一趟完成对待插入元素得放置,直到全部插入完成。

  • 直接插入排序

直接插入排序是一种最简单得排序方法,过程就是将每个待排元素逐个插入到已经排号得有序序列中。

  • 折半插入排序

由于在插入排序的过程中,已经生成了一个(排好的元素组成)有序数列。所以插入待排元素时可以使用折半查找的方式,更快速的确定新元素的位置,当元素个数较多时,折半插入排序优于直接插入排序。

  • 希尔排序

希尔排序可以看作是分组排序的排序方法。把全部元素分成几组(等距元素分到一组),在每一组内进行直接插入排序。然后继续减少间距,形成新的分组,进行排序,直到间距为1时停止。

直接插入排序

  • 输入

n个数的序列,通常直接存放在数组中,可能是任何顺序

  • 输出

输入序列的一个新排列,满足从小到大的顺序,默认升序,简单修改可以实现降序

  • 算法说明

每次从原有数据中取出一个数,插入到之前已经排好的序列中,直到所有的数全部取完,那么新的有序排列也就完成了。
通俗一点的解释就好比我们在打扑克牌,所有的牌扣在桌面上,我们一张一张的抓,抓起一张就在手里把它排好,那么我们把所有的牌都抓起来之后,手里的牌也就是有序的了

  • 算法流程

对于计算机来说,我们必须要详细的告诉它如何比较大小,以及如何确定位置,毕竟它不能像我们一样,一眼就看出位置。试想一下,当数据量比较多的时候,我们也需要一个一个的看过来,然后才能确定新插入元素的位置,整个过程如下:
1 第一个元素:放在第一个位置,直接排好
2 第二个元素: 与第一个元素比较,如果更大,放在第二个位置,如果更小,放在第一个位置
3 第三个元素:顺次从后向前比较,如果更小,将已排好的元素向后串位,直到找到合适的位置插入
4 剩余其它元素: 顺次从后向前比较,如果更小,将已排好的元素向后串位,直到找到合适的位置插入
5 如果待排元素是已经排好元素中最大的,只需要比较一次,然后直接追加到已排好的序列后面

直接插入排序伪代码

for j=2 to A.length
    key = A[j]
    i=j-1
    while i>0 and A[i]>key
        A[i+1]=A[i]
        i = i -1 
    A[i+1] = key

初始计数器为2 , 代表第一个元素默认排好,从第二个元素开始操作,直到最后一个元素
每次用key记录新操作的元素,i的初始值代表当前操作元素的前一个元素,也就是第一个要与之比较的元素。
while循环为内层循环,作用是已经排号的元素中找到合适的位置,来将key插入。
如果进入到循环体中执行,代表key相对较小,还要再向前寻找,同时,与之比对的元素要向后串位,因为此时可以确定,key一定在这个for循环的最后一行是将key插入到对应的位置,外层循环结束(每次循环插入一个数)

相关文章
|
2月前
|
算法 搜索推荐
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
本文介绍了冒泡排序、选择排序和插入排序三种基础排序算法的原理、实现代码和测试结果。
21 0
数据结构与算法学习十一:冒泡排序、选择排序、插入排序
|
2月前
|
搜索推荐 算法
【排序算法(一)】——插入排序,选择排序 —> 深层解析
【排序算法(一)】——插入排序,选择排序 —> 深层解析
|
5月前
|
算法 搜索推荐 C#
|
6月前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
6月前
|
算法 搜索推荐
数据结构与算法-插入排序
数据结构与算法-插入排序
32 2
|
6月前
|
算法 搜索推荐 数据可视化
【漫画算法】插入排序:插入宝石的传说
【漫画算法】插入排序:插入宝石的传说
|
6月前
|
人工智能 搜索推荐 JavaScript
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
40 0
|
6月前
|
机器学习/深度学习 搜索推荐 算法
【C/排序算法】:直接插入排序和希尔排序
【C/排序算法】:直接插入排序和希尔排序
45 0
|
6月前
|
搜索推荐 算法
排序算法之插入排序
排序算法之插入排序
45 0
|
6月前
|
搜索推荐
排序算法---插入排序-----详解&&代码
排序算法---插入排序-----详解&&代码