各种排序算法分析

HuJunfengHuJunfeng排序算法及算法分析HuJunfengHuJunfeng2问题的提出：•为什么要排序？有序表的优点？缺点？–构造关系。•按照什么原则排序？–比较？•如何进行排序？HuJunfengHuJunfeng3基本概念•排序（Sorting）：简单地说，排序就是把一组记录按照某个（或某几个）字段的值以递增（由小到大）或递减（由大到小）的次序重新排列的过程。（如按年龄从小到大排序）学号姓名年龄性别2004001张佳18男2004002王鹏19男2004003刘宁17女2004004李娟18女2004005陈涛19男2004006李小燕18女HuJunfengHuJunfeng4•作为比较基础的一个(或多个)字段，称为排序码。排序码可以是数值、符号或符号串。•排序码不一定是关键码，关键码可以作为排序码。关键码是唯一的，但排序码不一定唯一。排序码不唯一时，排序的结果可能不唯一。•参与排序的对象，称为记录。一个记录可以包含多个字段。•如果记录集合中存在多个排序码相同的记录，经过排序后，排序码相同的记录的前后次序保持不变，则这种排序方法称为是稳定的，否则是不稳定的。排序码与关键码（primarykey）HuJunfengHuJunfeng5•排序方法可以分为五种∶插入排序、选择排序、交换排序、分配排序和归并排序。•在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。本章侧重讨论内排序的方法，但有些方法(特别是归并排序的思想)也可以用于外排序。排序的类型HuJunfengHuJunfeng6排序算法的评价•评价排序算法好坏的标准–执行算法所需的时间–执行算法所需要的附加空间–算法本身的复杂程度也是考虑的一个因素•排序的时间开销是算法好坏的最重要的标志•排序的时间开销衡量标准:–算法执行中的比较次数（必须）。–算法执行中的移动次数（有可能避免）。•通常会关注最坏情况和平均情况的开销。HuJunfengHuJunfeng7插入排序•基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。02111(,,...,|,,)kkknaaabbbx顺次选取一个元素插入到合适位置HuJunfengHuJunfeng8插入排序的细分类如何插入到已排好序的序列中？直接插入（从后向前找位置后插入）O(n2)二分法插入（按二分法找位置后插入）O(nlog2n)表插入排序（按链表查找位置后插入）O(n2)HuJunfengHuJunfeng9直接插入排序•基本思想：–假定前面m个元素已经排序；–取第(m+1)个元素，插入到前面的适当位置；–一直重复，到m=n为止。–（初始情况下，m=1）HuJunfengHuJunfeng10第一趟：{23}，[起始只有一个记录]{11,23}11第二趟：{11，23}，{11，23，55}55第三趟：{11，23，55}，{11，23，55，97}97第四趟：{11，23，55，97}，{11，19，23，55，97}19第五趟：{11，19，23，55，97}，{11，19，23，55，80，97}80示例：{23，11，55，97，19，80}HuJunfengHuJunfeng11直接插入排序的算法中记录的数据结构typedefintKeyType;typedefintDataType;typedefstruct{KeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其他字段*/}RecordNode;typedefstruct{intn;/*n为文件中的记录个数，nMAXNUM*/RecordNode*record;}SortObject;HuJunfengHuJunfeng12直接插入排序算法复杂度评价极端情况下：最小比较次数∶每个记录仅比较一次最大比较次数∶每个记录比较已排好序的记录长度nnC1min2)1(21211maxnnniCniHuJunfengHuJunfeng13直接插入排序算法评价2最小移动次数∶最大移动次数∶nnM1min112max2)1(niniMHuJunfengHuJunfeng14直接插入排序算法评价3初始数据状态相关：•文件初态不同时，直接插入排序所耗费的时间有很大差异。–若文件初态为正序，则算法的时间复杂度为O(n)–若初态为反序，则时间复杂度为O(n2)HuJunfengHuJunfeng15直接插入排序算法评价4——平均复杂度•插入记录Ri-1，有i种可能的插入位置，即插入到第0，1，…，i-1位置上，假设每种情况发生的概率是相等的，均为pj=1/i(j=0,1,…,i-1)•比较次数为Cj=j+1(j=0,…,i-2,i-2)，则插入记录Ri-1的平均比较次数为∶21)2*)1((1)1(1)1(1101010iiiijijiCPijijijjjHuJunfengHuJunfeng16直接插入排序算法评价5——平均复杂度•直接插入排序的总的比较次数为：)()4(4432)1(*2111212121222112nOnOnnnnnlnjnlnjHuJunfengHuJunfeng17直接插入排序算法评价•直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)•直接插入排序的平均时间复杂度为T(n)=O(n2)•算法中引入了一个附加的记录空间temp，因此辅助空间为S(n)=O(1)•直接插入排序是稳定的HuJunfengHuJunfeng18存储结构与算法优化•顺序存储结构：二分插入算法，减少比较次数。•链式存储结构：减少移动次数。HuJunfengHuJunfeng19二分法插入排序•特点：在直接插入排序的基础上减少比较的次数，即在插入Ri时改用二分法比较找插入位置，便得到二分法插入排序•限制：必须采用顺序存储方式。HuJunfengHuJunfeng20例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42lowmidhigh[1527365369]42lowhighmid[1527365369]42highlow[152736425369](highlow，查找结束，插入位置为low或high+1)(4236)(4253)HuJunfengHuJunfeng21二分法插入排序算法voidbinSort(SortObject*pvector){inti,j,left,mid,right;RecordNodetemp;for(i=1;ipvector-n;i++){temp=pvector-record[i];left=0;right=i–1;while(left=right){mid=(left+right)/2；if(temp.keyvector-record[mid].key)right=mid-1;elseleft=mid+1;}//whilefor(j=i-1;j=left;j--)pvector-record[j+1]=pvector-record[j];if(left!=i)pvector-record[left]=temp;}//for}//binSortHuJunfengHuJunfeng22二分插入排序比较次数•二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数，插入第i个记录时，如果，则无论排序码的大小，都恰好经过次比较才能确定插入位置，如果，则比较次数为j+1，因此，将n(n=2k)个记录排序的总比较次数为njij2log0(2ij2log122jjinnnnnkkkini2212log1log......2210logHuJunfengHuJunfeng23二分法插入排序方法性能分析•当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数•算法的移动次数与直接插入排序算法的相同–最坏的情况为n2/2–最好的情况为n–平均移动次数为O(n2)–二分法插入排序算法的平均时间复杂度为T(n)=O(n2)•二分插入排序法是稳定的排序算法,在检索时采用leftright结束，left、right的修改原则是：temp.keypvector-record[mid].key，保证排序是稳定的。HuJunfengHuJunfeng24结论•移动次数与直接插入排序相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)•二分法插入排序算法的平均时间复杂度为T(n)=O(n2)•二分法插入排序是稳定的HuJunfengHuJunfeng25表插入排序•表插入排序是在直接插入排序的基础上减少移动的次数。•基本思想:–在记录中设置一个指针字段，记录用链表连接–插入记录Ri时，记录R0至Ri-1已经排序，先将记录Ri脱链–再采用顺序比较的方法找到Ri应插入的位置，将Ri插入链表。HuJunfengHuJunfeng26structNode;/*单链表结点类型*/typedefstructNodeListNode;structNode{KeyTypekey;/*排序码字段*/DataTypeinfo;/*记录的其它字段*/ListNode*next;/*记录的指针字段*/};typedefListNode*LinkList;表插入算法中记录的数据结构HuJunfengHuJunfeng27表插入排序的算法性能分析第i趟排序：最多比较次数i次，最少比较次数1次。n-1趟总的比较次数：最多：最少：n-1记录移动次数：0时间效率：O(n2)辅助空间：O(n)[指针]稳定性：p-key=now-key保证稳定的排序。2)1(11nniniHuJunfengHuJunfeng28选择排序•思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。•关键问题：在剩余的待排序记录序列中找到最小关键码记录。•方法：–直接选择排序–堆排序。HuJunfengHuJunfeng29直接选择排序•方法是∶–首先在所有记录中选出排序码最小的记录，与第一个记录交换–然后在其余的记录中再选出排序码最小的记录与第二个记录交换–以此类推，直到所有记录排好序HuJunfengHuJunfeng30直接选择排序性能分析•选择排序的比较次数与记录的初始状态无关。•第i趟排序：从第i个记录开始，顺序比较选择最小关键码记录需要n-i次比较。•总的比较次数：•移动次数：Mmin=0(初始为正序时）•最多移动次数：Mmax=3(n-1)(初始为逆序时，每趟1次交换，3次移动完成）•时间复杂度：T(n)=O(n2)，•辅助空间1个记录单位：Temp，•稳定性：不稳定的排序。2)1()(11nninniHuJunfengHuJunfeng3131起泡排序•方法①先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，否则不交换②然后对新的第二个记录R1与第三个记录R2作同样的处理③依次类推，直到处理完第n-1个记录和第n个记录–从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡–经过这次起泡，n个记录中最大者被安置在第n个位置上HuJunfengHuJunfeng3232④此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上。⑤然后再对前n-2个记录重复上述过程……，这样最多做n-1次起泡就能完成排序•可以设置一个标志noswap表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成•起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后(下)向前(