- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
1.插入排序
算法思想
插入排序使用了两层嵌套循环,逐个处理待排序的记录。每个记录与前面已经排好序的记录序列进行比较,并将其插入到合适的位置。假设数组长度为n,外层循环控制变量i由1至n-1依次递进,用于选择当前处理哪条记录;里层循环控制变量j,初始值为i,并由i至1递减,与上一记录进行对比,决定将该元素插入到哪一个位置。这里的关键思想是,当处理第i条记录时,前面i-1条记录已经是有序的了。需要注意的是,因为是将当前记录与相邻的上一记录相比较,所以循环控制变量的起始值为1(数组下标),如果为0的话,上一记录为-1,则数组越界。
现在我们考察一下第i条记录的处理情况:假设外层循环递进到第i条记录,设其关键码的值为X,那么此时有可能有两种情况:
如果上一记录比X大,那么就交换它们,直到上一记录的关键码比X小或者相等为止。
如果上一记录比X小或者相等,那么之前的所有记录一定是有序的,且都比X小,此时退出里层循环。外层循环向前递进,处理下一条记录。
算法实现(C#)
public class SortAlgorithm {??? // 插入排序??? public static void InsertSortT, C(T[] array, C comparer)??????? where C:IComparerT??? {?????????? ??????? for (int i = 1; i = array.Length - 1; i++) {??????????? //Console.Write({0}: , i);??????????? int j = i;??????????? while (j=1 comparer.Compare(array[j], array[j - 1]) 0) {??????????????? swap(ref array[j], ref array[j-1]);??????????????? j--;??????????? }??????????? //Console.WriteLine();??????????? //AlgorithmHelper.PrintArray(array);??????? }??? }??? // 交换数组array中第i个元素和第j个元素??? private static void swapT(ref T x,ref T y) {??????? // Console.Write({0}--{1} , x, y);??????? T temp = x;??????? x = y;??????? y = temp;??? }}
上面Console.WriteLine()方法和AlgorithmHelper.PrintArray()方法仅仅是出于测试方便,PrintArray()方法依次打印了数组的内容。swapT()方法则用于交换数组中的两条记录,也对交换数进行了打印(这里我注释掉了,但在测试时可以取消对它们的注释)。外层for循环控制变量i表示当前处理第i条记录。
public class AlgorithmHelper {??? // 打印数组内容??? public static void PrintArrayT(T[] array) {??????? Console.Write(?? Array:);??????? foreach (T item in array) {??????????? Console.Write( {0}, item);??? ??? }??????? Console.WriteLine();??? }}// 获得Comparer,进行比较public class ComparerFactory {??? public static IComparerint GetIntComparer() {??????? return new IntComparer();??? }??? public class IntComparer : IComparerint {??????? public int Compare(int x, int y) {??????????? return x.CompareTo(y);??????? }??? }}
上面这段代码我们创建了一个ComparerFactory类,它用于获得一个IntComparer对象,这个对象实现了IComparerT接口,规定了两个int类型的关键码之间比较大小的规则。如果你有自定义的类型,比如叫MyType,只需要在ComparerFactory中再添加一个类,比如叫MyTypeCo
文档评论(0)