南京邮电大学算法实验报告 - 图文(2)

void SortableList::Merge(int left,int mid,int right)//将两个有序子序列合并 { int *temp=new int[right-left+1]; } 排序结果： int i=left,j=mid+1,k=0; while ((i<=mid)&&(j<=right)) if(l[i]<=l[j])temp[k++]=l[i++]; else temp[k++]=l[j++]; while(i<=mid)temp[k++]=l[i++]; while(j<=right)temp[k++]=l[j++]; for(i=0,k=left;k<=right;)l[k++]=temp[i++]; 2.快速排序： 5

int SortableList::Partition(int left,int right)//分化函数 { int i=left,j=right+1;//以主元l[left]为中心分成左右子序列 do{ do i++; while (l[i]l[left]); if (i

} } 排序结果： 思考： 1、 在上述快速排序算法的执行过程中，跟踪程序的执行会发现，若初始输入序列递减有序，则调用 Partition 函数进行分划操作时，下标 i 向右寻找大于等于基准元素的过程中会产生下标越界，为什么？如何修改程序，可以避免这种情况的发生？ 这是因为原有的程序在序列最右边未设置一个极大值作为哨兵，则下标 i 在向右寻找大于等于基准元素的过程中，一直没有满足条件的元素值出现，就一直不会停止，直至越界。所以只要在序列的最后预留一个哨兵元素，将它的值设为极大值∞就可以解决： const int INF=2147483647; //定义一个极大值∞ l=new int[maxSize+1]; //预留最后一个哨兵的位置 7

void SortableList::Input() { for (int i=0;i>l[i];n++;} l[n]=INF; //最后一个元素为哨兵∞ } 2、 分析这两种排序算法在最好、最坏和平均情况下的时间复杂度。 两路合并排序：最好、最坏、平均情况下的时间复杂度均为 O(nlogn)。 快速排序：最好、平均情况下的时间复杂度为 O(nlogn)，最坏情况下为 O(n2)。 3、 当初始序列是递增或递减次序排列时， 通过改进主元（基准元素） 的选择方法， 可以提高快速排序算法运行的效率， 避免最坏情况的发生。 有三种主元选择方式。一是取 K(left+right)/2 为主元；二是取 left~right 之间的随机整数 j，以 Kj 作为主元；三是取 Kleft、 K(left+right)/2 和 Kright 三者的中间值为主元。试选择其中的一种，在原程序的基础上修改实现。下面给出第二种主元选择方式的具体 实现： 随机数的产生是由 srand 函数以 time 函数值（即当前时间）作为种子， rand 函数产生一个 0-RAND_MAX 范围内的随机数。 因此文件的开头应包含两个头文件 time.h 和 stdlib.h。为了不改动原有程序的基本结构，在原有程序上增加一个 RandomizedPartition 函数。 由 QuickSort 先调用该函数， 产生一个 left~right 范围内的随机下标 i，8

将该下标处的元素 Kj 和原有的主元 Kleft 交换，然后照常调用原有的 Partition 函数即可。 void SortableList::QuickSort(int left,int right) { if (left

四、实验小结（包括问题和解决方法、心得体会等） 通过对分治法的具体应用，在具体的算法和时间复杂度的对比下，更深层的理解分治法的策略，划小组合取有序，将复杂的问题分解成若干个小问题求解，虽然有具体的算法指导，但是在理解上自己还是应该多去琢磨一下。 五、指导教师评语 成 绩 批阅人 日 期 10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库南京邮电大学算法实验报告 - 图文(2)在线全文阅读。