1、第十章第十章 排序排序什么是排序?n你熟悉排序吗？你过去曾经用过哪些排序方法？n你自己有没有编过排序的程序？是用的什么策略？：:准考证号准考证号 姓名姓名性别性别成绩成绩n从排序的本意而言，排序可以对单个关键字进行，也可以对多个关键字的组合进行，可统称排序时所依赖的准绳为“排序码排序码”。为讨论方便起，本章约定排序只对单个关键字进行 n排序结果可以是升序，也可以是降序，本章约定排序结果为记录按关键字非递减的顺序进行排列。n作为比较基础的一个(或多个)字段，称为排序码排序码。排序码可以是数值、符号或符号串。n排序码排序码不一定是关键字，是关键字，关键码可以作为排序码。关键码是唯一的，但排序码不一
2、定唯一。排序码不唯一时，排序的结果可能不唯一。n参与排序的对象，称为记录。一个记录可以包含多个字段。n如果记录集合中存在多个排序码排序码相同的记录，经过排序后，排序码排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定稳定的，否则是不稳定不稳定的。排序码排序码 与与 关键字（关键字（primary keyprimary key）n排序算法的稳定性排序算法的稳定性：如果待排序记录中存在多条关键字相同的记录，经过排序后，这些记录之间的相对次序不变，则称这种排序算法为“稳定的”；反之，称为“不稳定的”。n排序算法的评价标准排序算法的评价标准：算法的时间复杂度 执行算法所需的附加空间 算法本身
3、的复杂性 【例【例】n直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)n直接插入排序的平均时间复杂度为T(n)=O(n2)n算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)n直接插入排序是稳定的存储结构与算法优化n顺序存储结构：折半插入排序，二路插入算法，减少比较次数。n链式存储结构：减少移动次数。n当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数n算法的移动次数与直接插入排序算法的相同最坏的情况为n2/2最好的情况为0平均移动次数为O(n2)二分法插入排序算法的平均时间复杂度为T(n)=O(n2)n二分插入排序法是稳定的
4、排序算法。p在折半插入排序的基础上的进一步改进p目的：减少排序过程中移动记录的次数，需要n个记录的辅助空间p具体做法：设置一个辅助数组dn，第一个记录放在d1中，并把该数组看成是一个环形的，以d1为界，分别在两端进行插入排序。p优点：可以使记录移动次数减少一半表插入排序由于插入排序的基本作法是将待排记录逐个插入到一个有序的记录序列中，在顺序表中实现插入就不可避免要移动记录。因此若想减少排序过程中移动记录所花时间，只有采用链表作存储结构才行。但是排序的目的是为了使用以查找的记录序列是一个有序序列，以便可以进行折半查找，因此只能是在排序过程中将它视作链表，即在排序过程中以“修改指针”替代“移动记录
5、”实现“插入”，排序的结果仍使记录序列按关键字有序。此时的链表应该是静态链表而不是动态链表。n基本思想:在记录中设置一个指针字段，记录用链表连接插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链再采用顺序比较的方法找到Ri应插入的位置，将Ri插入链表。n表插入排序是在直接插入排序的基础上减少移动的次数。n以静态链表作为待排记录序列的存储结构。n算法：n为插入方便起见,设数组中0号单元为表头,其关键字值取最大整数(以便构成循环链表)n插入时将1号单元和表头构成一循环表n以后将2至n号单元按关键字非递减有序插入到循环链表中MAXINT 49 38 65 97 76 13 27 49 0
6、1 2 3 4 5 6 7 8i=1 1 0MAXINT 49 38 65 97 76 13 27 49 2 0 1i=2MAXINT 49 38 65 97 76 13 27 49 2 3 1 0i=3i=4MAXINT 49 38 65 97 76 13 27 49 2 3 1 4 0注：蓝色为插入关键字时需要修改的指针注：蓝色为插入关键字时需要修改的指针MAXINT 49 38 65 97 76 13 27 49 0 1 2 3 4 5 6 7 8i=5MAXINT 49 38 65 97 76 13 27 49i=6MAXINT 49 38 65 97 76 13 27 49i=7i=
7、8MAXINT 49 38 65 97 76 13 27 49 2 3 1 5 0 4 6 3 1 5 0 4 2 6 3 1 5 0 4 7 2 6 8 1 5 0 4 7 2 3插入时从插入时从0号单元开始顺指针逐个比较，当遇到大于待插入号单元开始顺指针逐个比较，当遇到大于待插入关键字关键字K的关键字的关键字N时，修改时，修改N前一个记录的指针为前一个记录的指针为K的位的位置，修改置，修改K的指针为的指针为N的位置的位置n表插入排序的基本操作是将一个记录插入到已排好序的有序表中，与直接插入排序相比，不同之处是总共修改2n次指针来代替移动记录，排序过程中所需关键字比较次数相同，时间复杂度是O
8、(n2)n表插入排序的结果存放在顺序存储结构中，但以链表形式存在，不能作如折半查找等随机查找，因此排序后还需对记录作重排。重排记录的方法：n从1开始按顺序扫描有序链表，将链表中第i个结点移动至数组的第i号位置上。（其中第一个节点由MAXINT指出）n在移动时采用互换的方法，即第i个结点（在第p号位置）与i号位置上的节点互换(因为按顺序从1开始所以pi)，为保证链表的连续性,交换后将i号节点的指针改为p，在扫描过程中凡是pkey key保证稳定的排序。2)1(11nnini)(21)(211nninni)(23)(321nninnin起泡排序最好时间复杂度是O(n)n起泡排序最坏时间复杂度为O(
9、n2)n起泡排序平均时间复杂度为O(n2)n起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)n起泡排序是稳定的思考试对(90,85,79,74,68,50,46)进行快速排序的划分，你是否发现什么特殊情况？由于每次枢轴记录的关键字都是大于其它所有记录的关键字，致使一次划分之后得到的子序列(1)的长度为0，这时已经退化成为没有改进措施的冒泡排序。由此你可以想像得到，快速排序不适于对原本有序或基本有序的记录序列进行排序。void SelectSort(ElemType R,int n)int i,j,pos;ElemType min;for(i=0;i n-1;i+)min=R
10、i;pos=i;for(j=i+1;j n;j+)if(Rj=1;i-)HeapAdjust(R,i,n);建堆 堆排序的时间主要耗费在建初始堆和调整建新堆时进行的堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复反复“筛选筛选”上上。堆排序在最坏情况下，其时间复杂度也为堆排序在最坏情况下，其时间复杂度也为O(nlogO(nlog2 2n)n)，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于都不会使堆排序处于 最好最好 或或 最坏最坏 的状态。的状态。另外，另外，堆排序仅需一个记录大小供交换用的辅助存储空间堆排序仅需一个记录大小供交换用的辅助存储空间。然而堆排序是一种然而堆排序是一种不稳定的排序不稳定的排序方法，它方法，它不适用于不适用于待排序待排序记录个记录个数数n n较少的情况较少的情况，但对于，但对于n n较大的文件还是很有效的。较大的文件还是很有效的。750500810993006326927808318458909243811065二趟收集：二趟收集：
