插入排序是最简单（最容易理解）的一种排序算法。

其基本操作是将一个数插入到已经有序的数组中，那么我们要做的是确定插入到什么位置，所有在这个位置之后的数后移一个位置，从而给这个要插入的数腾出位置。所以关键点是找插入位置。

最简单的办法，从最后一个元素开始找，边找边后移，一直到找到合适的插入位置。

首先，数组第一个元素我们视为有序。第二个元素，跟第一个比较排序之后，前两个元素组成一个有序序列。第n个元素，从前面的有序序列(n-1个元素)的最后一个元素开始比较，直到找到合适的插入位置，插入即可，最终形成一个有序序列。

 代码(c#):

static void InsertSort(int[] numbers)        {            int temp, j;            for (int i = 1; i < numbers.Length; i++)            {                temp = numbers[i];                j = i;                while (j > 0 && numbers[j - 1] > temp)                {                    numbers[j] = numbers[j - 1];                    j--;                }                numbers[j] = temp;            }        }

  

还有一种稍高效一点的方法，因为我们要插入的数组已经是有序的了，所以可以用二分查找找到插入位置，然后后移这个位置之后的元素，插入新值。

代码(c#):

static void BinaryInsertSort(int[] myArray)        {            for (int i = 1; i < myArray.Length; i++)            {                if (myArray[i] < myArray[i - 1])                {                    int low = 0;                    int high = i - 1;                    int mid = (low + high) / 2;                    // 找到插入位置 low                    while (low <= high)                    {                        if (myArray[i] >= myArray[mid])                        {                            low = mid + 1;                            mid = (low + high) / 2;                        }                        if (myArray[i] < myArray[mid])                        {                            high = mid - 1;                            mid = (low + high) / 2;                        }                    }                    // 将插入位置后面的元素后移一个位置，后移之前保存要插入的值myArray[i]                    int temp = myArray[i];                    for (int j = i; j > low; j--)                    {                        myArray[j] = myArray[j - 1];                    }                    myArray[low] = temp;                }            }        }

 

最后，从代码可以看出。直接插入排序的时间复杂度是O(n*n)。虽然折半插入排序减少了关键字间的比较次数，但移动记录的次数不变，所有时间复杂度仍是O(n*n)。