插入排序
一、分類
1北专、直接插入排序
2禀挫、希爾插入排序
1、直接插入排序
A.含義
講一個(gè)記錄插入到已經(jīng)排序好的有序列表當(dāng)中逗余。
B.步驟
a.sorted數(shù)組的第0個(gè)位置沒有放入數(shù)據(jù)
b.從sorted第二個(gè)數(shù)據(jù)開始處理:如果該數(shù)據(jù)比前面的數(shù)據(jù)小.說明該數(shù)據(jù)需要往前面移動(dòng)特咆。
（1）首先將該數(shù)據(jù)備份到 sorted的0號(hào)位置作為"哨兵"
（2）然后將該數(shù)據(jù)的前面那個(gè)數(shù)據(jù)往后移動(dòng)
（3）然后往前搜索，找插入的位置
（4）找到插入的位置之后，第0位置的那個(gè)數(shù)據(jù)插入到對(duì)應(yīng)的位置腻格。
直接插入排序.PNG
2画拾、希爾排序（縮小增量排序 diminishing increment sort）
A.含義
先將整個(gè)等待排序的代碼分割成為若干的子序列，分別進(jìn)行直接插入排序菜职，等待整個(gè)序列中記錄基本有序的時(shí)候青抛，再對(duì)全體進(jìn)行一次直接插入排序
B.插入排序代碼
main()方法的寫法
public static void main(String[] args) {
Random r = new Random();
int size = 10;
int[] array = new int[size];
//排序前,賦值并且打印
System.out.println("排序前:");
for (int i = 0; i < array.length; i++) {
array[i] = r.nextInt(100);
System.out.print(array[i]+" ");
}
System.out.println();
//調(diào)用排序方法
insertSort(array);
//排序后,打印輸出結(jié)果
System.out.println("排序后:");
for (int i = 1; i < array.length; i++) {
System.out.print(array[i]+" ");
}
System.out.println();
}
排序方法的寫法
//直接插入排序的方法
public static void insertSort(int[] arr){
int len = arr.length;
for (int i = 2; i < len; i++) {
if(arr[i]<arr[i-1]){
arr[0] = arr[i];
arr[i] = arr[i-1];
int insertPosition = 0;
for (int j = i-2; j >=0; j--) {
if (arr[j]>arr[0]){
arr[j+1] = arr[j];
}else{
insertPosition = j+1;
break;
}
}
arr[insertPosition] = arr[0];
}
}
}
運(yùn)行結(jié)果
排序前:
2 68 46 58 81 61 18 27 54 43
排序后:
18 27 43 46 54 58 61 68 81 