插入排序
插入排序介绍
插入排序得基本思路是每次插入一个元素,每一趟完成对待插入元素得放置,直到全部插入完成。
- 直接插入排序
直接插入排序是一种最简单得排序方法,过程就是将每个待排元素逐个插入到已经排号得有序序列中。
- 折半插入排序
由于在插入排序的过程中,已经生成了一个(排好的元素组成)有序数列。所以插入待排元素时可以使用折半查找的方式,更快速的确定新元素的位置,当元素个数较多时,折半插入排序优于直接插入排序。
- 希尔排序
希尔排序可以看作是分组排序的排序方法。把全部元素分成几组(等距元素分到一组),在每一组内进行直接插入排序。然后继续减少间距,形成新的分组,进行排序,直到间距为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插入到对应的位置,外层循环结束(每次循环插入一个数)