2018-09-19
思路：
將一個記錄插入到已排序好的有序表中，從而得到一個新叔壤，記錄數(shù)增1的有序表瞎饲。
即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入炼绘，直至整個序列有序為止嗅战。
要點：設立哨兵，作為臨時存儲和判斷數(shù)組邊界之用俺亮。
如果碰見一個和插入元素相等的驮捍，那么插入元素把想插入的元素放在相等元素的后面。
所以脚曾，相等元素的前后順序沒有改變东且，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩(wěn)定的本讥。
public static void main(String[] args) {
int arr[] = {3, 5, 7, 2, 4, 9, 1, 6, 10, 8};
System.out.println("排序前:");
System.out.println(Arrays.toString(arr));
insertSort(arr);
System.out.println("排序后:");
System.out.println(Arrays.toString(arr));
}
private static void insertSort(int[] arr) {
for (int i=1; i<arr.length; i++){
int j=i;
int index = arr[i];//待插入元素
while (j>0 && index <arr[j-1]){//通過循環(huán)珊泳，逐個后移一位找到要插入的位置
arr[j] = arr[--j];
}
arr[j] = index;
}
}
