作者：vuefine 文献： - Data Structures and Algorithms Using C# |Michael Mcmillan - 数据结构与算法 | 邓俊辉 平台：.NET 2.0+
前面总结了最基本的排序：冒泡排序，随机生成了10个元素，并模拟了整个过程，共经历9轮，总计需要45次比较两两比较，模拟的结果显示，有2对元素两两比较了多达6次，显然这是冗余的！
今天，我要模拟的另一种排序算法：插入排序，insert sort，什么是插入排序？ 如果不知道，也无妨，看下图，你基本便能知晓插入排序的思想。那么插入排序的算法怎么写？整个排序过程是怎样的呢？
首先我们还是，准备自己的集合（请点击查看我自己封装的专门用于排序MyArray对象），在模拟插入排序时，我又增加了几个方法，现在为了方便我再把代码贴到这里，新增加的功能接口包括：
在指定位置插入元素统计插入元素的个数 public class MyArray { private MyElement[] _array; private int _upper; private int _cnt; private readonly int _size; public MyArray(int size) { _size = size; _array = new MyElement[size]; _upper = size - 1; _cnt = 0; } //统计插入元素的个数 public int InsertCount { get { return _cnt; } } public void Insert(MyElement item) { _array[_cnt++] = item; } //在指定位置插入元素 public void InsertAt(MyElement item,int index) { if(index <0 || index>_size) throw new ArgumentException(); for (int i = _cnt;i >index; i--) { _array[i] = _array[i - 1]; } _array[index] = item; _cnt++; } public void Clear() { for (int i = 0; i < _cnt; i++) _array[i].Val = 0; _cnt = 0; } public override string ToString() { StringBuilder stringBuilder = new StringBuilder(); foreach (var item in _array) { stringBuilder.Append(item.Val + " "); } return stringBuilder.ToString(); } public void FillRandomValue() { Random random = new Random(_size * 5); for (int i = 0; i < _size; i++) { var element = new MyElement(); element.Val = (int)(random.NextDouble() * _size * 5); this.Insert(element); } } public void Printf() { Console.Write(this.ToString()); } public MyElement GetAt(int index) { if (index < 0 || index > _size) throw new ArgumentException(); return _array[index]; } //如果a>b，交换；否则直接return public static void Swap(MyElement a, MyElement b) { if (a.Val <= b.Val) return; int t = a.Val; if (a.Val > b.Val) { a.Val = b.Val; b.Val = t; } } }新加的一个方法：InsertAt(ele,index)，它的功能是在向量指定位置处插入元素，同时将插入后的所有元素统一向后移动一个位置，移动时，要从最后一个开始逐次移动！
/// <summary> /// /// </summary> /// <param name="item"></param> /// <param name="index">插入元素的位置</param> public void InsertAt(MyElement item,int index) { if(index <0 || index>_size) throw new ArgumentException(); for (int i = _cnt;i >index; i--) { _array[i] = _array[i - 1]; } _array[index] = item; _cnt++; }插入排序算法的过程。首先，取出无序数组中的第一个元素，插入到有序数组的0号索引中。
MyArray sortedarr = new MyArray(size); sortedarr.Insert(myarr.GetAt(0)); //插入原数组的第一个元素接着，遍历无序数组的每一个元素，找到元素在有序数组的合适位置，然后插入到有序序列中。
for (int i = 1; i < size; i++) { MyElement ie = myarr.GetAt(i); insertElementAtSortedArray(sortedarr,ie); }上面中insertElementAtSortedArray方法实现了将ie元素插入sortedarr的功能。那么它是如何实现的呢？请看：
public static void insertElementAtSortedArray(MyArray sortedArray, MyElement ele) { //确定元素ele插入后的位置 int insertIndex = decideIndexAfterInsert(sortedArray, ele); sortedArray.InsertAt(ele, insertIndex); }一种二分查找版本，进而能够实现实现插入排序的稳定。
//确定元素ele插入后的位置 public static int decideIndexAfterInsert(MyArray sortedArray, MyElement ele) { int lo = 0; int hi = sortedArray.InsertCount; while (lo < hi) { int mi = (lo + hi) >> 1; if (ele.Val < sortedArray.GetAt(mi).Val) hi = mi; else lo = mi + 1; } return lo; }二分查找完后，返回的lo为大于ele的元素的最小秩。若插入元素有多个相同元素时，总能保证插入到秩最大者处。因此，基于这个二分查找版本实现的“插入排序”是稳定的！
我们解释下为什么lo是这么个语义？ lo初始值为0， hi为待排序数组的元素个数InsertCount，lo，hi的取值范围如下
0 <= lo < InsertCount l <=hi <= InsertCountele一定位于[lo,hi），注意是前闭后开，因为hi是元素个数，ele取不到hi。循环体内保证了[0,li)的元素不大于ele，[hi,InsertCount)的元素比ele大，
ele[0,li) <=ele 且 ele[hi,InsertCount) > ele循环跳出时，li>=hi， [0,hi<=li) <=ele 且ele[hi,InsertCount)>ele 所以li的位置为插入元素ele的位置。疑问：返回hi可行吗？
整个循环，记录下lo，hi，mi的取值历程！我们看下：
在插入39时，lo=0, hi=4, 此时mi=2, 与35比较后，区间取右分支，修改lo=3； mi = (3+4)/2=3, 与42比较后，区间取左分支，修改hi=3, 此时lo=hi，退出while循环 此时的位置3为39元素插入后的位置，插入后，序列由
11 24 35 42变为序列：
11 24 35 39 42那么我们看下插入排序两两比较，次数大于2次的记录：
因此，插入排序比冒泡排序，冗余比较的次数大大下降了！
那么，我们按照上篇写的统计代码的执行时间的方法（用C#描述数据结构1：统计代码执行时间对象），统计下执行随机生成的100个元素，冒泡排序和插入排序的执行时间比较， 保证两次随机产生的集合元素、顺序都一致，因为.NET中的Random是伪随机分布的，所以可以保证！ 冒泡排序，排序100个元素，所用时间93ms
来看下，插入排序，排序相同的100个元素，大约31ms，
冒泡排序不愧是暴利啊！！！ 插入排序，明显效率改进了不少！
总结： 1）冒泡排序很暴力 2）基于这个版本的二分查找的插入排序，是稳定的！ 3）一个优秀的排序算法是通过尽可能少的比较，来完成对整个序列的排序。
程序模拟实验所用到的所有源码，包括冒泡排序，插入排序，代码运行时长统计 http://download.csdn.net/detail/daigualu/9776250
