排序算法c语言描述---希尔排序

落日映苍穹つ 2021-11-05 01:56 252阅读 0赞

**排序算法系列学习，主要描述冒泡排序，选择排序，直接插入排序，希尔排序，堆排序，归并排序，快速排序等排序进行分析。**

**文章规划：**

**一。通过自己对排序算法本身的理解，对每个方法写个小测试程序。 具体思路分析不展开描述。**

**二。通过《大话数据结构》一书的截图，详细分析该算法 。**

**在此，推荐下程杰老师的《大话数据结构》一书，当然不是打广告，只是以一名读者的身份来客观的看待这本书，确实是通俗易懂，值得一看。**

**ps：一个较为详细的学习链接 [http://blog.csdn.net/MoreWindows/article/category/859207][http_blog.csdn.net_MoreWindows_article_category_859207]**

# 五。希尔排序 #

## 一。个人理解 ##

希尔排序(Shell Sort)是插入排序 的一种。是针对直接插入排序 算法的改进。该方法又称缩小增量 排序，因DL．Shell于1959年提出而得名。

**其实，希尔排序本质也就是直接插入算法的升级，希尔的基本思想，就是先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量大小再进行排序，待整个序列中的元素基本有序（增量足够小，通常为1）时，再对全体元素进行一次直接插入排序。**

**（直接插入的原理：把一个标记插入到已经排好序的有序表中。如： 把arr\[i\]插入arr\[0\]---arr\[i-1\]中的某个位置，其中，arr\[0\]---arr\[i-1\]是排好序的。这时候从后往前，在arr\[i-1\]到arr\[0\]中找到第一次满足比arr\[i\]小的那个数，则把arr\[i\]插入这数字后面，相应的把后面的大于arr\[i\]的元素都往后移，则此时arr\[0\]----arr\[i\]就是有序的，如此反复，直到全部元素都找好自己的位置）**

所以，对于希尔排序的介绍，通过以下两部分完成：

1.简单排序例子

2.如何选择增量（步长）

## 1.简单排序例子 ##

1.1例如，假设有这样一组数\[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 \]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
    25 59 94 65 23
    45 27 73 25 39
    10

然后我们对每列进行排序：

10 14 73 25 23
    13 27 94 33 39
    25 59 94 65 82
    45

将上述四行数字，依序接在一起时我们得到：\[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 \].这时10已经移至正确位置了，然后再以3为步长进行排序：

10 14 73
    25 23 13
    27 94 33
    39 25 59
    94 65 82
    45

对每列排序之后变为：

10 14 13
    25 23 33
    27 25 59
    39 65 73
    45 94 82
    94

最后的数组为［ 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94］，最后以1步长进行排序（此时就是简单的插入排序了）。

1.2又如，准备待排数组\[6 2 4 1 5 9\]，选择步长（增量）3，得

6 2 4
    1 5 9

对每列进行排序，得

1 2 4
    6 5 9

这时候得到的数组为\[ 1 2 4 6 5 9 \]，然后选择步长（增量为1）直接用插入排序。

**以上就是希尔排序的思路了，总的来说，就是每次选定一个步长，将数组进行划分，然后对每列小划分利用直接插入排序方法排序，得到新数组，再选择步长分组，利用直接插入排序。直到步长为1，最后利用一次直接插入排序。**

**说白了，希尔排序就是选择合适步长＋直接插入排序。**

下面谈谈如何选择步长。

## 2.希尔排序步长（增量）选择。 ##

其实步长（增量）的选择没有统一规定，也没绝对的规律。只要满足最后一个步长（增量）为1即可。

已知的最好步长串行是由Sedgewick提出的 (1, 5, 19, 41, 109,...)，该串行的项来自 9 \* 4^i - 9 \* 2^i + 1 和 4^i - 3 \* 2^i + 1 这两个算式 [\[1\]][1] .这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”

而我们在实践中，如果没特殊需要，一般增量的选取规则为：

第一次取总长度的一半，第二次取一半的一半，依次累推直到步长为1为止。

这样不仅简单，也能利用希尔算法进行排序。

好了，说了这么多，希尔排序的思路就是这样，下面上代码。

这个小测试也只是把步长对半选择，如果有其他需求，可以对步长的选择进行分析。

#include<stdio.h>
    // 打印结果
    void Show(int  arr[], int n)
    {
        int i;
        for ( i=0; i<n; i++ )
            printf("%d  ", arr[i]);
        printf("\n");
    }
    
    //希尔排序  按从小到大排序
    void ShellSort(int arr[], int n)
    {
        int i, j, k;
        int temp, gap;
        
        for (gap = n / 2; gap > 0; gap /= 2) //步长的选取
        {
            for (i = 0; i < gap; i++)        //直接插入排序原理
            {
                for (j = i + gap; j < n; j += gap)    //每次加上步长，即按列排序。
                    if (arr[j] < arr[j - gap])
                    {
                        temp = arr[j];
                        k = j - gap;
                        while (k >= 0 && arr[k] > temp) //记录后移，查找插入位置
                        {
                            arr[k + gap] = arr[k];
                            k -= gap;
                        }
                        arr[k + gap] = temp;  //找到位置插入
                    }
            }
        }
    }
    
    int main()
    {   //测试数据
        int arr_test[10] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
        //排序前数组序列
        Show( arr_test, 10 );
        ShellSort( arr_test, 10 );
        //排序后数组序列
        Show( arr_test, 10 );
        return 0;
    }

上述写法是对希尔算法的完整描述，其实，也可以在写法上进行一些简化。

void shellsort2(int a[], int n)  
    {  
        int j, gap;  
          
        for (gap = n / 2; gap > 0; gap /= 2)  
            for (j = gap; j < n; j++)//从数组第gap个元素开始  
                if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序  
                {  
                    int temp = a[j];  
                    int k = j - gap;  
                    while (k >= 0 && a[k] > temp)  
                    {  
                        a[k + gap] = a[k];  
                        k -= gap;  
                    }  
                    a[k + gap] = temp;  
                }  
    }

## 二。 《大话数据结构》一书截图分析 ##

**注：本文仅为分享知识，绝无商业用途。**

**如果以该种形式分享知识造成不必要的纠纷，还请第一时间告知。**

![Center][] ![Center 1][] ![Center 2][] ![Center 3][] ![Center 4][] ![Center 5][] ![Center 6][] ![Center 7][] ![Center 8][] ![Center 9][]

[http_blog.csdn.net_MoreWindows_article_category_859207]: http://blog.csdn.net/MoreWindows/article/category/859207
[1]: http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L12-ShellSort.htm#increments
[Center]: https://img-blog.csdn.net/20130810202851750?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20130810202905640?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20130810202914125?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 3]: https://img-blog.csdn.net/20130810202922484?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: https://img-blog.csdn.net/20130810202924812?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: https://img-blog.csdn.net/20130810202934562?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 6]: https://img-blog.csdn.net/20130810202946812?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 7]: https://img-blog.csdn.net/20130810203012140?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 8]: https://img-blog.csdn.net/20130810203036046?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaGl0d2h5bHo=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 9]: /images/20211104/bd828ea7158a4160bd863e94f33a7108.png