Accp java 插入排序

問(wèn)題描述：
有一個(gè)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，解決這種為題的方法用到一種新的排序方法——插入排序法。
具體算法描述如下：
　　1. 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
　　2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
　　3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
　　4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
　　5. 將新元素插入到下一位置中
　　6. 重復(fù)步驟2
以下是java版插入排序的實(shí)現(xiàn)過(guò)程。
實(shí)現(xiàn)的步驟：

1. 創(chuàng)建一個(gè)有序的數(shù)列,此數(shù)列稱(chēng)為源數(shù)組。
Int []num={1,2,3,5,6,7}

2. 從控制臺(tái)接收一個(gè)插入的數(shù)是4
Scanner input=new Scanner(System.in);
Int n=input.nextInt();

3. 當(dāng)把4插入進(jìn)源數(shù)組后，就應(yīng)該有一個(gè)新數(shù)組比源數(shù)組的個(gè)數(shù)多一個(gè)，
所以，創(chuàng)建一個(gè)新數(shù)組。
Int []newNum=new int[num.length+1];

4. 需要把源數(shù)組的值放入新數(shù)組
for(int i=0;i<newNum.length;i++)
{
newNum[i]=num[i];
}

經(jīng)過(guò)這樣的賦值數(shù)組就變成了如圖所示：

5．用插入的數(shù)字4和源數(shù)組的每一個(gè)數(shù)比較來(lái)確定4要插入的位置。 紅色數(shù)字是下標(biāo)

定義一個(gè)插入的位置：
Int index=0;
循環(huán)比較，如果插入數(shù)n=4比源數(shù)組里的某一個(gè)數(shù)大，那就把4放入該數(shù)的后面
for(int i=0;i<newNum.length;i++)
{
If(n>newNum[i])
Index=i+1;
}

5. 確定好插入數(shù)位置后，就要把該位置后面的數(shù)字向上移動(dòng)，請(qǐng)注意：移動(dòng)的時(shí)候一定從最后一個(gè)開(kāi)始。也就是先把數(shù)字7移動(dòng)下標(biāo)為6的位置，再把數(shù)字6移動(dòng)到下標(biāo)為5的位置，以此類(lèi)推。
for(int i=newNum.length-1;i>index;i--)
{
newNum[i]=newNum[i-1];
}

6. 通過(guò)以上的移動(dòng)已經(jīng)把index位置空出來(lái)，接下來(lái)就要把n=4放在index位置
newNum[index]=4;

7. 最后輸出newNum新數(shù)組的所有值
for(int i=0;i<newNum.length;i++)
{
System.out.println(newNum[i]);
}

北大青鳥(niǎo)通州版權(quán)所有