希尔排序: 在简单插入排序经过改进的更高效版本,也称缩小增量排序。 算法基本思想: 把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减小,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法终止。 希尔排序有两种方法:交换法(效率不高) 和 移位法。 算法图解:
算法实现: 交换法:
//该算法是希尔排序中的交换法(效率不高)
public static void shellSort(int[] arr) {
int temp = 0;
int count = 0;
for (int stepSize = arr.length / 2; stepSize > 0; stepSize /= 2) {
for (int i = stepSize; i < arr.length; i++) {
//遍历各组中所有的元素(共stepSize组),步长为stepSize
for (int j = i - stepSize; j >= 0; j -= stepSize) {
//如果当前元素大于加上步长后的那个元素,说明交换
if (arr[j] > arr[j + stepSize]) {
temp = arr[j];
arr[j] = arr[j + stepSize];
arr[j + stepSize] = temp;
}
}
}
System.out.println("希尔排序第" + (++count) + "轮" + Arrays.toString(arr));
}
System.out.println("排序的结果为:" + Arrays.toString(arr));
}
这里的第三层循环 j -= stepSize,到第二轮stepSize = 2时,当时有点不理解,自己在纸上写了排序全过程:
它可以两组进行交叉排序,且保证有序性。
移位法:
//对交换式的希尔排序进行优化--->移位法
public static void shellSortPlus(int[] arr) {
//增量stepSize,并逐步缩小增量
for (int stepSize = arr.length / 2; stepSize > 0; stepSize /= 2) {
//从第stepSize个元素,逐个对其所在组进行直接插入排序
for (int i = stepSize; i < arr.length; i++) {
int j = i;
int temp = arr[j];
if(arr[j] < arr[j-stepSize]) {
while(j - stepSize >= 0 && temp < arr[j-stepSize]) {
//移动
arr[j] = arr[j-stepSize];
j -= stepSize;
}
//当退出while循环时就给temp找到插入的位置
arr[j] = temp;
}
}
System.out.println(Arrays.toString(arr));
}
System.out.println("希尔排序的结果为: "+Arrays.toString(arr));
}
这个移位法算法的时间效率比交换法算法的时间效率高好多。