数据结构课件10数据结构课件排序幻灯片.ppt

* 链式基数排序算法的实现： 算法10.15 算法10.16 算法10.17 算法的性能分析： （1）空间：需辅助空间为2rd个队列指针； （3）时间：基本操作：指针的修改 时间复杂度：O(d(n+rd)) * 各种内部排序方法的比较和讨论： 排序方法 平均时间 最坏情况 辅助存储 简单排序 快速排序 堆排序 归并排序 基数排序 O(n*n) O(nlogn) O(nlogn) O(nlogn) O(d(n+rd)) O(n*n) O(n*n) O(nlogn) O(nlogn) O(d(n+rd)) O(1) O(logn) O(1) O(n) O(rd) * 《数据结构》综述： 一、学习数据结构的意义 设想一下，你决定向一个公司投资，而你对某个公司的了解只限于该公司的一条生产线每分钟可生产2000件产品，你会作出投资的决定吗？如果你是一个公司的管理者，这个公司日常的每笔交易的详细情况对你来讲的确重要，但如果你把时间花在这些数据上面，你就无法站在宏观的高度上把握公司的经营方向。 不管是经营一个公司，还是管理一个国家，对描述事物特征的数据必须加以分析与加工，现实事物是普遍联系的，描述这些事物属性及特征的数据之间也是普遍联系的，把这些数据之间的关系进行总结，得到集合、线性、树、图这四种基本关系，由此得到四类基本数据结构。而每种结构类型的数据，相同的操作（如遍历、查找等）需要采用不同的方法（算法），不同结构类型可进行的操作也有区别。通过应用这些算法，可得到事物的总体抽象特征。如：一个公司的年产值，年利润总额，利润率等。 * 反过来，为了描述一个复杂的事物，必须分析它的组成部分，既要描述每个部分的特征，又要描述各个部分之间的关系，如此细分下去，便于最终用计算机进行处理，而计算机的基本数据类型不适合描述复杂的结构，且仅用基本数据类型也不便于人的理解与记忆，所以使用介于两者之间的抽象数据类型成了计算机语言描述现实事物的纽带。人可以方便的把事物用抽象数据类型描述，也可以方便的把抽象数据类型用基本数据类型来实现，为用计算机处理现实问题提供了解决方法。 二、数据结构的学习重点 如何描述一种新的抽象数据类型？ 如何分析算法的优劣？ 线性表的主要特征； 线性表的存储表示(顺序表示、单向链表、循环链表、双向链表） * 特殊的线性表：栈、队列、串; 二叉树的定义、性质、存储结构、遍历算法; 图的定义、术语、存储结构; 静态查找表、二叉排序树、哈希函数的构造及冲突处理方法; 插入排序、快速排序、选择排序、归并排序、基数排序 * 第十章作业: 1.有一组待排序的记录的关键字初始排列如下: (32,54,12,24,32`,47) (1)请用直接插入排序算法对其进行排序.(画出每趟排序示图) (2)请用希尔排序算法对其进行排序.(画出每趟排序示图,d=2,1) (3)请用快速排序算法对其进行排序.(画出每趟排序示图) (4)请用树型选择排序算法对其进行排序.(画出排序示图) (5)请用堆排序算法对其进行排序.(画出排序示图) (6)请用归并排序算法对其进行排序.(画出排序示图) (7)请用链式基数排序算法对其进行排序.(画出排序示图) 2.上机题：编写快速排序算法的程序，每趟排序的枢轴依 “三者取中”法来选取。 测试数据：{49,38,65,97，76，13，27，49`} * 整个快速排序过程: [初始关键字] 49 38 65 97 76 13 27 49` 第一趟快速排序： {27 38 13 } 49 {76 97 65 49`} 第二趟快速排序： {13 } 27 {38} {49` 65} 76 {97} 结束 结束 第三趟快速排序： 49` {65} 结束 结束 有序序列： 13 27 38 49 49` 65 76 97 第四趟快速排序： * 快速排序算法的性能分析： （1）空间：需一个栈空间来实现递归。 （3）时间：基本运算：比较关键字和移动记录操作 平均时间复杂度：Tavg(n)= 快速排序算法的改进：三者取中法 若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，时间复杂度为O（n*n)。 用“三者取中”的法则来选取枢轴，即比较L.r[s].key、L.