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

希尔排序基本思想： 
 
 
　　先取一个小于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 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; // 计算下次分割的间隔长度 
 
 
　　} 
 
 
　　} 
 
 
　　}