問題描述：
有一個有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，解決這種為題的方法用到一種新的排序方法——插入排序法。
具體算法描述如下：
1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從后向前掃描
3. 如果該元素（已排序）大于新元素，將該元素移到下一位置
4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
5. 將新元素插入到下一位置中
6. 重復步驟2
以下是java版插入排序的實現過程。
實現的步驟：
1. 創(chuàng)建一個有序的數列,此數列稱為源數組。
Int []num={1,2,3,5,6,7}
2. 從控制臺接收一個插入的數是4
Scanner input=new Scanner(System.in);
Int n=input.nextInt();
3. 當把4插入進源數組后，就應該有一個新數組比源數組的個數多一個，
所以，創(chuàng)建一個新數組。
Int []newNum=new int[num.length+1];
4. 需要把源數組的值放入新數組
for(int i=0;i<newNum.length;i++)
{
newNum[i]=num[i];
}
經過這樣的賦值數組就變成了如圖所示： 
5．用插入的數字4和源數組的每一個數比較來確定4要插入的位置。 紅色數字是下標 
定義一個插入的位置：
Int index=0;
循環(huán)比較，如果插入數n=4比源數組里的某一個數大，那就把4放入該數的后面
for(int i=0;i<newNum.length;i++)
{
If(n>newNum[i])
Index=i+1;
}
5. 確定好插入數位置后，就要把該位置后面的數字向上移動，請注意：移動的時候一定從最后一個開始。也就是先把數字7移動下標為6的位置，再把數字6移動到下標為5的位置，以此類推。
for(int i=newNum.length-1;i>index;i--)
{
newNum[i]=newNum[i-1];
}
6. 通過以上的移動已經把index位置空出來，接下來就要把n=4放在index位置
newNum[index]=4;
7. 最后輸出newNum新數組的所有值
for(int i=0;i<newNum.length;i++)
{
System.out.println(newNum[i]);
}
北大青鳥通州版權所有
