三种插入排序算法

直接插入排序

排序原理：

• i=1 一张牌，不存在序
• i=2 从此时开始存在了序 , j是从我摸牌之后的第一张牌，也就是第一张有序牌，还未插入
• 把刚刚摸到的这张牌，当做哨兵，即将进行插入判断
• 如果，我原本的第一张排序key 大于哨兵key时，即原有牌大于我摸的第一张有序牌（第二张牌）
• 将我原有牌后移一个单位，并从右往左查找
  • 若依然存在原本的排序key，大于哨兵key ，继续将原有牌右移一个单位， 继续左查找
  • 若原有排序key 不大于哨兵key，则跳出while循环
• 然后 将哨兵key 插入到 不大于哨兵key的排序key 后面 。

void insertsort(table *tab)
{
    int i,j;
    for(i=2;i<=tab->length;i++)
    {
        j=i-1;
        tab->r[0]=tab->r[i];
        while(tab->r[0].key<tab->r[j].key)
        {
            tab->r[j+1]=tab->r[j];
            j=j-1;
        }
        tab->r[j+1]=tab->r[0];
    }
}

关于时间复杂度

在最好情况下，直接插入排序算法的比较次数为n-1次，移动次数为2*(n-1)次。
在最坏情况下，直接插入排序算法的比较次数为(n+1)(n-1)/2次，移动次数为(n+2)(n-1)/2次。
在平均情况下，直接插入排序算法的时间复杂度为 O(n²)。另外该算法只使用了用于存放哨兵的一个附加空间。
直接插入排序算法是稳定的排序算法

---

二分法插入排序

排序原理

• 首先需要设定一个left，right，mid。
• 假设前i-1个记录已排序，因此将第i个记录的排序码与前i-1个排序码的中值做判断即可减少循环次数。
• i=2开始，从此有了序。
  • 将得到的最后一张牌，即第i张牌，放入哨兵的位置，并将left设定为有序牌的最小值，即第一张牌。
  • 将right设定为已排序的最大值，即第i-1张牌，然后开始判断。
    • 若 left小于等于right 将left和right相加取中值mid，准备将中值mid与哨兵key做比较
      • 若 中值mid大于哨兵值，就将中值mid-1作为新的最大值，
      • 若 中值mid小于哨兵值，就将中值mid+1作为新的最小值。
• 一直循环，直至当right作为的最大值小于left作为的最小值，即left为插入位置。
• 将重新从已排序的最大值和left位置之后的元素右移一个单位，插入哨兵值。

void binarysort(table *tab)
{
    int i,j,left,right,mid;
    for(i=2;i<=tab->length;i++)
    {
        tab->r[0]=tab->r[i];
        left=1,right=i-1;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(tab->r[0].key<tab->r[mid].key)
                right=mid-1;
            else
                left=mid+1;
        }
        for(j=i-1;j>=left;j--)
            tab->r[j+1]=tab->r[j];
        tab->r[left]=tab->r[0];
    }
}

关于时间复杂度

对于二分法插入排序算法，在查找第i个记录的插入位置时，每执行一次while循环体，查找范围缩小一半，和直接插入排序的比较次数对比，二分法的比较次数少于直接插入排序的最多比较次数，而一般要多于直接插入排序的最少比较次数。
总体上讲，当n较大时，二分法插入排序的比较次数远少于直接插入排序的平均比较次数，但二者所要进行的移动次数相等，故二分法插入排序的时间复杂度也是O(n²)，所需的附加存储空间为一个记录空间。
二分法插入排序算法是稳定的排序算法

---

Shell插入排序(希尔，缩小增量排序)

排序原理：

• 首先需要设定分组d，一般最好记录数的一半作为组数，然后逐渐缩小组数。
• 故将分组d设为记录长度的二分之一，当分组存在，即d大于等于1时，然后进行组内循环直接插入排序.
• 对每分组的元素逐个，进行组间同位素直接插入排序。
  • 组间直接插入排序步骤：
    ①对于每d个距离的元素，先将自身给哨兵，比较与前面距离为d的元素。
    ②若前组同位素存在(j>0),若前组同位素的key大于哨兵的key，则将前组同位素后移一组，
    ③并且比较位置前移一组，直至找到前组同位素小于当前同位素，将哨兵作为前组的后组同位素。
• 然后结束一轮分组循环，将分组再细分到原来的二分之一，继续组内排序。

void shellsort(table *tab)
{
    int i,j,d;
    d=tab->length/2;
    while(d>=1)
    {
        for(i=d+1;i<=tab->length;i++)
        {
            tab->r[0]=tab->r[i];
            j=i-d;
            while(j>0&&tab->r[0].key<tab->r[j].key)
            {
                tab->r[j+d]=tab->r[j];
                j=j-d;
            }
            tab->r[j+d]=tab->r[0];
        }
        d=d/2;
    }
}

关于时间复杂度

shell排序中算法while循环的条件中j>0是为了保证比较时不会往左移超越哨兵元素而产生越界错误。
希尔排序一般而言比直接插入排序快，但要给出时间复杂度的分析相当难。至今为止也没有找到一个最好的缩小增量序列的选取方法。时间复杂度约为
因此Shell插入排序算法是不稳定的排序算法