黑马程序员技术交流社区

标题: 谁了解希尔排序，给介绍下呗 [打印本页]
作者: 风雪再现    时间: 2013-7-7 21:19
标题: 谁了解希尔排序，给介绍下呗
谁能给介绍一下希尔排序算法，并给个例子，要代码哦，尽量简单点
作者: 月儿圆    时间: 2013-7-7 21:29
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。[1]
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比[1]较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
给定实例的shell排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，2，1

  1. using System;
  2. public class ShellSorter
  3. {
  4. public void Sort(int[] list)
  5. {
  6. int inc;
  7. for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
  8. for (; inc > 0; inc /= 3)
  9. {
  10. for (int i = inc + 1; i <= list.Length; i += inc)
  11. {
  12. int t = list[i - 1];
  13. int j = i;
  14. while ((j > inc) && (list[j - inc - 1] > t))
  15. {
  16. list[j - 1] = list[j - inc - 1];
  17. j -= inc;
  18. }
  19. list[j - 1] = t;
  20. }
  21. }
  22. }
  23. }
  24. public class MainClass
  25. {
  26. public static void Main()
  27. {
  28. int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
  29. ShellSorter sh = new ShellSorter();
  30. sh.Sort(iArrary);
  31. for (int m = 0; m <= 13; m++)
  32. Console.WriteLine("{0}", iArrary[m]);
  33. Console.ReadKey();
  34. }
  35. }
  36. for (int i = k; i < len; i++)
  37. {
  38. if (arry[i - k] > arry[i])
  39. {
  40. int temp;
  41. temp = arry[i - k];
  42. arry[i - k] = arry[i];
  43. arry[i] = temp;
  44. }
  45. }
  46. }
  47. foreach (int i in arry)
  48. {
  49. Console.WriteLine(i);
  50. }
  51. Console.ReadLine();
  52. program ShellSorter;
  53. type arr=array[1..n] of integer;
  54. var a:arr;
  55. i,n,j,t,d:integer;
  56. bool:boolean;
  57. begin
  58. readln(n);
  59. for i:=1 to n do read(a[i]);writeln;
  60. d:=n;
  61. while d>1 do begin d:=d div 2;
  62. for j:=d+1 to n do begin t:=a[j];
  63. i:=j-d;
  64. while (i>0) and (a[i]>t) do
  65. begin
  66. a[i+d]:=a[i];
  67. i:=i-d;
  68. end;
  69. a[i+d]:=t;
  70. end;
  71. end;
  72. for i:=1 to n do write(a[i]:6);
  73. writeln;
  74. end.
复制代码
[摘自百度百科]





欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2