前面一口气写了冒泡、选择、插入三个排序算法,感觉今天和他们死磕上了。。。
就不该十一点多还看了几眼。。。然后又掉坑里了,大半夜果然的效率低,看个希尔排序然后居然写了1个小时。。。哇,难受
抄起键盘一顿梭,就是干
严格来说,希尔排序是基于插入排序的思想的,稍后在代码里可以看出,希尔排序又称缩小增量排序,是简单插入排序的增强版本,于1959年由Donald Shell提出。
算法基本思想:
- 将有n个元素的数组分成n/2份,第1个数据与第n/2+1个数据属于同一份。。。
- 使用类似插入排序的方法,将同一份的数据排序
- 然后,再变为n/4份,同样的操作再次排序
- 不断重复上述3个步骤之后,最后分成n份数据,再通过一次插入排序就完成了全部的排序。
(网上搜的图,自己不想画了,大半夜要睡觉去了,偷个懒)
代码实现:
import java.util.Arrays;
public class ShellSort {
public static void sort(int[] arr) {
int len = arr.length;
int gap;//步长
int istIndex;//插入位置索引
int tmp;
System.out.println("原始顺序: "+ Arrays.toString(arr));
//按照步长来分组
for(gap = len / 2; gap >= 1; gap /= 2) {
//类似插入排序的方法
for (int i = gap; i < len; i++) {
tmp = arr[i];//取出暂存
istIndex = i;//插入的位置
while ((istIndex > (gap-1) && tmp < arr[istIndex - gap])) {
//插入位置往前移,寻找合适位置
arr[istIndex] = arr[istIndex - gap];
istIndex -= gap;
}
arr[istIndex] = tmp;
}
System.out.println("步长为"+gap+"的排序: "+ Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr = new int[10];
//初始化数组
for (int i = 0; i < 10; i++) {
arr[i] = (int) (Math.random() * (100 + 1));
}
ShellSort.sort(arr);
}
}
分析小结:
其实希尔排序就是分了组的插入排序,通过这样做可以减少大部分的情况下,数据的移动次数,从而减小时间复杂度,同时希尔排序也是当时冲破O(n^2)的第一批算法之一。
在代码中可以看到,当我们将第二层for循环里的gap视为1的时候,其实接下来的代码就和之前的插入排序一模一样了!!!
其实对于该算法,还可以继续优化,就是改善步长的计算部分,现在是每次变为原来的1/2,其实有个公式h=3*h+1来计算步长,有兴趣的话可以自己研究一下,对于步长的选择是一种魔力,我就不多说了。。。睡觉睡觉了,不能在修仙了zzz