插入排序是一种简单的排序方法，因为的实现比较简单，所以在数据量较少时应用很广泛。插入排序根据其插入的不同方式，可以分为直接插入排序，折半插入排序，2-路插入排序，表插入排序和希尔排序。在这里我将一一写出各种插入排序的算法代码。直接插入排序template <class T>void InsertSort(T a[], int len){      int i, j;      T temp;      for (i=1; i<len; i++)      {            temp = a[i];            for (j=i-1; j>=0 && a[j]>temp; j--)//元素后移                  a[j+1] = a[j];            a[j+1] = temp;  //插入      }}      有些算法把a[0]设置为临时数据存放处（即原数组中a[0]未存储元素），这样就可以少进行一些判断，在数据量较大时可以节省一些时间，算法如下：template <class T>void InsertSort(T a[], int len){      int i, j;      for (i=1; i<len; i++)      {            a[0] = a[i];            for (j=i-1; a[j]>temp; j--)                  a[j+1] = a[j];            a[j+1] = a[0];      }} 折半插入排序法      由于插入排序的基本操作是在一个有序表中进行查找和插入，则这个查找操作可以利用折半查找来实现。但是折半插入排序仅减少了元素间的比较次数，而元素的移动次数不变，因此折半插入排序法的时间复杂度仍为O(n^2)。算法如下：template <class T>void HalfInsertSort(T a[], int len){      int i, j;      int low, high, mid;      T temp;      for (i=1; i<len; i++)      {            temp = a[i];            low = 0;            high = i - 1;            while (low <= high) //在a[low。。。high]中折半查找有序插入的位置            {                  mid = (low + high) / 2;                  if (a[mid] > temp)                        high = mid - 1;                  else                        low = mid + 1;            } //while                        for (j=i-1; j>high; j--)//元素后移                  a[j+1] = a[j];            a[high+1] = temp; //插入      }//for}希尔排序法      希尔排序法又称缩小增量排序法，它也是插入排序类的方法，但在时间效率上较前面几种插入排序算法有较大的改进。      希尔排序法通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到比较相邻元素的最后一趟排序为止。算法如下：template <class T> void ShellSort(T a[], int len)//Shell增量序列h（t）= N/2和h（k） =  h（k+1）/2。 {       for (int increase=len/2; increase>0; increase/=2)       {             for (int i=increase; i<len; i++)             {                   T temp = a[i];                   int j = i;                   for (; j>=increase; j-=increase)//元素后移                   {                         if (temp < a[j-increase])                               a[j] = a[j-increase];                         else                               break;                   }                   a[j] = temp; //插入             }//for       }//for } 注：缺2-路插入排序和表插入排序，有意者请补上！谢谢！   补充：我上面的希尔排序排序程序中使用的增量序列（increment）是Shell建议的序列h（t）= N/2和h（k） =  h（k+1）/2。这个序列并非最好的序列，使用希尔增量时希尔排序的最坏情形运行时间为O（N^2）。Hibbard提出一个稍微不同的增量序列，它在实践（并且理论上）给出更好的结果。他的增量形如1，3，7，…，2^k – 1。虽然这些增量几乎是相同的，但关键的区别在于相邻的增量没有公共因子。使用Hibbard增量时希尔排序的最坏情形运行时间为O（N^（3/2））。Sedgewick提出了几种增量序列，其最坏情形运行时间达到O（N^（4/3）），经验研究指出，在实践中这些序列的运行要比Hibbard的好得多，其中最好的序列是{1，5，19，41，109，…}，该序列中的项或者是9*4^i — 9*2^ i + 1， 或者是4^i — 3*2^ i + 1。通过将这些值按顺序放到一个数组中可以最容易地实现该算法。（摘自《数据结构与算法分析---c语言描述》，Mark Allen Weiss著）补充一个Hibbard增量的希尔排序法： template <class T> void ShellSort(T a[], int len)//Hibbard增量序列1，3，7，…，2^k - 1 {      int k = 0;      for (int n=len; n>3; n>>=1)             ++k;          int increase = (1 << k) - 1;//求出最大的增量值2^k - 1         for (; increase>0; increase/=2)       {             for (int i=increase; i<len; i++)             {                   T temp = a[i];                   int j = i;                   for (; j>=increase; j-=increase)//元素后移                   {                         if (temp < a[j-increase])                               a[j] = a[j-increase];                         else                               break;                   }                   a[j] = temp; //插入             }//for       }//for }  

评论