搜索
合并、快速排序一．实验目的：1.理解算法设计的基本步骤及各部的主要内容、基本要求；2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题；3.通过本次试验初步掌握将算法转化为计算机上机程序的方法。二．实验内容：1.设计和实现递归的合并排序算法、快速排序算法；2.设计和实现消除递归的合并排序算法、快速排序算法；3.设计有代表性的典型输入数据，分析算法的效率；4.对于给定的输入数据，给出算运行结果和运行结果，并给出实验结果分。三．实验操作：1.合并排序思想：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的思想，是一种稳定的排序方法。将以有序的子序列合并，得到完全有序的序列；及先使每个字序列有序，再使子序列段间有序。归并过程：比较数组中两个元素的大小，如比较a[i]和a[j]的大小，若a[i]=a[j]，将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表剩下的元素复制到r中从下标k到下标t的单元。如：6，202，100，301，38，8，1第一次归并：{6，202}，{100，301}，{8，38}，{1}第二次归并：{6，100，202，301}，{1，8，38}第三次归并：{1，6，8，38，100，202，301}合并排序算法：voidmerge(intArray[],intlow,inthigh){inti=low,j,k;intmid=(low+high)/2;j=mid+1;k=low;int*list=newint[high+1];while(i=mid&&j=high){if(Array[i]=Array[j])list[k++]=Array[i++];elselist[k++]=Array[j++];}while(i=mid)list[k++]=Array[i++];while(j=high)list[k++]=Array[j++];for(intn=low;n=high;n++)Array[n]=list[n];}voidmergeSort(intArray[],intlow,inthigh){if(lowhigh){intmid=(low+high)/2;mergeSort(Array,low,mid);mergeSort(Array,mid+1,high);merge(Array,low,high);}}2.快速排序思想：将要排序的数据存入数组中，首先任意去一个元素（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，值得注意的是，快速排序不是一种稳定的排序算法，即多个相同的值的相对位置也许会在算法结束时产生变动。快速排序的过程：1）设置两个变量i,j，排序开始的时候：i=0,j=N-1（N为元素个数）；2）以第一个数组元素作为关键数据，赋给key，即key=A[0]；3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将A[j]和A[i]互换；4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将A[i]和A[j]互换；5）重复第3、4步，直到i=j；如：下标012345原始数据627389第一次快排267389第二次快排237689第三次快排236789快速排序的算法：voidQsort(intList[],intlow,inthigh){if(low=high)return;intfirst=low;intlast=high;intkey=List[first];while(firstlast){while(firstlast&&List[last]=key)--last;List[first]=List[last];while(firstlast&&List[first]=key)++first;List[last]=List[first];}List[first]=key;Qsort(List,low,first-1);Qsort(List,last+1,high);}3.实验数据的输入：本实验采用将数据输入与输出存储到文件中的方式，需要采用C++文件流操作，对于数据的输入，由于cin对数据的读取会忽略空格和换行操作，使用cin流输入来控制数据的输入。对于输出操作，首先要从文件中读取数据，为了区别各数据，用逗号隔离，经过处理后将数据存入到另一文件之中。由于输入需要大量的数据，可采用从“随机数.txt”中读取数据。文件输入算法：intinput(){ofstreamoutFile;outFile.open(E://程序设计/practice1/算法设计与分析文本文件夹/number2.txt,ios::trunc);if(!outFile.is_open())coutFilecan'topen!endl;coutInputnumbers:endl;charnum;intlength=0;cin.get(num);while(num!='E'){length++;outFilenum;cin.get(num);}outFile.close();returnlength;}文件输出算法：voidoutput(intlength){doublestart,end;ifstreaminFile;ofstreamoutFile;inFile.open(E://程序设计/practice1/算法设计与分析/文本文件夹/number2.txt);outFile.open(E://程序设计/practice1/算法设计与分析/文本文件夹/result.txt,ios::trunc);char*Array=newchar[length];int*List=newint[length];int*Ray=newint[length];memset(List,0,length*sizeof(List));inti=0,j=0;outFile排序前的序列为：;while(!inFile.eof()){Array[i]=inFile.get();if(Array[i]!=''&&Array[i]!='\n'){if(Array[i]!=','){List[j]=List[j]*10+(Array[i]-'0');Ray[j]=List[j];}else{outFileList[j];j++;}}i++;}}4．程序运行时间的测量：为了了解两种算法时间运行效率，要对排序进行时间测量，调用time标准库。doublestart,end,time;start=clock();排序算法；end=clock();time=end-start;四．实验数据分析：本实验比较了快速排序和合并排序的时间效率，当输入的数据较少时，如文件中的2000个数据，快速排序输出的时间是0.0022s，而合并排序的输出时间是0.0023s，故在少量数据的情况下，两种排序的时间开销可以认为是一样的，当输入的数据较多时，归并排序的时间效率要高，在输入数据量为5000时，归并排序要快0.01s，所以并不能直接认为快速排序更快，而且快速排序有受到输入数据顺序的限制。五．实验感受;通过本次实验，了解到对于理解的东西并不能完全正确的写出程序，对于整数和逗号等字符一出现的情况可以利用字符处理的方式解决，但对于数字的统计需要细心，它还会影响到动态数组的开取问题，以及文件的导入流和导出流需要与普通数据输入有所区分。