【C# 排序】插入排序法InsertionSort

概览

插入排序法（打牌）

算法思想:每次将一个待排序的元素按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

例如：元素13要排序时候，可以认为13之前元素都已经排序完成，此时只要把13与之前元素一 一比较，然后找到合理位置插入。

代码

空间复杂度:(O(1)
时间复杂度︰ O(n)~O(n²)，可以利用折半查找，优化插入排序法。
稳定性：稳定

折半查找，优化插入排序法

当查找到元素和插入的元素相同，继续查找，直到low>hight,然后让low之后的所有元素右移一个位置（目的保证稳定性），插入元素。

当A[mid]=(A[0])时，为了保证算法的“稳定性”，应继续在mid)所指位置右边寻找插入位置。
比起“直接插入排序”，比较关键字的次数减少，但是移动元素的次数没变，整体来看时间复杂度依然是O(n^2)

如下图：

当找到60的位置，此时不能停止查找，应该继续查找

 继续查找

 low>high 停止查找，将low之后的所有元素后移一个位置

60的插入排序完成

代码如下：

 链表的插入排序

 C#代码

 public static class Sort
    {
        /// 

        /// 直接插入排序法
        /// 
        /// 
     public static void  StraightInsertionSort(int[] array)
        {
            for (int i = 1; i < array.Length; i++)
            {
                int item = 0;
                item=array[i];
                for (int j = i-1; j>=0 ; j--)
                {
                    if (item < array[j])
                    {
                        array[j+1] = array[j];
                    }
                    else
                    {
                        array[j + 1] =item;
                        break;
                    }
                }
            }
        }
        /// 

        /// 加入查找的改进，折半插入查找
        /// 
        /// 
        public static void StraightInsertionSort2(int[] array)
        {
            for (int i = 1; i < array.Length; i++)
            {
                int item = 0;
                item = array[i];
                int mid   ,low ,high;
                low =0;
                high = i - 1;
                mid = high / 2;
                ///折半查找位置
                while (low <= high)
                {
                    mid = (low + high)/2;
                    if (item < array[mid])
                    {
                        high = mid - 1;

                    }
                    else
                    {
                        low = mid + 1;

                    }
                }
                //找到位置后，将[low,i-1]元素都后移一位，最后将元素插入到low的位置
                for (int j = i - 1; j >= low ; j--)
                {
                    array[j+1] = array[j ];
                }
                array[low] = item;
            }
        }
    }