插入排序算法(Insertion Sort)的两种实现

插入排序算法是常见的排序算法之一。其原理是从左往右遍历，每次对所取到的值（元素）把它插入到合适的位置，使得从开始到目前取到的值是一个已经排好序的状态。所以当我们取到最后一个值时，前面所有的都已经是排好序的数组了。

下面给出两种插入排序的实现。第一种是常规插入排序，最坏时间复杂度为O(n^2).

/// <summary>
        /// Insertion Sort
        /// </summary>
        /// <param name="array">the array to be sorted</param>
      
        public static void InsertionSort(int[] array)
        {
            int key = 0;  //key is used to save the value of array[i] 
            for (int i = 1; i < array.Length; i++)
            {
                key = array[i]<mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny_mce/themes/advanced/langs/zh.js" mce_src="http://hi.images.csdn.net/js/blog/tiny_mce/themes/advanced/langs/zh.js"></mce:script><mce:script type="text/javascript" src="http://hi.images.csdn.net/js/blog/tiny_mce/plugins/syntaxhl/langs/zh.js" mce_src="http://hi.images.csdn.net/js/blog/tiny_mce/plugins/syntaxhl/langs/zh.js"></mce:script>;
                int j = i;  //j is used to save the position of array[i]
                while (j >= 1 && array[j - 1] > key)
                {
                    array[j] = array[j - 1];
                    j--;
                }
                array[j] = key;
            }
        }

因为对于当前的值（也就是代码中的 key）来讲，其前面的值已经排好序，如果逐一比较，很明显是很费时的。这里第二种实现用了二分查找的思想，虽然不能提高总体速度（因为我们需要移动数组元素的总次数不会减少），但是相对于第一种来讲，查找位置的速度会提高很多。

 /// <summary>
        /// Implement Insertion Sort through Binary Search
        /// </summary>
        /// <param name="array"> the array to be sorted</param>
        public static void InsertionSortBinary(int[] array)
        {
            int key = 0;
            for (int i = 1; i < array.Length; i++)
            {
                key = array[i];
                int position = InserstionPosition(array, key, 0, i - 1);
                for (int j = i; j > position; j--)
                {
                    array[j] = array[j - 1];
                }
                array[position] = key;
            }
        }

/// <summary>
        /// Find the position where the key should be placed
        /// </summary>
        /// <param name="array">the array to be sorted</param>
        /// <param name="key">the key value </param>
        /// <param name="begin">the starting search position in the array</param>
        /// <param name="end">the finishing search position in the array</param>
        /// <returns>the position where the key should be placed</returns>
        
        public static int InserstionPosition(int[] array, int key, int begin, int end)
        {
            while (begin <= end)
            {
                int mid = begin + (end - begin) / 2;  、、
                if (array[mid] > key)
                {
                    end = mid - 1;
                }
                else if (array[mid] < key)
                {
                    begin = mid + 1;
                }
                else
                {
                    return mid;
                }
            }
            return end + 1;
        }