每天学一个算法之插入排序
文章目录
插入排序(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;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论