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;
        }

		

  //查找数值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;    //插入
        }
    }
}