插入排序的基本思想是，每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

//插入排序与打扑克时整理手上的牌非常类似。

----------------------------------------------------
直接插入排序的基本思想
    1.直接插入排序的基本思想是，把n个待排序的元素看成为一个有序表和一个无需表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素。
排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次即可完成排序过程。

    把a[i]插入到a[0],a[1],...,a[i-1]之中的具体实施过程为：
先把a[i]赋值给t，然后将t依次与a[i-1]，a[i-2]，....进行比较，
将比t大的元素右移一个位置，直到发现某个j(0<=j<=i-1)，使得a[j]<=t或j为(-1),
把t赋给a[j+1]。

---------------------

     2.
  通常将一个记录R[i](i=2,3,...,n-1)插入到当前的有序区，使得插入后仍保证该区间里的记录是按关键字有序的操作称第i-1趟直接插入排序。
  
   排序过程的某一中间时刻，R被划分为俩个子区间R[1....i-1](已排好序)和R[i...n](当前未排序的部分，无序区)。

   直接插入排序的基本操作是将当前无序区的第i个记录R[i]插入到R[1....i-1]中适当的位置，使R[1....i]变为新的有序区。因为这种方法每次使有序区增加一个记录，通常称增量法。

   插入排序与打扑克时整理手上的牌非常类似。摸来的第一张牌无需整理。
此后每次从桌上的牌(无序区)中摸最上面的一张并插入左手的牌(有序区)中正确的位置。
为了找到这个正确的位置，须自左向右将摸来的牌与左手中已有的牌逐一比较。

------------------------------------------ 

   好了，根据以上的算法，可以写程序实现了。自己水平有限哈。

我写的测试代码如下：

#include <iostream>
using namespace std;

void insert_sort(int a[],int length)
{
 int t;
 for(int i=0;i<length;i++)
 {
  t=a[i];    //将待排序的元素a[i]赋给t

  for(int j=i-1;j>=0&&a[j]>t;j--)
  {
   a[j+1]=a[j];   //把比t大 （a[j]>t） 的元素，全部后移一个位置
  }
  a[j+1]=t;       //把待排序的t插入到a[j+1].完成插入排序过程。
 }
}

int main()
{
 int a[5]={12,5,41,36,89};
 insert_sort(a,5);
 for(int i=0;i<5;i++)
  cout<<a[i]<<" ";
 return 0;
}

 http://s4/middle/5e3ab00cx88c865a331f3&690[原创]" TITLE="排序问题：直接插入排序的算法思想 [原创]" />

//一分钟搞定。0 Bug。 

熬夜的唯一好处，在于自由。能增强你的自信。

你觉得，眼前的东西，尽在你的掌握之中。July、06.12。晚安。