什么是希尔排序，可以参考这篇文章：希尔排序原理，图文并茂，通俗易懂
public class ShellSort {
public static void main(String[] args) {
int[] a = {1, 3, 5, 2, 4};
int length = a.length / 2;
while (length >= 1) {
sort(a, length);
length /= 2;
}
sort(a, length);
System.out.println(Arrays.toString(a));
}
/**
* @param a 排序的数组
* @param n 步长
* */
private static void sort(int[] a, int n) {
for (int i = 0; i < a.length; i++) {
for (int j = i + n; j <a.length; j++) {
if (a[i] > a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
}
发现自己写了个错的希尔排序。。。
if (a[i] > a[j]) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
这里一不小心用了冒泡排序！！！应该是插入排序，两个元素交换位置非要使用插入排序，真让人头大。最终正确版本的希尔排序 ：
public class ShellSort {
public static void main(String[] args) {
int[] a = {1, 3, 5, 2, 4};
int length = a.length / 2;
while (length >= 1) {
sort(a, length);
length /= 2;
}
sort(a, length);
System.out.println(Arrays.toString(a));
}
/**
* @param a 排序的数组
* @param n 步长
* */
private static void sort(int[] a, int n) {
int j;
for (int i = n; i < a.length; i++) {
int temp = a[i];
for (j = i - n; j >= 0; j -= n) {
if (a[j] > temp) {
a[j + n] = a[j];
} else {
break;
}
}
a[j + n] = temp;
}
}
}
插入排序：有序队列中右移插入元素，并且是从右向左遍历
