排序大全

CompanyLOGO第9章排序《数据结构(C#语言描述)》配套PPT北京大学出版社制作：陈广博客：cgbluesky.blog.163.com《数据结构(C#语言描述)》配套PPT引入《数据结构(C#语言描述)》配套PPT•排序（Sorting）是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为按关键字“有序”的记录序列。如何进行排序，特别是高效率地进行排序是计算机工作者学习和研究的重要课题之一。本章主要介绍几类内部排序方法的基本思想、排序过程、算法实现。9.1排序的基本概念《数据结构(C#语言描述)》配套PPT内排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；外排序：若参加排序的记录数量很大，内存无法容纳全部资料，排序需要借助外部存储设备才能完成，则称此类排序为外部排序。9.2插入排序《数据结构(C#语言描述)》配套PPT插入排序（InsertionSort）的主要思想是不断地将待排序的元素插入到有序序列中，使有序序列不断扩大，直至所有元素都进入有序序列中。9.2插入排序《数据结构(C#语言描述)》配套PPT9.2.1直接插入排序36597182ijtemp4插入排序19.2插入排序《数据结构(C#语言描述)》配套PPT9.2.1直接插入排序36597182ijR[0]4改进后的插入排序29.2插入排序《数据结构(C#语言描述)》配套PPT9.2.2希尔排序•希尔排序（ShellSort）又称为缩小增量排序，是由D.L.Shell在1959年提出的，它是对直接插入排序的一种改进方法。直接插入排序法更适合数据量较少的排序，当待排序记录序列接近“正序”时，其时间复杂度也可提高至接近O(n)。希尔排序正是依据此，对直接插入排序进行改进。其基本思想是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这时再对所有记录实施直接插入排序。9.2插入排序《数据结构(C#语言描述)》配套PPT9.2.2希尔排序365971824ijd=4temp89.2插入排序《数据结构(C#语言描述)》配套PPT9.2.2希尔排序•希尔排序适用于待排序记录数目较大的情况，在此情况下，希尔排序一般要比直接插入排序快。1971年，斯坦福大学的詹姆斯.彼得森和戴维.L.拉塞尔在大量实验的基础上推导出，希尔排序的时间复杂度约为O(n1.3)。9.3交换排序《数据结构(C#语言描述)》配套PPT交换排序（ExchangeSort）的主要思路是在排序过程中，通过对待排序记录序列中元素进行比较，如果发现次序相反，就将存储位置交换来达到排序目的。本节主要介绍两种交换排序方法：冒泡排序和快速排序。9.3交换排序《数据结构(C#语言描述)》配套PPT9.3.1冒泡排序•冒泡排序（BubbleSort）是一种简单的交换排序方法。它的基本思想是对所有相邻记录进行比较，如果是逆序，则将其交换，最终达到有序。9.3交换排序《数据结构(C#语言描述)》配套PPT9.3.1冒泡排序108315261130ij9.3交换排序《数据结构(C#语言描述)》配套PPT9.3.1冒泡排序•冒泡排序法在运行时间方面，待排序记录越接近有序，算法的执行效率就越高，反之，执行效率就越低，它的平均时间复杂度为O(n2)。9.3交换排序《数据结构(C#语言描述)》配套PPT9.3.2快速排序•快速排序是由C.A.RHoarse提出并命名的一种排序方法，。在各种排序方法中，这种方法对元素之间比较次数较少。因而速度也比较快，被认为是目前最好的排序方法之一。在.NET的多个集合类所使用的Sort()方法正是使用快速排序法对集合中的元素进行排序的。9.3交换排序《数据结构(C#语言描述)》配套PPT9.3.2快速排序365971824ij3temp9.3交换排序《数据结构(C#语言描述)》配套PPT9.3.2快速排序•快速排序的平均时间复杂度为O(nlog2n)。就平均时间而言，快速排序是目前被认为最好的内部排序方法。但是，如果待排序记录的初始状态有序，快速排序蜕化为冒泡排序，其时间复杂度为O(n2)。也就是说，排序记录越乱，基准两侧记录数量越接近，排序速度越快；待排序记录越有序，排序速度越慢。为了避免一趟排序后的记录集中的基准的一侧，可以在快速排序前对序列进行“预处理”，将序列的第一个元素、中间元素和最后一个元素进行对比，取中间的值作为基准值。9.4选择排序《数据结构(C#语言描述)》配套PPT•选择排序（SelectionSort）是以选择为基础的一种常用排序方法，它的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的记录序列的最后，直到全部排列完为止。选择排序的方法有很多种，这里只介绍两种最有代表性的方法：直接选择排序和堆排序。9.4选择排序《数据结构(C#语言描述)》配套PPT9.4.1直接选择排序•直接选择排序的基本思想是：第一趟从所有的n个记录中选取最小的记录放在第一位，第二趟从n-1个记录中选取最小的记录放到第二位。以此类推，经过n-1趟排序后，整个序列就成为有序序列。9.4选择排序《数据结构(C#语言描述)》配套PPT9.4.1直接选择排序365971824ijk9.4选择排序《数据结构(C#语言描述)》配套PPT9.4.1直接选择排序•简单选择排序需要外循环n-1趟，在每一趟外循环之中又有一个内循环，内循环要做n-i次比较，由此简单选择排序的平均时间复杂度为O(n2)。9.4选择排序《数据结构(C#语言描述)》配套PPT9.4.2堆排序•堆排序（HeapSort）是由J.Williams在1964年提出的，它是在选择排序的基础上发展起来的，比选择排序的效率要高。9.4选择排序《数据结构(C#语言描述)》配套PPT9.4.2堆排序•堆：如果将堆看成是一棵完全二叉树，则这棵完全二叉树中的每个非叶子结点的值均不大于（或不小于）其左、右孩子结点的值。由此可知，若一棵完全二叉树是堆，则根结点一定是这棵树的所有结点的最小者或最大者。非叶子结点的值大于其左、右孩子结点值的堆被称为大根堆；非叶子结点的值小于其左、右孩子结点的值的堆被称为小根堆。48322619287(a)大根堆71820321526(b)小根堆211820323526(c)不是堆9.4选择排序《数据结构(C#语言描述)》配套PPT9.4.2堆排序•堆排序的时间，主要由建立初始堆和反复重建堆这两个部分的时间开销构成。堆排序的最坏时间复杂度为O(nlog2n)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。9.5归并排序《数据结构(C#语言描述)》配套PPT•归并排序（MergingSort）是利用“归并”技术来进行的排序，所谓归并是指将两个或两个以上的有序表合并成一个新的有序表。它的基本思想是：将这些有序的子序列进行合并，从而得到有序的序列。合并是一种常见运算，其方法为比较各子序列的第一个记录，将小者取出作为合并序列的第一个记录，如此继续比较，最终可以得到排序结果。因此，归并排序的基础是合并。9.5归并排序《数据结构(C#语言描述)》配套PPT9.5.1二路归并排序•利用二个有序序列的合并来实现归并排序被称为二路归并排序。二路归并排序的基本思想是：如果序列中有n个记录，可以先把它看成n个子序列（由于只包含一个记录，所以是排好序的）。将每相邻的两个子序列合并，得到n/2个有序子序列，每个子序列包含2个记录。继续将这些子序列合并，得到n/4个有序子序列。如此反复，直到最后合并成一个有序序列，排序完成。9.5归并排序《数据结构(C#语言描述)》配套PPT9.5.1二路归并排序5178326949.5归并排序《数据结构(C#语言描述)》配套PPT9.5.1二路归并排序•二路归并排序易于在链表上实现，它的时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)，但二路归并排序跟其他排序相比，需要更多的临时空间。9.6本章小结《数据结构(C#语言描述)》配套PPT本章介绍了多种排序方法，其中并无绝对好与不好的算法，每种排序方法都有其优缺点，适合于不同的环境。因此在实际应用中，应根据具体情况做出选择。下面提出几点建议供读者参考。•当待排序记录数n较小时（一般n≤50），可采用直接插入、直接选择排序或冒泡排序。若文件初始状态基本为正序，则应选用直接插入排序、冒泡排序。如果单条记录本身信息量较大，由于直接插入排序所需的记录移动操作较直接选择排序多，因此用直接选择排序较好。•当n较大时，则应采用时间复杂度为O(nlog2n)的排序方法，如快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中被认为是最好的方法。当待排序的关键字是随机分布时，快速排序的平均时间最短，C#集合类中内置的排序方法也是使用快速排序法实现的；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况；归并排序由于需要大量的辅助空间，所在并不值得提倡，但如果要将两个有序表组合成一个新的有序表，最好的方法是归并排序法。