插入排序&&希尔排序

插入排序我看了下动图，哦，对对，推荐个好的网站，动态展示算法，排序的

地址：https://visualgo.net/en

嗯，言归正传，插入排序把，就是

把第一个标记成已排序了，然后第二个拿出来，跟第一个比一下，比第一个大就不用动，比第二个小就挪到前边去，效果就是小的前边大的后边，接下来，再把第三个拿出来，跟前边的都比，从第二个开始，然后第一个，倒序比，找个比前变大比后边小的位置，插进去，就跟上图展示的一样

代码实现：

package com.eyuninfo.bean.exception;

public class Order {
	public static void main(String[] args) {
		int[] array = { 5, 2, 100, 2, 3, 8, 10 };
		order(array);
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}

	public static int[] order(int[] array) {

		for (int i = 1; i < array.length; i++) {
			int current = array[i];
			while (i >= 1 && array[i - 1] > current) {
				array[i] = array[i - 1];
				i--;
			}
			array[i] = current;
		}

		return array;
	}
}
           

希尔排序：

在插入排序基础上进一步优化

希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。

如图展示的，数组大小除以2，是5就按着每隔4个取数，把得到的分组分别进行插入排序，然后5再除以2余2，再按着每隔一个取数，插入排序，最后再除以2=1，进行最后一次插入排序

package com.eyuninfo.bean.exception;

public class Order {
	public static void main(String[] args) {
		int[] array = { 5, 2, 100, 2, 3, 8, 10 };
		shellSort(array);
		for (int i = 0; i < array.length; i++) {
			System.out.println(array[i]);
		}
	}

	public static void shellSort(int[] a){
		int n = a.length;
		for(int h = n / 2; h > 0; h /= 2){//希尔增量
			for(int i = h; i < n; i++){
				//将a[i]插入到a[i-h],a[i-2h],a[i-3h]...中
				for(int j = i; j >= h && a[j] < a[j - h]; j -= h){
					int temp = a[j];
					a[j] = a[j-h];
					a[j-h] = temp;
				}
			}
		}
	}
}