插入排序
- 思路
- 代碼
- 性能分析
- 相關排序演算法
思路
1.將陣列劃分為有序、無序區間
2.抓取無序區間的第一個元素，與有序區間的元素進行比較
3.找到合適位置插入
…
哎？這不就是碼牌嗎？
比較時，無非三種情況：
- key > a[i]
- key==a[i]
- key < a[i]
針對情況 1和情況 2，直接尾插
針對情況 3，就先將當前元素 a[i ] 后移，再插入
代碼
public static void insertSort(int[] n) {
//n個數，排(n-1)趟
for (int i = 0; i <n.length-1 ; i++) {
//將陣列劃分為有序、無序區間
//有序：[0,i] 無序：[i+1,n.length)
//無序區間第一個元素作為key
int key=n[i+1];
int j=0;
//遍歷有序區間，與key比較
for (j = i; j>=0; j--) {
//情況3
if (key<n[j]){
n[j+1]=n[j];
}else {
//情況1、2
break;
}
}
n[j+1]=key;
}
System.out.println(Arrays.toString(n));
}
性能分析
相關排序演算法
排序1—選擇排序
排序3—冒泡排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/266659.html
標籤：java