希尔排序

希尔排序又称“缩小增量排序”,是对直接插入排序方法的改造。

希尔排序是一种不稳定的排序方法。基本思想是将整个待排记录序列分割成若干子序列,然后分别进行插入排序,带整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。具体做法是先取定一个小于n的整数d1作为第一增量,把文件的全部记录分成d1组,将所有距离为d1倍数的记录放在同一组中,在各组内进程插入排序;然后取第二个增量d2(d2 < d1),重复上述的分组和排序工作,依次类推。直至所取的增量di=1,既所有记录放在同一组进行直接插入排序为止。

增量序列为5,3,1时,希尔插入排序过程如下图:


函数如下:


©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容