排序算法 — 插入排序和希尔排序

插入排序算法

有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

直接插入排序

直接插入排序的排序思路是：每次将一个待排序的元素与已排序的元素进行逐一比较，直到找到合适的位置按大小插入。

例子： 有序列：

开始时，有序序列只有一个元素就是第一个元素（红色），后面的无序序列（绿色）。接下来，取无序序列中的第一个元素3，把它放到有序系列的合适位置。方法是，从有序序列的最后面向前，依次和3比较，如果比3大，就向后移动一个位置，直到找到比3小的元素，然后把3插到后面（由于后面的元素已经依次移动，所以该位置已经空出），或者有序序列中没有比3小的元素，则将3放在有序序列的第一个位置（由于移动，该位置已经空出）。最后结果为：

同样，取无序队列中的第一个元素，也就是6，然后，从有序序列的后面依次向前比较，首先是8，大于6，则向后移动（注意，8后移则会占据6的位置，所以要提前将6存一份）。接着比较3和6,3比6小，所以将6插在3的后面（也就是原来8的位置，8已经后移，该位置已空）。所以结果就是：

继续下去，直到安排好最后一个元素。

代码： 代码也很简单，主要的就是比较和后移，但要注意，要将待排序的元素多存一份，因为后移时，会占据该元素的位置。

#include<bits/stdc++.h> 
void insert_sort(int value[],int n)
{
   int i = 1;
   for(;i < n;i++)
   {
       if(value[i] < value[i - 1])
       {
           int j = i - 1;
           int temp = value[i];//value[i]的再移动的过程中会变化，所以要提前存储下来
           for(;j >= 0;j--)
           {
               if(temp < value[j])//当value[i]小于value[j]的时候，将value[j]向后移动
               {
                   value[j + 1] = value[j];
                   continue;
               }
               //否则退出循环
               break;
           }
           //退出循环时，说明value[i]大于value[j],这时，应该将value[i]放在value[j]的后面（后面一个位置已经移空）
           //还有一种情况是前面所有元素都比value[i]大
           value[j + 1] = temp;
       }
   }
}
int main()
{
   int value[] = {8,3,6,2,4,5,7,1,9,0};
   insert_sort(value,10);
   printf("排序后的结果为：\n");
   int i = 0;
   for(;i < 10;i++)
       printf("%d  ",value[i]);
   printf("\n");
   return 0;
}

上面的函数可以写的更简洁一点

 #include<bits/stdc++.h> 
void insert_sort(int value[],int n)
{
    int i = 0;
    for(i = 1;i < n;i++)
    {
        int temp = value[i];
        int j = 0;
        for(j = i - 1;j >= 0 && value[j] > temp;j--)
        {
            value[j + 1] = value[j];//移动
        }
        value[j + 1] = temp;//插入

    }
}
int main()
{
    int value[] = {8,3,6,2,4,5,7,1,9,0};
    insert_sort(value,10);
    printf("排序后的结果为：\n");
    int i = 0;
    for(;i < 10;i++)
        printf("%d  ",value[i]);
    printf("\n");
    return 0;
}

时间复杂度

只是定性的一个分析：从代码中可以看出，算法的核心就是比较和移动，如果序列本身是有序的，那么只需要n次比较，不需要移动，所以此时的时间复杂度为O(n)。如果序列是倒序的，则排第n个元素时，需要与前n-1个元素进行比较，前n-1个元素也都要后移。这样n从1取到n就是，比较和移动的次数都是0+（2-1）+（3-1）+..+(n-1)结果就是n*(n-1)/2，所以是O(n2)级别。书上说，直接插入排序的平均时间复杂度也是O(n2)级别。

是否是稳定的

是的。（稍微想一下就知道）

希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。

希尔排序算法的时间复杂度和步长的选取有关，平均时间复杂度为O(nlog2n)，最坏为O(n2)，最好为O(n).

