排序算法之希尔排序

概述

希尔排序是插入排序的一种更高效的改进版本.

希尔排序的基本思想是: 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

就是将插入排序分组一下

分组排序步骤如下:

1. 选定一个增量, 即将数组分为几组
2. 根据增量分别对几个分组进行插入排序
3. 减小增量, 重复步骤1-2, 直到增量为1进行最后一次排序

 

其时间空间复杂度为:

 

Java代码实现