希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本
插入排序存在的效率问题
如果已经排序的分组元素为{2,5，7,9，10}未排序的分组元素为{1,8}那么下一个待插入元素为1，我们需要拿着1从后往前，一次和10,9，7,5，2进行位置交换，才能真正完成插入。如果我们要提高效率，就是把1放到更前面的位置，例如直接将1放到2前面，这样可减少交换次数。下面我们来看看希尔排序
将数组{9,1,2,57,4,8,6,3,5}正序
希尔排序原理
1、选定一个增长量，按照增长量h作为数组分组的依据，对数据进行分组
2、对分好组的每一组数据完成插入排序
3、减小增长量，最小减为1，重复第二部操作
第一次h应该为7，这里为了方便的分析排序过程，暂时写作5
增长量h的确定：增长量h的值固定规则如下
int h=1;
while(h<数组长度/2){
h=2h+1
}
增长量减少规则
h=h/2 如果除不开按照java的除法规则，例如7/2=3
代码
public static void main(String[] args) {
Integer arr[] = {9,1,2,57,4,8,6,3,5};
sort(arr);
System.out.println(Arrays.toString(arr));
sort(arr, Comparator.reverseOrder());
System.out.println(Arrays.toString(arr));
}
/**
* 自定义排序
*
* @param arr
* @param comparator
* @param <T>
*/
public static <T> void sort(T[] arr, Comparator<T> comparator) {
int h=1;
while (h<arr.length/2) {
h = 2 * h + 1;
}
while (h>=1){
for (int i = h; i <= arr.length-1; i+=h) {
for (int j = i; j >=h; j-=h) {
if(greater(comparator,arr[j],arr[j-h])){
exch(arr,j-h,j);
}else {
break;
}
}
}
h=h/2;
}
}
/**
* 正序
*
* @param arr
* @param <T>
*/
public static <T> void sort(Comparable<T>[] arr) {
//找到最大增量
int h=1;
while (h<arr.length/2) {
h = 2 * h + 1;
}
//当增量为1的时候所有数据都在一组
while (h>=1){
//找到待排序元素，通过观察发现待排序元素的索引=增长量 所以i=h
//arr.length-1 参与排序的最大索引 i+=h 因为待排序索引的开始值
for (int i= h; i <= arr.length-1; i+=h) {
//假如h=2 待排序索引为8，通过已排好序的数组的索引6,4,2,0，发现每次都-h,
//所以j=j-h,j>=h是因为0索引在if判断和位置交换的j-h索引处，否则会出现负数角标
//j=i 因为待排序的索引是变化的，而这种变化是通过i体现出来的
for (int j = i; j >=h; j-=h) {
if(greater(arr[j-h],arr[j])){
exch(arr,j,j-h);
}else {
break;
}
}
}
h=h/2;
}
}
/**
* 比较大小，如果c1比c2大，返回true,否则false，正序
*
* @param c1
* @param c2
* @return
*/
private static boolean greater(Comparable c1, Comparable c2) {
return c1.compareTo(c2) > 0 ? Boolean.TRUE : Boolean.FALSE;
}
private static <T> boolean greater(Comparator comparator, T c1, T c2) {
return comparator.compare(c1,c2 ) > 0 ? Boolean.TRUE : Boolean.FALSE;
}
/**
* 将arr数组中i角标和j角标位置互换
*
* @param arr 数组
* @param i 角标
* @param j 角标
* @param <T>
*/
private static <T> void exch(T[] arr, int i, int j) {
T temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
时间复杂度分析
在希尔排序中，增长量h并没固定的规则，很多论文中研究了不同的递增序列，但都无法证明某个序列是最好的，对于希尔排序的时间复杂度分析，设计很多数学知识，这里不做分析了。
所以我们采用事后分析法对希尔排序和插入排序的性能做比较
希尔排序最坏情况事后分析法
public class Shell {
public static void main(String[] args) {
Integer arr[] = new Integer[10000000];
for (int i = 10000000-1; i >=0 ; i--) {
arr[i]=i;
}
System.out.println(Arrays.toString(arr));
LocalDateTime start = LocalDateTime.now();
sort(arr);
LocalDateTime end = LocalDateTime.now();
System.out.println(Arrays.toString(arr));
System.out.println("希尔排序的时间:"+ Duration.between(start,end).getNano());
}
/**
* 正序
*
* @param arr
* @param <T>
*/
public static <T> void sort(Comparable<T>[] arr) {
int h=1;
while (h<arr.length/2) {
h = 2 * h + 1;
}
while (h>=1){
for (int i= h; i <= arr.length-1; i+=h) {
for (int j = i; j >=h; j-=h) {
if(greater(arr[j-h],arr[j])){
exch(arr,j,j-h);
}else {
break;
}
}
}
h=h/2;
}
}
/**
* 比较大小，如果c1比c2大，返回true,否则false，正序
*
* @param c1
* @param c2
* @return
*/
private static boolean greater(Comparable c1, Comparable c2) {
return c1.compareTo(c2) > 0 ? Boolean.TRUE : Boolean.FALSE;
}
/**
* 将arr数组中i角标和j角标位置互换
*
* @param arr 数组
* @param i 角标
* @param j 角标
* @param <T>
*/
private static <T> void exch(T[] arr, int i, int j) {
T temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
插入排序最坏情况时候分析法
public class Insertion {
public static void main(String[] args) {
Integer arr[] = new Integer[10000000];
for (int i = 10000000-1; i >=0 ; i--) {
arr[i]=i;
}
System.out.println(Arrays.toString(arr));
LocalDateTime start = LocalDateTime.now();
sort(arr);
LocalDateTime end = LocalDateTime.now();
System.out.println(Arrays.toString(arr));
System.out.println("插入排序的时间:"+ Duration.between(start,end).getNano());
}
/**
* 正序
*
* @param arr
* @param <T>
*/
public static <T> void sort(Comparable<T>[] arr) {
for (int i = 1; i <arr.length ; i++) {
for (int j = i; j >0 ; j--) {
if(greater(arr[j-1],j)){
exch(arr,j-1,j);
}else {
break;
}
}
}
}
/**
* 比较大小，如果c1比c2大，返回true,否则false，正序
*
* @param c1
* @param c2
* @return
*/
private static boolean greater(Comparable c1, Comparable c2) {
return c1.compareTo(c2) > 0 ? Boolean.TRUE : Boolean.FALSE;
}
private static <T> boolean greater(Comparator comparator, T c1, T c2) {
return comparator.compare(c1,c2 ) > 0 ? Boolean.TRUE : Boolean.FALSE;
}
/**
* 将arr数组中i角标和j角标位置互换
*
* @param arr 数组
* @param i 角标
* @param j 角标
* @param <T>
*/
private static <T> void exch(T[] arr, int i, int j) {
T temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
希尔排序的时间:178000000
插入排序的时间:273000000