C#插入排序
C#插入排序一、插入排序的种类
包括：直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。属于稳定排序的一种（通俗地讲，就是两个相等的数不会交换位置） 。
二、插入排序算法原理
插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序
第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；
第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中.....
第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。
三、算法分析
平均时间复杂度：O(n2)
空间复杂度：O(1) (用于记录需要插入的数据)
四、插入排序稳定性
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素
比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
五、C#插入排序算法
/// <summary>
/// 插入排序(升序)
/// </summary>
public static int[] InsertionSort(int[] needSortArray)
{
for (int i = 1; i < needSortArray.Length; i++)
{
int key = needSortArray[i];// 相当于[当前牌],这里赋给key起临时保存的作用
// 将当前牌与手中的牌依次比较
int j = i - 1;
while (j >= 0 && key < needSortArray[j])
{
// 将元素后移
needSortArray[j + 1] = needSortArray[j];
j--;
}
// j+1(因为上边的while循环多做了一次判断)即为当前牌插入的位置
needSortArray[j + 1] = key;
}
return needSortArray;
}
六、插入排序算法实例
以下面5个无序的数据为例：
65 27 59 64 58
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
七、算法优化
插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。
//查找数值iData在长度为iLen的pDataArray数组中的插入位置
int FindInsertIndex(int *pDataArray, int iLen, int iData)
{
int iBegin = 0;
int iEnd = iLen - 1;
int index = -1; //记录插入位置
while (iBegin <= iEnd)
{
index = (iBegin + iEnd) / 2;
if (pDataArray[index] > iData)
iEnd = index - 1;
else
iBegin = index + 1;
}
if (pDataArray[index] <= iData)
index++;
return index;
}
/********************************************************
*函数名称：BinaryInsertSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 二分查找插入排序
*********************************************************/
void BinaryInsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int index = FindInsertIndex(pDataArray, i, pDataArray[i]); //二分寻找插入的位置
if (i != index) //插入位置不为i，才挪动、插入
{
int j = i;
int temp = pDataArray[i];
while (j > index) //挪动位置
{
pDataArray[j] = pDataArray[j-1];
j--;
}
pDataArray[j] = temp; //插入
}
}
}