浅谈插入排序
插入排序,是把无序数列中的数一个个插入到有序数列中,直到无序数列没有数为止。
比如有这么一个数列: 2 4 6 1 3 5 14 2 0 10
一共有10个数,我们可以把第一个数当做有序区,剩下的数认为是在无序区; 接下来就是把无序区的数一个个插入到有序区。
怎么插入呢?
我们可以从“4”开始,先判断有序区的第一个数(这里是“2”)是否比“4”大;如果比“4”大,那就把这个数往后移动;
然后在判断这个数(“2”)原本位置的前一个数是否比“4”大(上面的数列有序区只有一个数,所以不用再往前遍历了),如果比4大,那就往后移动;依此类推,当 前一个数比“4”小或等于“4”,那就停止遍历;然后把“4”插入到最后一个往后移动的数原来的位置,这样就完成了一个数的插入。接下来循环此操作直到无序区没有数为止。
代码示例
这里只贴出算法有关代码
void insert_sort(int *array, int len)
{
for(int i = 1; i < len; i++)
{
int j = i - 1;
int ret = array[i];
while(j >= 0)
{
if(array[j] > ret)
{
array[j+1] = array[j];
j--;
}
else
{
break;
}
}
array[j+1] = ret;
}
}
调试结果
分别打印出从小到大排序和从大到小排序的结果
zzc@zzc-virtual-machine:~/share$ ./1
排序之前,数组为:39 48 29 16 48 40 37 19 33 33
排序之后,数组变为:16 19 29 33 33 37 39 40 48 48
zzc@zzc-virtual-machine:~/share$ ./1
排序之前,数组为:19 40 4 40 16 20 5 21 6 17
排序之后,数组变为:40 40 21 20 19 17 16 6 5 4
附录
总结
以上介绍了插入排序的原理,也进行了代码实现和调试。
好记性不如烂笔头,以后忘记了再回来看看。
知行合一乃终点。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)