本文主要向大家介绍了C/C++知识点之插入类排序（直接插入排序），通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

   1.直接插入排序
            1）时间复杂度：T（n）=O（n^2）;
            2）空间复杂度：S(n)=O(1);
            3）简介：直接插入排序是一种最基本的插入排序方法，直接插入排序（Straight Insertion Sorting）的基本思想是把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].
            4）直接插入排序实现：
                 eg：待排序的序列为{48，62，35，77，55，14，35，98}；
                 A）首先将待排序得数存入数组a[]中，且a[0]不赋值（a[0]是一个监哨，其作用一是临时保存待插入的记录，二是防止越界），首先将第一个数字（也就是a[1]看作已排好顺序的单元素子集合）；
                      {48}，62，35，77，55，14，35，98
                 B）其次将a[2]赋值给a[0],然后a[2]与a[1]比较，每次比较如果a[2]小于a[1]数值交换否则此次比较终止，交换后，a[1]与a[0]比较（我们可以看到无论a[1]原本的a[2]，a[0]等于原本的a[2]，所以无论如何都不会与a[0]进行交换，这就是a[0]所起到的监哨与记录的作用）本例中a[2]=62>(a[1]=48),所以不进行交换；
                       {48，62}，35，77，55，14，35，98;
                 同理：                 C）{35，48，62}，77，55，14，35，98;
                 D）{35，48，62，77}，55，14，35，98;
                 E）{35，48，55，62，77}，14，35，98;
                 F）{14，35，48，55，62，77}，35，98;
                 G）{14，35，35，48，55，62，77}，98;
                 H）{14，35，35，48，55，62，77，98};
           4）源代码：
                 typedef int KeyType;
                 typedef struct{
                                  Keytype key;
                                  OtherType other_data;
                                  }RecordType;
                 void InsSort(RecordType r[],int length)
                 {
                     for(i=2;i<=length;
                   {
                        r[0]=r[i];j=i-1;
                       while(r[0].key<r[i].key)
                        {                               r[j+1]=r[j];j=j-1;
                            }
                        r[j+1]=r[0];
                  }
                   }
                         

本文由职坐标整理并发布，了解更多内容，请关注职坐标编程语言C/C+频道！