希尔排序,又称为缩小增量排序,其基本思想为:先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-1<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
核心代码:
public static void shellInsertSort(int[] data, int dk){ for(int i=dk; i<data.length; i++){ // 是直接插入排序的一个变种 if(data[i] < data[i-dk]){ int cur = data[i]; int j = i - dk; for(; j>=0&&cur<data[j]; j-=dk){ data[j+dk] = data[j]; } data[j+dk] = cur; } } } 完整代码:
package cn.ccnu.sort; public class Shell { public static void shellInsertSort(int[] data, int dk){ for(int i=dk; i<data.length; i++){ // 是直接插入排序的一个变种 if(data[i] < data[i-dk]){ int cur = data[i]; int j = i - dk; for(; j>=0&&cur<data[j]; j-=dk){ data[j+dk] = data[j]; } data[j+dk] = cur; } } } public static void shellSort(int[] data){ int dk = data.length/2; while(dk>=1){ shellInsertSort(data, dk); dk = dk/2; } } public static void main(String[] args) { int[] data = {10, 3, 12, 5, 4, 9, 4, 7, 6}; shellSort(data); for (int i : data) { System.out.print(i + " "); } } }
