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