Java 排序算法 —— 选择排序+插入排序+希尔排序

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法 叫做选择排序，因为它在不断地选择剩余元素之中的最小者。 

//（升序）
public static void Sort(int[] a) {
	int N = a.length; 
	for (int i = 0; i < N; i++) {
		int min = i; 
		for (int j = i + 1; j < N; j++) {
			if (a[j] < a[min]) {
				min = j;
			}
		}
		int temp = a[i];
		a[i] = a[min];
		a[min] = temp;
	}
}
           

插入排序

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。插入排序也是这样的，对于 0 到 N-1 之间的每一个 i，将 a[i] 与 a[0] 到 a[i-1] 中比它小的所有元素依次有序地交换。 在索引i由左向右变化的过程中，它左侧的元素总是有序的，所以当i到达数组的右端时排序就完成了。

//（升序）
public static void Sort(int []a) {
	int N = a.length;
	for (int i = 1; i < N; i++) {
		for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
			int temp = a[j];
			a[j] = a[j-1];
			a[j-1] = temp;
		}
	}
}
           

希尔排序

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组 的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需 要N-1 次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。 

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。 在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。

实现希尔排序的一种方法是对于每个 h，用插入排序将 h 个子数组独立地排序。但因为子数组是相互独立的，一个更简单的方法是在h子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格。只需要在插入排序的代码中将移动元素的距离由1改为h即可。这样，希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。 

//（升序）
public static void Sort(int[] a) {
	int N = a.length;
	int h = 1;
	while (h < N / 3) {
		h = 3 * h + 1;
	}
	while (h >= 1) {
		for (int i = h; i < N; i++) {
			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;
			}
		}
		h = h / 3;
	}
}
           

参考资料：算法（第四版）