一、shell排序

按照某种增量序列，依次操作。在处理第i个增量d时，把整个待排数组Array中，距离为d的倍数的那些记录放在同一组（作为子序列），组内进行插入排序（也可以采用其他排序方式，不过试验证明插入排序效果最好）；逐渐扩大小序列的规模，而减少小序列个数，最后所有序列都合并在一个大序列中进行一趟插入排序，从而完成排序。注意，最后一个增量并不一定是1，可以让最后一个增量是比较小的数，然后对整个数列进行一次插入排序（因为此时已经基本有序）。与交换排序不同的是，shell排序不是着眼于相邻的记录来进行比较，而是对那些不相邻的记录进行比较和交换。