之所以标题加上"(直接)"的字眼, 是因为有许多时间复杂度为更低的算法都是对这个最原始/直接的插入排序算法优化演变出来的. 所以他们也可以算是插入排序. 当然, 这里我们要说的是最原始最直接的插入排序.
插入排序: O(n ^ 2)
插入排序（InsertSort）的基本思想是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数,然后把第二个数按大小插入到有序表中;
第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。插入排序类似玩牌时整理手中纸牌的过程。
第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。插入排序类似玩牌时整理手中纸牌的过程。
插入排序是稳定的排序方式.
代码如下:
PS: 其实是昨晚写的, 今天整理出来. 半夜实在头昏脑涨, 写了三遍, 才最终演化成最后那种稍好的形式...
for (i = 1; i < n; i++) //从1到n-1, 往前面插
{
temp = a[i]; //要插入的值为a[i]
for (j = i; j > 0; j--); //从a[i-1]开始依次往前比较
{
if (temp >= a[j-1]))
{
break;
}
}
if (j < i) //则a[j]的位置就是a[i]需要插入的地方, a[j]...a[i-1]先依次往后移
{
for (k = i; k > j; k--)
{
a[k] = a[k-1]
}
a[j] = temp;
}
}
看了眼标准的算法实现, 发现丑爆了, 而且确实麻烦了, 没必要先找出位置,
再移动. 可以一边找就一边移动了, 就不用费二遍事了.
遂改成了下面这样..
for (i = 1; i < n; i++) //从1到n-1, 往前面插
{
temp = a[i]; //要插入的值为a[i]
for (j = i - 1; (j >= 0) && (temp < a[j]); j--) //从a[i-1]开始依次往前比较
{
swap(temp, a[j]);
}
}
仔细和标准的算法实现对比了下, 发现这种实现像冒泡, 不是插入..
效率上来说一个swap是三个语句, 效率确实还是低
遂进一步修改成了最终版..
for (i = 1; i < n; i++) //从1到n-1, 往前面插
{
temp = a[i]; //要插入的值为a[i]
for (j = i; (j > 0) && (temp < a[j-1]); j--) //如果temp比a[j-1]小, 则a[j-1]的值向后移动一个单位.
{
a[j] = a[j-1];
}
a[j] = temp;
}
总结: 插入排序, 相当于待插入元素是游离于"队伍"外面, 看到比自己大的, 就让其后退一步, 直到找到合适自己的位置, 直接站进队伍里. 上面第二种实现 , 相当于待插入元素是在队里里面, 拍拍前面人的肩膀, "嗨, 哥们, 你太高了, 咱俩换下位置, 你站我后面去." 这个依次交换的方式显然是冒泡的方式了,
插入, 不是"交换", 而是"移动", 最后一锤定音, 插进去! ^ ^