C#直接插入排序(InsertionSort)

1.1 算法描述

(1)从第一个元素开始,该元素可以认为已经被排序;

(2)取出下一个元素,在已经排序的元素序列中从后向前扫描;

(3)如果该元素(已排序)大于新元素,将该元素移到下一位置;.

(4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

(5) 将新元素插入到该位置后;

(6)重复步骤2~5。

1.2 动图演示

C#直接插入排序(InsertionSort)

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;//将待插入的数放入插入位置
              }
      }
}