插入排序

发表于

标题：插入排序

插入排序基本思想 : 每一步将一个待排序的元素，按其排序码的大小，插入到前面已经排好序的一组元素的合适位置上去，直到元素全部插完为止。

【直接插入排序】:当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序 进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

插入排序示意图

如上图所示各趟排序后的结果 :

元素集合越接近有序, 直接插入排序算法的时间复杂度越高
最优的情况下 : 时间复杂度为 O(n)
最差的情况下 : 时间复杂度为 O(n^2)
空间复杂度 : O(1) , 它是一种稳定的排序算法

【希尔排序】: 又称缩小增量排序，是对直接插入排序的优化 , 如下图所示 , 以3为间隔 , 每次进行排序 , 使数组接近于有序 ,

这样就能减少元素后移的次数 , 这样在大量数据排序时 , 效率会大大提高 ; 在下面的测试中会有明显的差别

希尔排序示意图

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
//直接插如排序
void InsertSort(int *a, int len)
{
    assert(a);
    //由于end是从i+1开始进行排序的n,所以i要小于len-1
    for (int i = 0; i < len - 1; i++){        
    int end = i+1;        
    //使用临时变量记录end下标的值        
    int tmp = a[end];        
    //如果end下标的值小于i当前下标的值,则进行元素后移        
    if (a[end] < a[i]){            
        //由于是在已经排序好的数组插入元素,所以后移的结束条件为            
        //当end走到数组最开始的位置和临时变量不小于end-1代表的元素时            
        while (end > 0 && tmp < a[end - 1]){        
            a[end] = a[end-1];                
            end--;            
        }
    }        
    //将临时变量放到end所走到的位置        
    a[end] = tmp;
    }
}
//希尔排序(缩小增量排序)
void ShellSort(int *a, int len)
{
    assert(a);
    int idx = len;
    while (idx > 1)    {        
        //idx为每次插入排序所需要的间隔        
        idx = idx / 3 + 1;        
        for (int i = 0; i < len - idx; i++){
            int end = i + idx;            
            int tmp = a[end];            
            if (a[end] < a[i]){
                //注意:这里的判断条件和直接插入不同,由于希尔排序是跳跃式的插入排序
                //所以这里end的结束不是数组的最开始,而是i
                while (end > i && tmp < a[end - idx]){
                    a[end] = a[end - idx];        
                    end -= idx;                
                }            
            }            
            a[end] = tmp;        
        }
    }
}
void Printf(int *a, int len)
{
    assert(a);
    for (int i = 0; i < len; i++)
        printf("%d ", a[i]);
    printf("\n");
    }
int main()
{
    int a[100000] = { 0 };        
    int b[100000] = { 0 };
    srand(time(0));
    for (int i = 0; i < 100000; i++){        
    b[i] = a[i] = rand();        
    }
    int begin1 = clock();
    InsertSort(a, sizeof(a)/sizeof(int));
    int end1 = clock();
    int begin2 = clock();
    ShellSort(b, sizeof(b) / sizeof(int));
    int end2 = clock(); 
    //比较直接插入排序和希尔排序的效率
    printf("直接插入排序所需要的时间 : %d ms\n", end1-begin1);
        printf("希尔排序所需要的时间 : %d ms\n", end2-begin2); 
    system("pause");
    return 0;
}

在上面的代码中随机生成了100000个数据用直接插入排序和希尔排序分别进行测试 , 调试结果如下 :

调试结果示意图