《SORT解题报告PPT课件》由会员分享,可在线阅读,更多相关《SORT解题报告PPT课件(10页珍藏版)》请在金锄头文库上搜索。
1、SORTSORT解题报告解题报告10软(3)杨楠题目描述题目描述1.插入排序步骤3的总共移动次数2.冒泡排序步骤1的总共的交换次数3.快速排序所有执行步骤2中,比基准值小的个数总和4.归并排序中,所有的两两归并的两个序列中,第一序列的第一个元素比第二个序列的第一个元素大的次数题目分析题目分析做法:写出四种排序,在题目要求的地方计数。题目分析题目分析因为要进行四种排序,所以要保存原数组。题目分析题目分析快速排序第二个要求:2.重新排序数列,按顺序将所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partitio
2、n)操作。题目要求按照顺序将所有的元素进行一次分区操作,即分区后,比基准小的元素相对位置和比基准大的元素相对位置要和原来的一样。即52891,分区后只能是21589,而不能是12589或其他的。题目分析题目分析partition: for(i=left+1;i=right;+i)if(aik;-j)aj=aj-1;+k;这样partition时间复杂度就大于O(N),最坏会是O(N2),书中给出的方法是O(N)的。题目分析题目分析归并排序要按照题目给的例子用循环写。比如五个数12345循环的话第一次归并是12345,第二次归并是12345,第三次是12345而用递归的话,递归下去是分成12345,再分成12345,这样第一次归并变成了12345,第二次是12345,第三次是12345,这样答案会错掉。题目分析题目分析 for(k=1;kn;k*=2)for(i=0;i+kn;i+=2*k)Merge(a,b,i,i+k-1,Min(i+2*k-1,n-1);题目分析题目分析由于冒泡排序和插入排序每次交换都是交换相邻的两个,每交换一次即减少一对逆序数,所以两个排序的答案是一样的,只需用一个即可。THANKS!THANKS!