/**
* 希尔排序,也称缩小增量排序
* 交换法
* @param arr 要排序的数组
*/
public static void shellSort(int[] arr) {
//定义增量step
int step = arr.length;
//定义临时变量用于辅助交换
int tmp = 0;
//增量每次都变为原来的一半,直到增量为1为止
while ((step = step / 2) >= 1) {
//以增量大小为一组将数组元素分组,依次按对应顺序比较对应位置的元素大小
for (int i = step; i < arr.length; i++) {
for (int j = i - step; j >=0; j -= step) {
//如果后边一组的元素大于前边一组的元素,则交换位置
if (arr[j] > arr[j + step]) {
tmp = arr[j];
arr[j] = arr[j + step];
arr[j + step] = tmp;
}
}
}
}
}
/**
* 希尔排序之 移位法
* @param arr 要排序的数组
*/
public static void shellSort2(int[] arr){
//变量step为增量,并不断的缩小增量,直到缩小到1为止
for (int step = arr.length / 2; step > 0; step /= 2) {
//对每次缩小的增量按照大小进行移位
for (int i = step; i < arr.length ; i++) {
//定义变量保存当前要比较的数值及其对应的索引
int j = i;
int tmp = arr[j];
//如果当前数字小于前边一组对应的数字,则移位
if (arr[j - step] > arr[j]) {
//循环寻找当前元素要插入的位置
while ((j - step) >= 0 && arr[j - step] > tmp) {
arr[j] = arr[j - step];
j -= step;
}
//则循环结束后找到要插入的位置
arr[j] = tmp;
}
}
}
}
原文:https://www.cnblogs.com/mx-info/p/14838791.html