直接插入排序是一种最简单的插入排序法，是一种稳定排序，时间复杂度为 O(n^2)。

基本思想
每次从无序段中取出第一个元素，把它插入到有序段的合适位置，使有序段仍然有序。
这样无序段在变短，有序段在变长，直到无序段变没了。
开始时，有序段只有一个元素就是第一个元素，其它都为无序段。

如下：
大括号中的是有序段。
{30} 20 40 15 35 25
① 20 和 30 比较，30 后移一位
{20 30} 40 15 35 25
② 40 和 30 比较，不用移动
{20 30 40} 15 35 25
③ 15 和 40 比较，40 后移一位，继续比较下一位
④ 15 和 30 比较，30 后移一位，继续比较下一位
⑤ 15 和 20 比较，20 后移一位
{15 20 30 40} 35 25
⑥ 35 和 40 比较，40 后移一位，继续比较下一位
⑦ 35 和 30 比较，不用移动
{15 20 30 35 40} 25
⑧ 25 和 40 比较，40 后移一位，继续比较下一位
⑨ 25 和 35 比较，35 后移一位，继续比较下一位
.....
{15 20 25 30 35 40}

例子

using System;


namespace System
{
    public class Test
    {
        public static void Main()
        {
            int[] array = new int[6] { 30, 20, 40, 15, 35, 25 };

            PrintArray(array);
            Console.WriteLine("-----------------");

            StraightSort.Sort(array);

            PrintArray(array);

            Console.ReadKey();
        }

        public static void PrintArray(int[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                if (i > 0) Console.Write(" ");
                Console.Write(array[i].ToString());
            }
            Console.WriteLine();
        }
    }

    public class StraightSort
    {
        public static void Sort(int[] array)
        {
            for (int i = 1; i < array.Length; i++) // 从第二个开始
            {
                if (array[i] < array[i - 1]) // 前面有大的数，需要后移
                {
                    int j = i - 1; // j 表示前面数的指针
                    int temp = array[i];
                    do
                    {
                        array[j + 1] = array[j]; // 后移元素
                        j = j - 1;
                    } while (j >= 0 && array[j] > temp);// 前面的数还是大的时，继续循环后移

                    array[j + 1] = temp; // array[i] 插入正确的位置上
                }
            }
        }
    }
}