基础算法之插入排序Insertion Sort

原理

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。相信大家都打过扑克牌，很好理解。

例子

将数组[5,6,3,1,8,7,2,4]进行从小到大排序

排序步骤：

从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤2~5

动画演示

代码参考

　　 　　static void Main(string[] args)
        {
            int[] intArray = { 3, 6, 4, 2, 5, 1 };
            Insertion_Sort(intArray);

            foreach (var item in intArray)
            {
                Console.WriteLine(item);
            }
            Console.ReadLine();
        }

        static void Insertion_Sort(int[] unsorted)
        {
            int i, j, temp;
            for (i = 1; i < unsorted.Length; i++)
            {
                // 检查有无序状态
                if (unsorted[i-1] > unsorted[i])
                {
                    temp = unsorted[i];
                    // 移位
                    for (j = i; j > 0 && unsorted[j - 1] > temp; j--)
                    {
                        unsorted[j] = unsorted[j - 1];
                    }
                    // 强势插入
                    unsorted[j] = temp;
                }
            }
        }

参考资料

维基百科http://en.wikipedia.org/wiki/Insertion_sort