《836SORT解题报告》由会员分享，可在线阅读，更多相关《836SORT解题报告（10页珍藏版）》请在装配图网上搜索。
1、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=right;+i)if(a 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);由于冒泡排序和插入排序每次交换都是交换相邻的两个，每交换一次即减少一对逆序数，所以两个排序的答案是一样的，只需用一个即可。
836SORT解题报告
