1.1 算法描述
(1)从第一个元素开始,该元素可以认为已经被排序;
(2)取出下一个元素,在已经排序的元素序列中从后向前扫描;
(3)如果该元素(已排序)大于新元素,将该元素移到下一位置;.
(4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
(5) 将新元素插入到该位置后;
(6)重复步骤2~5。
1.2 动图演示
1.3 C#代码实现
public Class SortDemo
{
public void InsertionSort(int[] arr)
{
int temp=0;
//遍历待插入的数(从第二位开始)
for(int i=1;i<arr.Length;i++)
{
temp=arr[i];//待插入的数
int j=i-1;//(j为已排序的待插入的位置序号)
//若已排序的数大于待插入数,则往后移一位
while(j>=0&&arr[j]>temp)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=temp;//将待插入的数放入插入位置
}
}
}