首页 > 代码库 > 《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#数据结构和算法》-排序