Swift.希尔排序

import Foundation

class ShellSortSolution {
    func sort(_ n: [Int]) -> [Int] {
        
        var s = n
        var gap = n.count/2
        
        while gap > 0 {
            
            var i = gap
            while i < n.count {
                
                var j = i
                while j > 0 && j - gap >= 0 {
                    
                    if s[j - gap] > s[j] {
                        let temp = s[j]
                        s[j] = s[j - gap]
                        s[j - gap] = temp
                    }else {
                        break
                    }
                    
                    j -= gap
                }
                
                i += 1
            }
            
            gap /= 2
        }
        
        return s
    }
}

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

github地址：https://github.com/cubegao/LeetCode