排序算法之希尔排序

怼烎@ 2022-06-16 08:40 258阅读 0赞

问题描述：

输入一个原始数列，把它进行升序排序，从小到大输出。

例如：给定数列如下：  
5 15 99 45 12 1 90 19 33 41

排序后的结果为：  
1 5 12 15 19 33 41 45 90 99

希尔排序，首先选定步长值，选定的方法一般是从数组个数n/2开始，依次往下除以2，直到步长减少到1为止，选好步长之后，我们在每个步长值上，进行插入排序，使得该步长范围的数列都是有序的，随着步长逐步变小，整个数列慢慢变得有序了，等到步长为1的时候，数列已经基本有序了，我们知道在越有序的数列中，采用插入排序的效率越高，因为已经有序的那段数列是不需要动的，下面我们来看一下具体的过程：

下标值序号： 0 1 2 3 4 5 6 7 8 9  
原始状态为： 5 15 99 45 12 1 90 19 33 41  
第一次：step=10/2=5  
排序后结果： 1 15 19 33 12 5 90 99 45 41 （依次对a\[i\],a\[i+5\]进行插入排序）

第二次：step=5/2=2  
排序后结果： 5 1 12 15 33 19 90 41 99 45（依次对a\[i\], a\[i+2\]进行插入排序）

第三次：step=2/2=1  
排序后结果：1 5 12 15 19 33 41 45 90 99（依次对a\[i\], a\[i+1\]进行插入排序，这个就相当于插入排序了，只是此时整个序列已经基本有序了）

从上面我们可以发现：  
1. 对于N个数的数列来说，希尔排序的步长是不断除以2来递减的，所以步长下降的非常快  
2. 希尔排序开始的时候移动的次数多，随着步长减少，序列慢慢变得有序之后，移动次数就变少了  
3. 也就是说，随着步长不断变小，执行的就越快，所以当步长缩小为1的时候，在进行插入排序就非常快了  
4. 其实排序的过程也就是不断消除逆序的过程（逆序就是排在前面的数比排在后面的数大，则称为一个逆序），对于一个随机的产生的数列，逆序总数是O(n^2)的，而采取交换相邻元素的方法来消除逆序，每次只能删除一个，因此必须执行O(n^2)的交换次数，这就是为什么冒泡，插入，选择都是O(n^2)的时间复杂度，而如果我们想突破这个下界，就必须进行一些比较，来交换比较远的两个元素，使得一次交换能够减少超过一个的逆序，希尔、快速排序，堆排序都是如此，只是规则各有不同。  
5. 算法的平均时间复杂度是O（nlogn），最差时间复杂度O(n^s)(1

#include<stdio.h>
    
    int main()
    {
        int arr[] = { 5, 15, 99, 45, 12, 1, 90, 19, 33, 41 };
        int i, j, k, nTemp, nCount = sizeof(arr) / sizeof(arr[0]);
        printf("排序前\n");
        for (i = 0; i < nCount; i++)
            printf("%d ", arr[i]);
        printf("\n");
    
        for (i = nCount / 2; i > 0; i /= 2)//设置希尔排序的步长
        {
            for (j = i; j < nCount; j++)
            {
       //遍历数组中个值进行排序，希尔排序相对于插入排序的优化就在于，在不断减少步长的过程中，变得越来越有序，在越有序的情况下，插入排序越快
                if (arr[j] < arr[j - i])
                {
                    nTemp = arr[j];
                    for (k = j - i; k >= 0 && nTemp < arr[k]; k -= i)
                        arr[k + i] = arr[k];
                    arr[k + i] = nTemp;
                }
            }
        }
    
        printf("\n排序后\n");
        for (i = 0; i < nCount; i++)
            printf("%d ", arr[i]);
        printf("\n");
        return 0;
    }

运行结果：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220616/fe9c0919a5fa4059aac398c29e2ea825.png