每天学一个算法之插入排序

插入排序(INSERTION-SORT)(设按升序排列)

1、思路

  • 类比思想:
    假设桌上有一叠反面朝上的扑克,一个人左手为空,每次右手从这叠扑克的最上边拿一张扑克放到左手。在将扑克插入左手时,都与之前插入的扑克比较大小,插入适当位置,使之按升序排列。当将最后一张牌插入的时候,这叠扑克升序排序结束,得到升序序列。
  • 伪代码描述:
    A为待排序数组。

    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key

2、C#代码

static void InsertionSort<T>(T[] arr) where T: IComparable<T>
{
    int i, j;
    T tmp;
    for (i = 1; i < arr.Length; i++)
    {
        tmp = arr[i];
        j = i - 1;
        while (j >= 0 && tmp.CompareTo(arr[j]) < 0 ) //tmp < arr[j]
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = tmp;
    }
}

评论

暂无评论