Lugick Wang's Blog
0%

排序算法——希尔排序

发表于 Disqus：

前言

希尔排序，以从小到大排序为例。

原理

将数据按步长进行分组，每组分别进行插入排序。初始步长为 N，后每次都除以 2。最后步长为 1 即进行插入排序。

算法实现

Wiki

swift 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func shellSort(array: inout [Int]) -> [Int] {
    let n = array.count
    //初始步长
    var gap = n / 2
    while gap > 0 {
        for i in gap..<n {
            //插入排序
            let temp = array[i]
            var j = i
            
            while j >= gap && array[j-gap] > temp {
                array[j] = array[j-gap]
                j -= gap
            }
            array[j] = temp
        }
        
        //新步长
        gap = gap / 2
    }
    print(array)
    return array
}

例子

1
2
3
4
var shellArray = [49,38,65,97,76,13,27,49,55,4]
shellSort(array: &shellArray)

[4, 13, 27, 38, 49, 49, 55, 65, 76, 97]

动画展示

希尔排序