580-希尔排序算法的思想和性能分析-蒲公英云

580-希尔排序算法的思想和性能分析

希尔排序算法的思想

希尔排序可以认为是插入排序的一个优化，升级。
如果数据序列从大的方向，从全局看，已经是趋于有序的，那么插入排序是所有排序算法中效率最高的。
希尔排序就是从插入排序的这句中总结优化的，它以自己最大的能力在全局中不断地把数据调整成趋于有序的，这样使得插入排序效率就越来越高。

插入排序是按顺序从左到右，依次定位到元素，然后在前面已排序的序列中找到合适的位置插入。也就是说，随着插入排序的进行，只是前面那部分是有序的，从整体上表现出来，并不是越排越有序。
而希尔排序对插入排序的优化是，让全局数据序列越来越有序，尽最快的速度先变成趋于有序的序列，然后统一用插入排序进行处理。

希尔排序：对数据进行分组插入排序。
在这里插入图片描述
我们进行第一次分组处理

每隔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;
        }
    }
}