- 1.因为这个排序是一个叫希尔的人发明的,所以就叫希尔排序了
- 2.希尔排序是插入排序的升级版
- 3.根据其排序的特点又叫做缩小增量排序
- 4.插入排序就是增量为1的希尔排序
希尔排序的大体步骤
- 1、先将无序序列按照一定的步长(增量)分为几组
- 2、别将这几组中的数据通过插入排序的方式将其进行排序
- 3、然后缩小步长(增量)分组,然后将组内的数据再次进行排序。直到增量为1位置
具体代码
func sort(items: Array<Int>) -> Array<Int> {
var list = items
var step: Int = list.count / 2
while step > 0 {
print("步长为\(step)的插入排序开始:")
for i in 0..<list.count {
var j = i + step
while j >= step && j < list.count {
if list[j] < list[j - step] {
let temp = list[j]
list[j] = list[j-step]
list[j-step] = temp
j = j - step // 结束while循环
} else {
break
}
}
}
print("步长为\(step)的插入排序结束")
print("本轮排序结果为:\(list)\n")
step = step / 2 //缩小步长
}
return list
}
示例
希尔排序 [2, 8, 9, 3, 5]
步长为2的插入排序开始:
步长为2的插入排序结束
本轮排序结果为:[2, 3, 5, 8, 9]
步长为1的插入排序开始:
步长为1的插入排序结束
本轮排序结果为:[2, 3, 5, 8, 9]
希尔排序:时间复杂度—-O(n^(3/2))
反过来理解:步长为1是相邻两个数依次两两比较,步长为2是隔一个数依次进行的两两比较