直接插入排序更适合于原始记录基本有序的集合。这是因为如果记录基本有序，那么直接插入排序时移动的次数就会很少。而希尔排序正式利用了直接排序的这一个特点，希尔排序将数据按一定的步长进行分组，是的记录很快就会达到整体基本有序。

例子： 有序列：

首先选择一个步长，前面说过不同的初始步长会导致不同的时间复杂度，书上说，希尔排序的步长选择是一个数学难题，所以我们不要纠结。最常用的初始步长就是length/2。在这个例子中，length=9，所以初始步长step=4。然后我们将原序列分成四组（记住，步长是多少就分成多少组！！！！），分组的原则是，同一组中的元素中，每两个元素之间的下标的差为步长step。分组结果如下（相同颜色为一组）

然后，分别对每一组按照直接插入排序的方法进行排序（注意，此时每组中相邻的两个元素之间的下标差是步长step，而不是1）结果为：

然后改变步长：step=step/2，所以这一轮的步长为2，然后将数组分成两组（再次说明，步长是多少，就分多少组）。如下（相同颜色为一组）：

然后按照直接插入进行排序

然后，继续改变步长，step=step/2，所以这一轮的步长为1，此时素组就分成一组了：

然后，按照直接插入排序进行排序，

接下来改变步长，step=step/2，步长为0，结束。

写代码： 通过上面的例子我们可以看到，实际上对分成的每一个组，进行的操作还是直接插入排序，只不过处理时，要考虑相邻两个元素之间的下标差不在是1,而是step。所以，我们首先要对上面直接插入排序的函数insert_sort()进行必要的修改，加入两个参数：首元素的下标（以确定是对哪一组数据进行直接排序）和步长。如下：

#include<bits/stdc++.h> 
/**
* 修改直接插入排序的函数
* 加上了两个参数：start_index表示每组的第一个元素的下标
* step表示步长
* */
void insert_sort(int value[],int n,int start_index,int step)
{
   int i = start_index + step;
   for(;i < n;i+=step)
   {
       if(value[i] < value[i - step])
       {
           int j = i - step;
           int temp = value[i];//value[i]的再移动的过程中会变化，所以要提前存储下来
           for(;j >= 0;j-=step)
           {
               if(temp < value[j])//当value[i]小于value[j]的时候，将value[j]向后移动
               {
                   value[j + step] = value[j];
                   continue;
               }
               //否则退出循环
               break;
           }
           //退出循环时，说明value[i]大于value[j],这时，应该将value[i]放在value[j]的后面（后面一个位置已经移空）
           //还有一种情况是前面所有元素都比value[i]大
           value[j + step] = temp;
       }
   }
}
int main()
{
   int value[] = {8,3,6,2,4,5,7,1,9,0};
   insert_sort(value,10,0,1);
   printf("排序后的结果为：\n");
   int i = 0;
   for(;i < 10;i++)
       printf("%d  ",value[i]);
   printf("\n");
   return 0;
}

最后主函数中，主要任务就是分组，然后对每组数据都调用insert_sort()函数，还是再次强调：step是多少就分多少组！！！

完整代码

#include<bits/stdc++.h> 
void insert_sort(int value[],int n,int start,int step)
{
    int i = 0;
    for(i = start + step;i < n;i += step)
    {
        int temp = value[i];
        int j = 0;
        for(j = i - step;j >= start && value[j] > temp;j -= step)
        {
            value[j + step] = value[j];//移动
        }
        value[j + step] = temp;//插入

    }
}

void shell(int value[],int n)
{
    int step = n / 2;
    while(step > 0)
    {
        int i = 0;
        for(i = 0;i < step;i++)
        {
            insert_sort(value,n,i,step);
        }
        step /= 2;
    }
}
int main()
{
    int value[] = {8,3,6,2,4,5,7,1,9,0};
    shell(value,10);
    printf("排序后的结果为：\n");
    int i = 0;
    for(;i < 10;i++)
        printf("%d  ",value[i]);
    printf("\n");
    return 0;
}