【任务目标】

将一组无序数组变为有序

【插入排序原理】

将数组分为两部分，有序的部分和无序的部分。每次从无序的部分中选择一个元素，将该元素插入有序部分，多次插入后，有序部分的元素越来越多，无序部分的元素越来越少，直到无序部分元素为0。

                            

可以看见，每次迭代时，有序部分元素数量加一，无序部分元素数量减一。若有n个元素，那么要迭代n次。

无序部分减少的那个元素可以按照从左到右的顺序一个个取。

有序部分增加的那个元素需要从右往左一个个比较确定位置，也就是有序向量的插入方法。

实际上对于某个无序数组，可以看做由有序部分+无序部分组成。刚看到这个数组时，从左到右，有序部分元素数量为0，无序部分元素数量为n。

【插入排序原理概括】

将数组分为有序和无序两部分，通过迭代，不断将无序部分的首元素插入有序部分中。

【代码实现】

using System;

namespace InsertionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] A = new int[30];
            Random ra = new Random();
            for (int i = 0; i < 30; i++)
            {
                A[i] = ra.Next(200);
            }
            Program ps = new Program();
            ps.InsertSort(A);
            Console.WriteLine("排序结果:");
            foreach (int a in A)
            {
                Console.Write(a + " ");
            }

            Console.ReadKey();
        }


        public void InsertSort(int[] A)
        {
            int temp;
            int j;
            for (int i = 1; i < A.Length; i++)//直接从第二个元素开始
            {
                temp = A[i];
                j = i-1;
                while (j>=0&&temp<A[j])//用<确保相同元素的相对次序不变，而不用<=
                {
                    A[j+1] = A[j];//将大的元素后移，而不是每比较完就交换
                    j--;//从右往左比较，所以--,而不是++
                }
                A[j+1] = temp;
            }
        }
    }
}

【实现结果】

【考虑其他情况】

【元素已经有序或接近有序】例如，对A={0,1,2,3,4,5,6,7,8,9}和A={3,1,2,0,4,5,6,7,8,9}，按照插入算法的执行顺序，我们发现其很快就能完成整个算法。

【元素完全逆序或混乱】例如，对A={9,8,7,6,5,4,3,2,1,0}，按照插入算法的执行顺序，在插入阶段会发生很多次比较，耗费大量的时间，这是我们可以改进的地方，实际上也就是改进有序向量的插入算法。

【有多个相同的元素】排序前后相同元素的相对次序不会改变

【插入排序改进】

 public void InsertSort2(int[] A)
        {
            int temp;
            int j;
            for (int i = 1; i < A.Length; i++)//直接从第二个元素开始
            {
                temp = A[i];
                int key = BinSearch(A, temp, 0, i);//在前i个元素中查找
                j = i - 1;
                while (j >= key)//二分查找相当于将比较的截止位置从0换成key，while循环内的代码不用改
                {
                    A[j + 1] = A[j];//将大的元素后移，而不是每比较完就交换
                    j--;//从右往左比较，所以--,而不是++
                }
                A[j + 1] = temp;
            }
        }

        //二分查找算法 https://blog.csdn.net/enternalstar/article/details/103575546
        public int BinSearch(int[] A,int a, int lo,int hi)
        {
            while (lo<hi)
            {
                int middle = lo + ((hi - lo) >> 1);
                if (a < A[middle])
                {
                    hi = middle;
                }
                else
                {
                    lo = middle + 1;
                }
            }
            return lo;

        }

【改进结果】

 

【插入排序和冒泡排序的区别】

• 越往后，冒泡排序越来越快，插入排序越来越慢
• 冒泡排序的思想是从整体上实现数组有序，插入排序的思想是从局部实现有序然后再整体有序，类同归并排序

冒泡排序法和插入排序法的比较

【参考】

[1]邓俊辉.数据结构（C++语言版）第三版[M]

【相关链接】

排序算法C#实现之冒泡排序详解

排序算法C#实现之归并排序详解

排序算法C#实现之选择排序详解