这篇文章主要着重讲下直接插入排序算法的分析过程与源代码实现方法:
直接插入排序算法原理,在这里我不多说了,各位可以参考<<算法导论中文版>>这本书。
这里的算法实现主要把整型变量r作为监视哨，存放待插入的记录。监视哨有两个作用：一个用来备份待插入的记录，以便前面关键字较大的记录后移；二是防止关键字比较时越界，当待插入记录list[i]比较到r时能结束比较。
直接插入排序的C#实现代码：
using System;
using System.Collections.Generic;
using System.Text;
namespace DataStructureConsoleApplication
{
public class InsertSort
{
public void Sort(int[] list)
{
int i, j;
for (i = 1; i < list.Length; i++)
{
int r = list[i];//将待插入的记录存放到监视哨r中。
j = i;
while ((list[j-1]>r)) //寻找插入位置
{
list[j] = list[j-1]; //记录后移
--j;
}
list[j] = r; //将待插入记录插入到已排序的序列中
}
}
}
public class mainClass
{
public static void Main(string[] args)
{
int[] iArray = new int[] { 1, 3, 5, 2, 4, 6 };
InsertSort iSort = new InsertSort();
iSort.Sort(iArray);
int m=0;
for (; m < iArray.Length; m++)
{
Console.WriteLine("{0}",iArray[m]);
}
}
}
}
运行结果：
1
2
3
4
5
6
算法分析执行过程：
1、当int i=1,判断是否小于list的长度。如果小于的话，执行循环内部的运算，否则退出循环。（大家都知道直接插入排序适用于待排序的记录数目较少且基本有序的情况。否则的话，也可以考虑其他希尔排序等等。），好了，直接将list[1]赋值给r了，这时list[1],r的值为3,接下来j的值为1,然后while循环判断list[0]是否大于r,也就是说是否1>3,好明显这是不成立的，因此直接退出while循环，执行list[1]=r这句了。
2、当for循环之后，int i=2时，判断i是否小于list的长度。这时将list[2]的值赋给r，接下来j的值为2,然后while循环判断list[1]是否大于r,也就是说是否3>5,好明显不成立，因此退出了while循环，执行list[2]=r这句了。
3、当for循环后，int i=3时，判断i是否小于list的长度。这时将list[3]的值赋给r，接下来j的值为3,然后while循环判断list[2]是否大于r,也就是说是否5>2，条件成立，执行循环内部的运算，将list[2]与list[3]所对应的内存地址交换（记录后移），即排好顺的列表是1 3 2 5 4 6了。
4、执行--j，这时j的值是2，然后while循环判断list[1]是否大于r，也就是说3>2，条件成立，执行循环内部的运算，将list[2]与list[1]所对应的内存地址交换（记录后移），即排好顺的列表是1 2 3 5 4 6了。
5、执行--j，这时j的值是1，然后while循环判断list[0]是否大于r，也就是说1>2，条件不成立，退出循环，执行list[1]=r这句了。
6、当for循环后，int i=4时，判断i是否小于list的长度。这时将list[4]的值赋给r，接下来j的值为4，然后while循环判断list[3]是否大于r，也就是说是否5>4，条件成立，执行循环内部的运算，将list[4]与list[3]所对应的内存地址交换（记录后移），即排好顺的列表是1 2 3 4 5 6了。在这里基本上已排好顺序了。
7、执行--j，这时j的值是3，然后while循环判断list[2]是否大于r,也就是说3>4，条件不成立，退出循环，执行list[3]=r这句了。
8、当for循环后，int i=5时，判断i是否小于list的长度，这时将list[5]赋给r，接下来j的值为5，然后while循环判断list[4]是否大于r，也就是说是否4>5，条件不成立，退出循环，执行list[5]=r这句了。
9、最后当for再次循环，int i=6时已经超出范围了，因此整个for循环退出了。
P.S.如果分析的不对，或者觉得对我这种分析方法有什么问题或者建议的话，可以欢迎来讨论！
评论