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;
	}
}
           

參考資料：算法（第四版）