原创

插入排序之直接插入排序和希尔排序

温馨提示：

本文最后更新于 2021年11月20日，已超过 881 天没有更新。若文章内的图片失效（无法正常加载），请留言反馈或直接联系我。

直接插入排序和希尔排序都属于插入排序，所以这里把两种算法放到一起来比较一下。
希尔排序是在直接插入排序的基础上进行改进的，所以算法很相近。
前面的文章有单独讲解两种算法的还有图解，这里就不过多的赘述。

#include <stdio.h> 
#define N 20
/**
*打印数组 
*/
void PrintArrary(char desc[],int a[],int len){
    puts(desc);
    for(int i = 0;i<len;i++){
        printf("%d ",a[i]);
    }
    printf("\n");
}
/**
*直接插入排序 
*将待排序序列分为两部分 有序序列和无序序列 
* 初始状态 第一个元素 为有序序列  从第二个元素到最后为无序序列 
*开始排序 将无序序列中的元素挨个插入到有序序列中 
*时间复杂度 最好 O(n)--初始有序 最坏O(n^2) --初始逆序 
*/ 
void insertSort(int a[],int len){
    int i,j,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;  //待排序元素插入 
    }
}
/**
*希尔排序（直接插入排序的改进） 
* 时间复杂度 最好 O(n^1.3)--我也不清楚怎么算的 最坏 O(n^2)--退化为直接插入排序 
*/ 
void shellSort(int a[],int len){
    int d ;  //增量 初始为序列长度的一半 每次减半 指导最后到 1 为止 
    int i,j,temp;
    for(d = len/2;d>0;d/=2) {
        for(i=d;i<len;i++){
            temp = a[i];
            for(j = i-d;j>=0&&a[j]>temp;j-=d){
                a[j+d] = a[j];
            }
            a[j+d] = temp;
        }
    }
} 
int main() {
    int a[N] = {4,3,8,9,6,7,2,1};
    int len = 8;
    PrintArrary("初始序列",a,len);
    insertSort(a,len);
    PrintArrary("直接插入排序",a,len);
    shellSort(a,len    );
    PrintArrary("希尔排序",a,len);
    return 0;
}

file

正文到此结束

所属分类：算法

本文标签： 排序数据结构算法
本文链接： https://www.it1997.com/article/54
版权声明： 本文由小陈没烦恼原创发布，转载请遵循《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权

插入排序之直接插入排序和希尔排序

相关文章

热门推荐

说给你听

本文目录

标签云

近期评论

网站信息