希尔排序的算法思想与实现

时间:2021-09-09 22:10:08

希尔排序基本思想:

  先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

  该方法实质上是一种分组插入方法。

  给定实例的shell排序的排序过程

  假设待排序文件有10个记录,其关键字分别是:

  49,38,65,97,76,13,27,49,55,04。

  增量序列的取值依次为:

  5,3,1

缩小增量法

  属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序

  排序过程:先取一个正整数d1<n,把所有序号相隔d1的数组元素放一组,组内进行直接插入排序;然后取d2<d1,重复上述分组和排序操作;直至di=1,即所有记录放进一个组中排序为止

  初始:d=5

  49 38 65 97 76 13 27 49* 55 04

  49 13

  |-------------------|

  38 27

  |-------------------|

  65 49*

  |-------------------|

  97 55

  |-------------------|

  76 04

  |-------------------|

  一趟结果

  13 27 49* 55 04 49 38 65 97 76

  d=3

  13 27 49* 55 04 49 38 65 97 76

  13 55 38 76

  |------------|------------|------------|

  27 04 65

  |------------|------------|

  49* 49 97

  |------------|------------|

  二趟结果

  13 04 49* 38 27 49 55 65 97 76

  d=1

  13 04 49* 38 27 49 55 65 97 76

  |----|----|----|----|----|----|----|----|----|

  三趟结果

  04 13 27 38 49* 49 55 65 76 97

希尔排序的JAVA实现  public class Test {

  public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };

  public static void main(String args[]) {

  int i; // 循环计数变量

  int Index = a.length;// 数据索引变量

  System.out.print("排序前: ");

  for (i = 0; i < Index - 1; i++)

  System.out.printf("%3s ", a[i]);

  System.out.println("");

  ShellSort(Index - 1); // 选择排序

  // 排序后结果

  System.out.print("排序后: ");

  for (i = 0; i < Index - 1; i++)

  System.out.printf("%3s ", a[i]);

  System.out.println("");

  }

  public static void ShellSort(int Index) {

  int i, j, k; // 循环计数变量

  int Temp; // 暂存变量

  boolean Change; // 数据是否改变

  int DataLength; // 分割集合的间隔长度

  int Pointer; // 进行处理的位置

  DataLength = (int) Index / 2; // 初始集合间隔长度

  while (DataLength != 0) // 数列仍可进行分割

  {

  // 对各个集合进行处理

  for (j = DataLength; j < Index; j++) {

  Change = false;

  Temp = a[j]; // 暂存Data[j]的值,待交换值时用

  Pointer = j - DataLength; // 计算进行处理的位置

  // 进行集合内数值的比较与交换值

  while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {

  a[Pointer + DataLength] = a[Pointer];

  // 计算下一个欲进行处理的位置

  Pointer = Pointer - DataLength;

  Change = true;

  if (Pointer < 0 || Pointer > Index)

  break;

  }

  // 与最后的数值交换

  a[Pointer + DataLength] = Temp;

  if (Change) {

  // 打印目前排序结果

  System.out.print("排序中: ");

  for (k = 0; k < Index; k++)

  System.out.printf("%3s ", a[k]);

  System.out.println("");

  }

  }

  DataLength = DataLength / 2; // 计算下次分割的间隔长度

  }

  }

  }