LeetCode 希尔排序 题解题目描述实现希尔排序算法对一个整数数组进行排序。示例 1输入nums [5,2,3,1] 输出[1,2,3,5]示例 2输入nums [5,1,1,2,0,0] 输出[0,0,1,1,2,5]解题思路方法希尔排序思路希尔排序是插入排序的改进版本它的工作原理是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行依次直接插入排序。希尔排序的关键在于选择合适的增量序列常用的增量序列有希尔增量n/2, n/4, ..., 1、Hibbard 增量2^k - 1、Sedgewick 增量等。复杂度分析时间复杂度O(n log n) 到 O(n²) 之间具体取决于增量序列的选择。空间复杂度O(1)只需要常数级的额外空间。代码实现方法希尔排序def shell_sort(nums): n len(nums) # 初始化增量为 n//2 gap n // 2 # 当增量大于 0 时继续排序 while gap 0: # 对每个子序列进行插入排序 for i in range(gap, n): # 保存当前要插入的元素 key nums[i] # 从当前元素的前一个增量位置开始向前比较 j i - gap while j 0 and nums[j] key: # 将大于key的元素向后移动gap个位置 nums[j gap] nums[j] j - gap # 将key插入到适当的位置 nums[j gap] key # 缩小增量 gap // 2 return nums # 测试 nums1 [5,2,3,1] print(shell_sort(nums1)) # 输出[1,2,3,5] nums2 [5,1,1,2,0,0] print(shell_sort(nums2)) # 输出[0,0,1,1,2,5]测试用例测试用例 1输入nums [5,2,3,1]输出[1,2,3,5]测试用例 2输入nums [5,1,1,2,0,0]输出[0,0,1,1,2,5]总结本题是排序算法的经典问题主要考察对希尔排序算法的理解和实现。希尔排序是插入排序的改进版本它通过将数组分成若干子序列进行排序然后逐步缩小增量最终完成排序。希尔排序的核心思想是使用一个增量序列将数组分成若干子序列对每个子序列进行插入排序然后缩小增量重复这个过程直到增量为 1最后进行一次插入排序。这种方法的时间复杂度取决于增量序列的选择通常在 O(n log n) 到 O(n²) 之间是一种不稳定的排序算法。掌握希尔排序的原理对于理解排序算法的改进思想非常重要。