内部排序之---插入类排序

一：插入类排序
1：直接插入排序：
【算法思想】最基本的操作是将第i个记录插入到前面i-1个以排好序列的记录中。具体过程是：将第i个记录的关键字K依次与其前面的i-1个已经拍好序列的记录进行比较。将所有大于K的记录依次向后移动一个位置，直到遇到一个关键字小于或等于K的记录，此时它后面的位置必定为空，则将K插入。
【过程】大括号中的为已经排好序列的元素
A:{48} 62 35 77 55 14 35 98
B:{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//假设排序序列在1～len之间，则r[0]为空，可以作为监视哨始终存放待插入
H:{14 35 35 48 55 62 77 98}//记录
【算法特点】
1）使用监视哨r[0]临时保存待插入的记录
2）从后往前查找应插入的位置
3）查找与移动采用一个循环完成。

从空间角度上看：它只需要一个辅助空间r[0]
从时间消耗上看：主要时间消耗在关键字比较和移动
对于一趟插入排序，算法中的while循环次数主要取决与待插入记录与i-1个记录的关键字关系。
最好情况为（顺序）：r[i]>r[i-1],while循环值执行一次，并且不移动记录
最差情况为（你序）：r[i]对于整个排序过程而言，最好情况是排序记录本身已经按照关键字有序排列，总的比较次数为n-1此，移动记录的次数也达到最小2(n-1) 最坏情况是排序记录本身为逆序，此时总的比较次数达到(n 2)(n-1)/2，记录移动的次数也达到了最大值(n 4)(n-1)/2                     时间复杂度为O(n^2),空间复杂度为O(1)

它是稳定的排序方法。由于是从后往前进行的，循环while的判断条件就保证了后面出现的关键字不可能插入到前面相同的关键字之前。
附直接插入算法：

void Insort(int r[],int len)
{
int i,j;
for(i=2;i<=len;i  )
{
r[0]=r[i];
j=i-1;
while(r[0]<r[j])
{
r[j 1]=r[j];
j=j-1;
}
r[j 1]=r[0];
}
}

2：折半插入排序
【算法思想】对于有序表的折半查找，性能优于顺序查找所以折半查找用于有序记录r[1~i-1]之间。采用折半插入排序，可以减少关键字的比较次数，如要插入第i个元素，则需要进行log2i次比较，因此插入n-1个元素的平均关键字的比较次数为n(log2n)，然而，虽然折半插入排序与直接插入排序法相比，改善了算法中比较次数的数量级为O（nlong2n）,但是未能改变移动元素的时间耗费，所以折半的总时间复杂度仍然为O(n^2).
【过程】
A：48要插入62
r[0]=62,low=1,high=1
while(low<=high)
{mid=1;  if r[1]=48<62    high=mid-1=0   low>high  break; }
r[low]=r[1]=r[0]=62
B：48 62要插入35
r[0]=35,low=1,i=3,high=2
while(low{mid=1; if(35high,break;}
for(j=i-1=2;j>=low(1);--j)     r[j+1]=r[3]=r[j]=r[2]=62
循环j=1          r[j+1]=r[2]=r[j]=r[1]=48
出循环             r[low]=r[1]=r[0]=35//依次类推

附上算法
 

void Binsort(int r[],int len)
{
   int i,low,high;
  for(i=2;i<=len;i++)
   {
    r[0]=r[i];
    low=1;
     high=i-1;
   while(low<=high)
   {
    mid=(low+high)/2
   if(r[0]<r[mid])
  high=mid-1;
   else
   low=mid+1;
   }
for(j=i-1;j>=low;--j)
   r[j+1]=r[j];
  [low]=r[0];
  }
  }

3：希尔排序
【算法思想】在待排序的关键字序列基本有序且关键字个数n较少，其算法性能最佳
1）将待排序的关键字序列分为若干个较小的自诩列，对自子序列进行直接插入排序使得整个待排序序列排序。
2）在进行直接插入排序时候，若待排序列已经有序，直接插入排序的时间复杂度可以提高到O(n).若待排序序列基本有序时候，即序列中具有下列特性的记录较少：
r[i]【过程】
1）首先选定记录间的距离d1，在整个待排序记录序列中将所有间隔为d的记录分成一组进行组内直接插入排序
2）然后取i=i+1,记录间的举例为d2.在整个待排序序列中，将所有时间间隔为d2的记录分成一组，进行组间直接插入排序
重复多次，直至d=1

A：取d=4,分为4个间隔为4的子序列，各个自序列内进行插入排序
46      55      13     42      94      17      5      70
注释：46与94相比教46<94不变，55与17比较55>17,将55与17交换位置，13与5相比，交换位置，42与70比较，不变。则第一次结果为：
46     17       05     42      94      55      13    70
B：取d=2,分为2个间隔为2的自序列进行插入排序
注释：46与5比交换，17与42比不交换，然后46与96比不交换，42与55比，不交换，94与13比交换，55与70比不交换。则第二次的结果为：
5      17      13       42       46      55     94     70
C：取d=1,分为一个间隔的子序列，最后结果为
5      13       17      42      46       55      70     94
附上算法代码：

void shellInsert(int r[],int len,int d)
   {
   for(i=1+d;i<=len;i++)
    if(r[i]<r[i-d])
    r[0]=r[i];//先将较小的元素放到r[0]中保存
    for(j=i-d;j>0&&r[0]<r[j];j-=d)
    r[j+d]=r[j];//这里相当与r[i]=r[i-d];
    r[j+d]=r[0];//这里相当与r[i-d]=r[0];
   }//其实总的看下来仍然相当与简单排序法中的交huan


   void shellsort(int r[],int len,int delta[],int n)
   {
   int i;
   for(i=0;i<=n-1;i++)
     shellInsert(r,len,delta[i])
  }

【算法分析】
（1）时间复杂度为o(n^1.5)
（2）算法不稳定