首页 > 代码库 > 《C#数据结构和算法》-排序
《C#数据结构和算法》-排序
7.7 各种排序方法的比较与讨论 排序在计算机程序设计中非常重要,上面介绍的各种排序方法各有优缺点, 适用的场合也各不相同。在选择排序方法时应考虑的因素有: ( 1)待排序记录的数目 n 的大小; ( 2)记录本身除关键码外的其它信息量的大小; ( 3)关键码的情况; ( 4)对排序稳定性的要求; ( 5)语言工具的条件,辅助空间的大小等。综合考虑以上因素,可以得出如下结论: ( 1)若排序记录的数目 n 较小(如 n≤50)时,可采用直接插入排序或简 单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当 记录本身信息量较大时,用简单选择排序比较好。 ( 2)若记录的初始状态已经按关键码基本有序,可采用直接插入排序或冒 泡排序。 ( 3)若排序记录的数目n较大,则可采用时间复杂度为O(nlog2n)的排序 方法(如快速排序、堆排序或归并排序等)。快速排序的平均性能最好,在待排 序序列已经按关键码随机分布时,快速排序最适合。快速排序在最坏情况下的时 间复杂度是O(n2),而堆排序在最坏情况下的时间复杂度不会发生变化,并且所 需的辅助空间少于快速排序。但这两种排序方法都是不稳定的排序,若需要稳定 的排序方法,则可采用归并排序。 (4)基数排序可在 O(d×n)(d 为关键码的个数,当 n 远远大于 d 时)时 间内完成对 n 个记录的排序,但基数排序只适合于字符串和整数这种有明显结构 特征的关键码。当 n 很大、d 较小时,可采用基数排序。 (5)前面讨论的排序算法,除基数排序外,其它排序算法都是采用顺序存 储结构。在待排序的记录非常多时,为避免花大量的时间进行记录的移动,可以 采用链式存储结构。直接插入排序和归并排序都可以非常容易地在链表上实现, 但快速排序和堆排序却很难在链表上实现。此时,可以提取关键码建立索引表, 然后对索引表进行排序。也可以引入一个整形数组 t[n]作为辅助表,排序前令 t[i]=i,1≤i≤n。若排序算法中要求交换记录 R[i]和 R[j],则只须交换 t[i] 和 t[j]即可。排序结束后,数组 t[n]就存放了记录之间的顺序关系。7.8 C#中排序方法 C#语言中的许多类都提供了排序的成员方法。比如,在第四章介绍的数组 类 Array 就提供了排序方法 Sort。 Array 类中的排序方法采用的是快速排序算法, 并且要求数组中的数据元素必须实现 IComparable 接口,这样数据元素之间才能 进行比较。实际上,任何类型的数据都是使用比较器进行排序,所以,该类型要 实现排序方法,都必须实现 IComparable 接口。泛型类实现了泛型 IComparable 接口,非泛型类实现非泛型 IComparable 接口。 C#中提供了 Comparer 类来实现 各种比较器。 又比如,泛型 List 类也实现了 Sort 方法。 Sort 方法使用 Comparer 类的比较 器来决定 List<T>类中数据元素的顺序。比较器首先检查 List<T>类中数据元素是 否实现了泛型 IComparable 接口,如果实现了比较器就使用该实现,否则,比较 器再检查数据元素是否实现了非泛型 IComparable 接口,如果实现了就使用该实 现。如果这两种接口都没有实现,比较器将抛出一个 InvalidOperationException 异常 法使用了数组类 Array 的 Sort 方法。 同样,ASP.NET 2.0 中的GridView控件也实现了Sort方法。GridView控件的 类似于DataGrid控件,但比DataGrid控件更吸引人,使用更方便,程序员写 的代码也更少。Sort方法使用排序表达式和排序方向对GridVie控件进行排序。 排序表达式用于决定要排序的列,它可以对多列进行排序。排序方向决定是升序 还是降序排序。 7.7 各种排序方法的比较与讨论 排序在计算机程序设计中非常重要,上面介绍的各种排序方法各有优缺点, 适用的场合也各不相同。在选择排序方法时应考虑的因素有: ( 1)待排序记录的数目 n 的大小; ( 2)记录本身除关键码外的其它信息量的大小; ( 3)关键码的情况; ( 4)对排序稳定性的要求; ( 5)语言工具的条件,辅助空间的大小等。 综合考虑以上因素,可以得出如下结论: ( 1)若排序记录的数目 n 较小(如 n≤50)时,可采用直接插入排序或简 单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当 记录本身信息量较大时,用简单选择排序比较好。 ( 2)若记录的初始状态已经按关键码基本有序,可采用直接插入排序或冒 泡排序。 ( 3)若排序记录的数目n较大,则可采用时间复杂度为O(nlog2n)的排序 方法(如快速排序、堆排序或归并排序等)。快速排序的平均性能最好,在待排 序序列已经按关键码随机分布时,快速排序最适合。快速排序在最坏情况下的时 间复杂度是O(n2),而堆排序在最坏情况下的时间复杂度不会发生变化,并且所 需的辅助空间少于快速排序。但这两种排序方法都是不稳定的排序,若需要稳定 的排序方法,则可采用归并排序。 (4)基数排序可在 O(d×n)(d 为关键码的个数,当 n 远远大于 d 时)时 间内完成对 n 个记录的排序,但基数排序只适合于字符串和整数这种有明显结构 特征的关键码。当 n 很大、d 较小时,可采用基数排序。 (5)前面讨论的排序算法,除基数排序外,其它排序算法都是采用顺序存 储结构。在待排序的记录非常多时,为避免花大量的时间进行记录的移动,可以 采用链式存储结构。直接插入排序和归并排序都可以非常容易地在链表上实现, 但快速排序和堆排序却很难在链表上实现。此时,可以提取关键码建立索引表, 然后对索引表进行排序。也可以引入一个整形数组 t[n]作为辅助表,排序前令 t[i]=i,1≤i≤n。若排序算法中要求交换记录 R[i]和 R[j],则只须交换 t[i] 和 t[j]即可。排序结束后,数组 t[n]就存放了记录之间的顺序关系。
《C#数据结构和算法》-排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。