[DataStructure]Insertion Sort(插入排序法)

插入排序法的步驟就是把後面的牌抽到前面適當的位置插入

以{123456,123,12,33,44,55}為例

將123插入到最前面
[123 123456] 12 33 44 55
將12插入到最前面
[12 123 123456] 33 44 55
將33插入到12跟123之間
[12 33 123 123456] 44 55
將44插入到33跟123之間
[12 33 44 123 123456] 55
將55插入到44跟123之間
[12 33 44 55 123 123456]

Java

public class test{
	static int [] num = {123456,123,12,33,44,55};
	public static void main(String [] argv){
		insertion_sort();
		for(int i : num){
			System.out.print(i + " ");
		}
	}
	public static void insertion_sort(){
		for(int i = 1; i < num.length; i++){
			//紀錄目前要插入的值
			int tmp = num[i];
			//插入值的前一筆資料為基準點
			int datum = i - 1;
			//尋找到比插入值還要小的，若否則值往後推
			while(datum > -1 && tmp < num[datum]){
				num[datum+1] = num[datum];
				datum--;
			}
			//datum因不符合while而跳出，所以datum前一筆為最後符合的值，插入
			num[datum+1] = tmp;
		}		
	}
}