当前位置:   article > 正文

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

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

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

文章规划:

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

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

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

ps:一个较为详细的学习链接   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>
  2. // 打印结果
  3. void Show(int arr[], int n)
  4. {
  5. int i;
  6. for ( i=0; i<n; i++ )
  7. printf("%d ", arr[i]);
  8. printf("\n");
  9. }
  10. //希尔排序 按从小到大排序
  11. void ShellSort(int arr[], int n)
  12. {
  13. int i, j, k;
  14. int temp, gap;
  15. for (gap = n / 2; gap > 0; gap /= 2) //步长的选取
  16. {
  17. for (i = 0; i < gap; i++) //直接插入排序原理
  18. {
  19. for (j = i + gap; j < n; j += gap) //每次加上步长,即按列排序。
  20. if (arr[j] < arr[j - gap])
  21. {
  22. temp = arr[j];
  23. k = j - gap;
  24. while (k >= 0 && arr[k] > temp) //记录后移,查找插入位置
  25. {
  26. arr[k + gap] = arr[k];
  27. k -= gap;
  28. }
  29. arr[k + gap] = temp; //找到位置插入
  30. }
  31. }
  32. }
  33. }
  34. int main()
  35. { //测试数据
  36. int arr_test[10] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
  37. //排序前数组序列
  38. Show( arr_test, 10 );
  39. ShellSort( arr_test, 10 );
  40. //排序后数组序列
  41. Show( arr_test, 10 );
  42. return 0;
  43. }

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

  1. void shellsort2(int a[], int n)
  2. {
  3. int j, gap;
  4. for (gap = n / 2; gap > 0; gap /= 2)
  5. for (j = gap; j < n; j++)//从数组第gap个元素开始
  6. if (a[j] < a[j - gap])//每个元素与自己组内的数据进行直接插入排序
  7. {
  8. int temp = a[j];
  9. int k = j - gap;
  10. while (k >= 0 && a[k] > temp)
  11. {
  12. a[k + gap] = a[k];
  13. k -= gap;
  14. }
  15. a[k + gap] = temp;
  16. }
  17. }

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

注:本文仅为分享知识,绝无商业用途。

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



声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/658206
推荐阅读
相关标签
  

闽ICP备14008679号