网站seo 优帮云参考消息网国内新闻
希尔排序算法的思想
希尔排序可以认为是插入排序的一个优化，升级。
如果数据序列从大的方向，从全局看，已经是趋于有序的，那么插入排序是所有排序算法中效率最高的。
希尔排序就是从插入排序的这句中总结优化的，它以自己最大的能力在全局中不断地把数据调整成趋于有序的，这样使得插入排序效率就越来越高。
插入排序是按顺序从左到右，依次定位到元素，然后在前面已排序的序列中找到合适的位置插入。也就是说，随着插入排序的进行，只是前面那部分是有序的，从整体上表现出来，并不是越排越有序。
而希尔排序对插入排序的优化是，让全局数据序列越来越有序，尽最快的速度先变成趋于有序的序列，然后统一用插入排序进行处理。
希尔排序：对数据进行分组插入排序。
我们进行第一次分组处理
每隔5个元素，把它们分到1个组里面。
25-87为一组， 进行插入排序。
40-41为一组，进行插入排序。
25-3为一组，进行插入排序。
9-40为一组，进行插入排序。
32-31为一组，进行插入排序。
总共10个元素，每间隔5个位置的元素是一个组的，所以一组有2个元素，总共分为5组。
这5组遍布了整个序列的前前后后。每一个组内进行插入排序。就是从全局尽快的把元素调整成趋于有序的。
25和87是一组的，已经是有序的，40和41是一组的，已经是有序的。
25和3是一组的，但是不是有序的，3和25进行交换，
9和40是一组的，已经是有序的，不用进行交换
32和31是一组的，但是不是有序的，我们把32和31交换
从全局来看，数据已经趋于有序的了
然后进行第二次分组，gap继续缩小
每间隔2个位置的元素算是一个组 ，所以总共有2个组，1个组有5个元素，在同一组内进行插入排序
25，3,31,41,40是一组的，但是不是有序的，进行插入排序。
40,9，87,25,32是一组的，进行插入排序
第二次分组，进行插入排序，已完成，整体更加趋于有序了。
我们进行第三次分组处理
这次就是每间隔1个位置的元素是一组，相当于是整个序列是一组的，进行插入排序。
处理完毕
这一次处理完之后
gap=gap/2=1/2=0
希尔排序结束！
注意：对半分组不是一定要除以2的，除以3也可以，除以4也可以，我们要在实际情况中，根据实际的数据量进行分组的调整，测试一下性能是否达到最好的。
希尔排序算法的代码实现
//希尔排序
void ShellSort(int arr[], int size)
{for (int gap = size / 2; gap > 0; gap /= 2)//100W 19 1000W 24{for (int i = gap; i < size; i++)//O(n)i++:所有组都是要处理的 {int val = arr[i]; int j = i - gap;for (; j >= 0; j-=gap)//O(n) {if (arr[j] <= val){break;}arr[j + gap] = arr[j];}arr[j + gap] = val;}}
}
希尔排序算法的性能分析
最坏的时间复杂度：
O(n^2)
最外层的for循环相当于是二分搜索的概念，对于数据量的增长，这个for循环不用关注其性能的损耗了
最好的时间复杂度：O(n)
相当于数据序列本身就是有序的，遍历了1遍而已
空间复杂度:O(1)
没有占用额外的空间，随着数据量的增长，我们在栈上申请的变量不会增多，空间的占用就是这两个变量
不稳定：
因为它可能会把值相同的元素放在不同的组里面，然后就有可能发生相同元素的相对位置的变化。
有时候我们要把快速排序和插入排序结合起来