每天学一个算法（一、插入排序）

一、插入排序（INSERTION-SORT）（设按升序排列）思路类比思想： 假设桌上有一叠反面朝上的扑克，一个人左手为空，每次右手从这叠扑克的最上边拿一张扑克放到左手。在将扑克插入左手时，都与之前插入的扑克比较大小，插入适当位置，使之按升序排列。当将最后一张牌插入的时候，这叠扑克升序排序结束，得到升序序列。伪代码描述： 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] = keyC#代码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; }}