算法基础:排序算法:希尔排序 心已赠人 2022-11-20 09:48 142阅读 0赞 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center] 希尔排序是一个年过花甲的排序算法,是最早一批冲进时间复杂度n平方之内的算法之一,本质上是插入算法的优化。由Shell-Metzner在1959年所提出,在很长一段时间内都是以希尔排序命名,像我这样的古老的程序员念书的时候,这个排序还是被称为希尔排序的。据说希尔本人认为这个算法不应该以他的名字命名,如果根据希尔排序的原理或者实现方式来命名的话,它可能会被命名为“一种优化的插入排序算法”或者“一种改进的增量递减的插入排序改进算法”,虽然这更像一个专利的名称。这篇文章继续介绍一下希尔排序的主要要点和实现。 ### 目录 ### * 算法思路 * 算法要点 * 模拟实现 * 结果验证 -------------------- # 算法思路 # > * 算法的思路非常简单,希尔排序是在插入排序的基础上进行的,增量递减的插入排序改进是希尔算法的核心内容,增量在算法中被称为增量,比如一个待排序列有10个元素,增量递减的思路可以进行自行定制,比如除2,首次增量为10/2=5,然后接下来为5/2=2,然后2/2=1,所以称为增量递减。 -------------------- # 算法要点 # 希尔排序的排序的要点几乎是没有什么要点: * 外层循环:实现增量递减,这里是/2的方式,还有很多其他的方式可自行拓展 * 插入排序:内层的两层循环完全就是插入排序,没有任何变动,唯一的区别是标准的插入排序是gap是1,而这里使用递减的gap换掉。 # 模拟实现 # * 插入排序:在此处仍然列出来就是为了证明,希尔排序使用的完全是插入排序的核 void insert_sort(int* arr, int num) { for (int i=1; i<num; i++) { int value = arr[i], j=i-1; for (j=i-1; j>=0 && arr[j] > value; j--) arr[j+1] = arr[j]; arr[++j] = value; } } * 希尔排序 void shell_sort(int* arr, int num) { int gap=num/2; while (gap) { for (int i=gap; i<num; i++) { int value = arr[i], j=i-gap; for (j=i-gap; j>=0 && arr[j] > value; j-=gap) arr[j+gap]=arr[j]; arr[j+gap]=value; } gap /= 2; } } > 比较一下while中的两层循环会发现,将1换成gap,代码和变量完全不需要做任何变动。 -------------------- # 结果验证 # 加上打印和调用的示例代码,可以使用如下方式进行验证 #include <stdio.h> #include <string.h> #include <stdlib.h> void shell_sort(int* arr, int num) { int gap=num/2; while (gap) { for (int i=gap; i<num; i++) { int value = arr[i], j=i-gap; for (j=i-gap; j>=0 && arr[j] > value; j-=gap) arr[j+gap]=arr[j]; arr[j+gap]=value; } gap /= 2; } } void print_array(int* arr, int num) { for (int i=0; i<num; i++) printf("%d ",arr[i]); printf("\n"); } int main() { int n = 0; while (scanf("%d",&n) != EOF) { int* array = (int *)malloc(sizeof(int)*n); memset(array,0,sizeof(int)*n); for (int i=0; i<n; i++) { scanf("%d",&array[i]); } shell_sort(array,n); print_array(array,n); free(array); array= NULL; } } 执行结果示例 8 9 8 7 6 5 4 3 2 2 3 4 5 6 7 8 9 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdW1pYW9jbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/5b8d08517d844e2cbde5429ec9ab5f2f.png
还没有评论,来说两句吧...