經(jīng)常碰到這樣一類排序問題：把新的數(shù)據(jù)插入到已經(jīng)排好的數(shù)據(jù)列中释移。
- 將第一個(gè)數(shù)和第二個(gè)數(shù)排序晴埂，然后構(gòu)成一個(gè)有序序列
- 將第三個(gè)數(shù)插入進(jìn)去，構(gòu)成一個(gè)新的有序序列田轧。
- 對(duì)第四個(gè)數(shù)、第五個(gè)數(shù)……直到最后一個(gè)數(shù)鞍恢，重復(fù)第二步傻粘。
如何寫寫成代碼：
- 首先設(shè)定插入次數(shù)，即循環(huán)次數(shù)帮掉，for(int i=1;i<length;i++)弦悉，1個(gè)數(shù)的那次不用插入。
- 設(shè)定插入數(shù)和得到已經(jīng)排好序列的最后一個(gè)數(shù)的位數(shù)蟆炊。insertNum和j=i-1稽莉。
- 從最后一個(gè)數(shù)開始向前循環(huán)，如果插入數(shù)小于當(dāng)前數(shù)涩搓，就將當(dāng)前數(shù)向后移動(dòng)一位污秆。
- 將當(dāng)前數(shù)放置到空著的位置，即j+1。
public void insertSort(int[] a){
int length=a.length;//數(shù)組長(zhǎng)度，將這個(gè)提取出來是為了提高速度疮方。
int insertNum;//要插入的數(shù)
for(int i=1;i<length;i++){//插入的次數(shù)
insertNum=a[i];//要插入的數(shù)
int j=i-1;//已經(jīng)排序好的序列元素個(gè)數(shù)
while(j>=0&&a[j]>insertNum){//序列從后到前循環(huán)，將大于insertNum的數(shù)向后移動(dòng)一格
a[j+1]=a[j];//元素移動(dòng)一格
j--;
}
a[j+1]=insertNum;//將需要插入的數(shù)放在要插入的位置庸推。
}
}
