排序算法---希尔排序

1. 基本思想?

希尔排序是插入排序的一种，它与直接插入排序不同的是，它会优先比较距离较远的元素，因此希尔排序又被称为“缩小增量排序”。希尔排序的实现思路是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

?2. 实现逻辑

（1）首先选取一个步长gap,通常是数组长度的一半，向上取整和向下取整都可以

（2）所有距离为gap的倍数的记录放在同一个组中，在各组内进行直接插入排序。

（3）改变步长 gap = gap/2,? 重复操作，直至完全有序

?3. 案例：

对数组? [9,1,2,5,7,4,8,6,3,5]? 进行排序

3.1 流程图?

?

3.2 实现代码

        function shellSort(arr) {
            let len = arr.length
            let count = 0
            for (let gap = parseInt(len / 2); gap > 0; gap = parseInt(gap / 2)) {
                // 外层循环将数组分成若干组
                for (let i=gap; i<len; i++) {  
                    // 内层遍历每组中所有的元素，对每一组进行插入排序
                    for (let j=i-gap; j>=0; j-=gap) {
                        if (arr[j] > arr[j+gap]){
                            let temp = arr[j]
                            arr[j] = arr[j+gap]
                            arr[j+gap] = temp
                        }
                    }
                }

                console.log(`希尔排序第${++count}轮结束后，数组变为：${arr}`)
            }
         }
         let arr = [9,1,2,5,7,4,8,6,3,5]
         shellSort(arr)

?3.3 结果

?

4. 复杂度分析

4.1 时间复杂度

?

?4.2 空间复杂度

?

4.3 稳定性

我们在分布对数组进行排序的时候，很有可能将两个相同值的元素的相对位置进行改变，所以希尔排序是不稳定的排序算法

?