vlambda博客
学习文章列表

基本思想：

希尔排序是一种高效的插入排序，插入排序是一点一点的移动元素，在数据量规模比较小和基本有序比较高效，希尔排序为了加快速度改进了插入排序，交换不相邻的元素对数组进行局部排序，并最终用插入排序将局部有序的元素排序。

其思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序的数组就是h个互相独立的有序数组编织在一起组成的一个数组。在进行排序的时候，如果h很大，我们就能将元素移动到很远的地方，为实现很小的h有序创造方便。

具体步骤：

1. 对较大数据集合分成若干个小组；

2. 然后对每个小组进行插入排序；

3. 缩小增量为上个增量的一半，继续划分分组；

4. 对划分的小组进行插入排序；

5. 循环步骤3,4直到增量为1，整个数组被划分为一组；

代码实现：

“3 个循环一个条件”

Python:

Def shellSort(nums):
 size = len(nums)
 step = size // 2
 while step > 0:
 for i in range(step, size):
 j = i
 while j >= step and nums[j] < nums[j - step]:
 nums[j], nums[j - step] = nums[j - step], nums[j]
 j -= step
 step = step // 2
 return nums

C++:

std::vector<int> shell_sort(std::vector<int> nums) {
 int lens = nums.size();
 int step = lens / 2;
 while (step > 0) {
 for (int i = step; i < lens; ++i) {
 int j = i;
 while (j >= step) {
 if (nums[j] < nums[j - step]) {
 int temp = nums[j - step];
 nums[j - step] = nums[j];
 nums[j] = temp;
 }
 j -= step;
 }
 }
 step = step / 2;
 }
 return nums;
}

复杂度分析：

时间复杂度分析：

希尔排序优于直接插入排序,原因是在元素列不断变的有序的情况下,元素比较以及交换的次数也在减少,希尔排序的时间复杂度为O(n^(3/2)),最好的时间复杂度为(NlogN)，最坏的情况是O(n^2)；

空间复杂度分析：

没有开辟额外的存储空间，如果说开辟了也是在交换的时候开辟了一个temp，所以为O(1);

稳定性：

直接插入排序是稳定的,虽然希尔排序作为插入排序的一种,但是分组排序的时候,原本的顺序可能被破坏,因此希尔排序是一种不稳定的排序；