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