数组-希尔排序

采用希尔排序方式对数组进行排序

希尔排序百科:希尔排序(Shell's Sort),是插入排序的一种又称“缩小增量排序”,是一种直接插入排序算法的一种更高效的改进版本.
希尔排序是把记录按下标的一定增量分组,对每组实用直接插入排序算法排序.随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法终止.
希尔排序是基于插入排序的一下以下两点性质而提出改进方法的:

1. 插入排序再对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
2. 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位.

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

基本思想:

1. 先取一个小于n的整数d1作为第一个增量,把文件的全部记录分组,所有距离为d1倍数的记录放在同一个组中.现在各组内进行直接插入排序,然后,取第二个增量d2.
2. 该方法实质上是一种分组插入方法

算法分析:

1. 时间复杂度O(_n^3/2)
   时间复杂度下限是 n*log2n.希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n²)复杂度的算法快得多。希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。
2. 算法稳定性
   由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的.
   综上,希尔排序是一种不稳定排序算法.

代码实现-Swift版本:

func shellSort(nums: inout [Int]){
    // 设置增量
    var increment = nums.count / 2
    
    while increment > 0 {
        for i in increment ..< nums.count {
            var leftIndex = i - increment// 找到增量位置和增量对应位置的索引
            while leftIndex >= 0 {
                if nums[leftIndex] > nums[leftIndex+increment] {
                    // 如果对应位置数大,则交换
                    nums.swapAt(leftIndex, leftIndex+increment)
                }
                leftIndex -= increment
            }
        }
        increment = increment / 2
    }
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 希尔百科

考察要点:

• 数组
• 排序