希尔排序
希尔排序
概述：
首先将数组的一半作为步数，以步数作为起始值，通过插入排序，与之前的以增量为步数的成员进行比对，大的放后面，小的放前面，基本形成有序，之后步数减半，重复以上步骤，直到从小到大排序。
比较插入排序，会减少大量的插入步骤。
场景分析：
4，2，5，1，3
将数组的一半作为步数，
以步数作为起始值，
↓
5，
4，2， 1，3
通过插入排序，与之前的以增量为步数的成员进行比对，
↓
4，2，5，1，3
后一位起始值
↓
1，
4，2，5， 3
大的放后面，小的放前面，
↓ ↓
4，1，5，2，3
3
4，1，5，2，
4，1，3，2，5
3，1，4，2，5
↑
这样基本形成大值在右，小值在左，
然后步数减半，重复以上步骤，
1，
3， 4，2，5
1，3，4，2，5
4
1，3， 2，5
1，3，4，2，5
2，
1，3，4， 5
1，3，2，4，5
直到从小到大有序。
1，2，3，4，5
JAVA实现：
package Sorts;
public class ShellSort {
public static void main(String[] args) {
int[] array = {5,4,3,2,1};
shellSort(array);
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]+",");
}
}
public static void shellSort(int[] array) {
int length = array.length;
int temp = 0;
int j = 0;
//首先将数组的一半作为步数， 之后步数减半，
for (int add = length / 2; add >= 1; add /= 2) {
//以步数作为起始值，
for (int i = add; i < length; i++) {
temp = array[i];
//通过插入排序，与之前的以增量为步数的成员进行比对，
for (j = i; j >= add; j -= add) {
if(temp < array[j - add]) {
//大的放后面，
array[j] = array[j - add];
}else {
break;
}
}
//小的放前面，
array[j] = temp;
}
}
}
}
