一、希尔排序法介绍
希尔排序实际上也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。
二、希尔排序法基本思想
希尔排序是把一组数据按下表的一定增量分组,对每组使用直接插入排序算法进行排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便种植
三、希尔排序法的示意图
四、希尔排序法应用实例
有一组数据{8,9,1,7,2,3,5,4,6,0},从小到大进行排序
代码实现
public class ShellSort {
public static void main(String[] args) {
// int[] arr = {3, 5, 1, 6, 0, 8, 9, 4, 7, 2};
int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
sort2(arr);
// int[] arr = new int[8000000];
// for (int i = 0; i < 8000000; i++) {
// arr[i] = (int) (Math.random() * 100000);
// }
//
// long start = System.currentTimeMillis();
// sort(arr);
// long end = System.currentTimeMillis();
// System.out.println(end - start);
System.out.println(Arrays.toString(arr));
}
private static void sort2(int[] arr){
int step = arr.length;
while ((step /= 2) >= 1){
//该循环控制共分了多少组
for (int i = 0; i < step ; i++){
//该循环控制每组有多少个数需要比较
//arr.length / step 为每组的元素个数 -1后则为需要参与比较的数
for (int j = 0; j < (arr.length / step) -1; j++) {
int insertValue = arr[i+step*(j+1)];
int tempIndex = i+step*(j+1);
while (tempIndex > i && insertValue < arr[tempIndex -step]){
arr[tempIndex] = arr[tempIndex -step];
tempIndex -= step;
}
arr[tempIndex] = insertValue;
}
}
}
}
}