数据结构课程设计报告最新.docx

数据结构课程设计实验报尹浩宇一、 需求分析本课程设计需要实现的是对集中内部排序算法的时间复杂度、比较次数和交换次数进行分析。通过分析，选择了8种比较典型的内部排序算法作为目标算法进行测试，记录排序所花费的时间、交换比较次数，在画出相应的图标进行分析。二、 概要设计考虑到方便初始化等原因，将所有的排序算法看做继承同一基类的对象。采用c/c+语言进行该程序的设计。将所有的排序算法看作一个对象，从虚基类sort中继承方法和数据，统一使用sort指针进行测试。将所得结果以文本形式保存在文件中，之后使用excel等工具绘制相关的图形并进行分析。另外，测试数组的规模从10k随机增加到100k。三、 详细设计（其他排序算法的类类似，在此不一一赘述）四、 排序算法结果比较 测试的排序算法包括：直接插入排序(insert sort)、希尔排序(shell sort)、起泡排序(bubble sort)、快速排序(quick sort)、简单选择排序(selection sort)、堆排序(heap sort)和并归排序(merging sort)七种。直接插入排序（insert sort）即是将整个数组分为两个部分，一部分是已经有序的数组，剩余的是待排序的数组。对每一个在待排序数组中的元素，相当于在一个已排好序的数组a0n中插入一个数据e，使得a0.n+1仍然为一个有序的数组。待排序的数组长度为0的时候排序完成。算法如下：virtual void insert_sort(int *a,int len)int temp,j;for (int i = 0; i aj & j -1) aj + 1 = aj; j -= 1;aj + 1 = temp;/end for/end insert_sort()由分析，对于每一个在数组a的元素都需要在已排好序的数组中寻找其应该在的位置，最坏的情况即完全逆序下ai需要比较i 1次，总共需要比较的次数为1n-1i即n*(n-1)/2次，即是一个o(n2)的时间复杂度。但是在逆序的情况下该算法只需要简单遍历数组即可，即是一个o(n)的时间复杂度。对于随机的情况，更具概率相同的原理，其时间复杂度应仍然是o(n2)，但排序所需时间应该是完全逆序情况下的一半。以下是对算法运行时间、比较次数、交换次数的记录图表：其结果大致符合理论得出分析的结论。另外，该结果也反映出该算法不是一个稳定的排序算法。 希尔排序(shell sort)在直接插入排序中，不必要的交换过多，并且我们可以发现若待排序的数组已经基本有序，使用插入排序是很快的。希尔排序是利用上述规律对直接插入排序的一种改进，将规模较大数组分为规模小的部分排序，待数组基本有序之后进行直接插入排序。其算法如下：void shell_sort(int *a,int len)for(int div = len / 2;div = 1;div /= 2)/set div and reducefor(int i = div;i = 0;j -= div)/sort arr with few elemsif(aj aj - div)swap(aj,aj - div);通过查阅资料，希尔排序的复杂度应该为o(n32)。通过运行程序，获得其运行时间、比较次数、交换次数和数组规模关系如下：起泡排序(bubble sort)起泡排序基本思路是遍历未排序的数组，将相邻两个元素中较小的移向后方。多次遍历数组未排序部分后完成排序。其算法如下：void bubble_sort(int *a,int len)for (int i = 0; i len; +i)for (int j = 0; j len - i; +j)if(aj = high) return; int first = low; int last = high; int key = afirst; while(first last) while(first = key)-last; afirst = alast; while(first last & afirst = key)+first; alast = afirst; afirst = key; qsort(a, low, first-1); qsort(a, first+1, high);其测试结果如下图所示：简单选择排序(selection sort)简单选择排序通过遍历未排序数组，从中选出最小的元素并置于有序数组的第一个，其时间复杂度为o(n2)，而且这种排序算法是一种稳定的排序算法。算法实现如下：void selection_sort(int *a,int len)int min = 0;int i,j;for (i = 0; i len - 1; +i)min = i;for(j = i + 1;j aj) min = j;if(min != i)swap(amin,ai);i = 0;/ while(i len)coutai+= ai。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。从而完成排序。对于堆排序，他的平均时间复杂度为o(n*logn)。算法实现如下：void heapadjust(int array,int i,int nlength) int nchild; int ntemp; for(;2*i+1nlength;i=nchild) nchild=2*i+1; if(nchildarraynchild)+nchild; if(arrayi=0;-i) heapadjust(array,i,length); for(i=length-1;i0;-i) arrayi=array0arrayi; array0=array0arrayi; arrayi=array0arrayi; heapadjust(array,0,i); 其测试结果如下图所示：并归排序并归排序采用分治的思想，将无序的规模较大的数组分割为较小的数组进行排序，再将这些子序列合并为一个有序的序列，其时间复杂度为o(n*logn)。算法实现如下所示：void msort(int *a1,int *sorted,int start,int end)int m;if(start = end)sortedend = a1end;elsem = (start + end) / 2;msort(a1,sorted,start,m);msort(a1,sorted,m + 1,end);merge(a1,sorted,start,m,end);void sort_arr(int *a,int len)int sortedlen;msort(a,sorted,0,len - 1);测试结果如下图所示：总结根据排序是否使用分治思想将其分为两类，其中使用了并归方法的算法包括并归、快速和堆排序。剩下的选择、哈希、起泡和选择排序没有使用分治的办法（其实希尔排序在一定程度上也使用了并归的思想，但在此将其作为一种“改良版的冒泡排序”而归入该分组）。下文中将分别分析各组中的算法。先分析分治的三种算法。由于编译器函数栈的限制，快速排序调用函数过多无法正常运行，因此这里着重讨论堆排序和并归排序。很明显，对已随机生成的数组，快速排序的效果远远好于另外两个算法，但是显然付出的代价在于对于正序和逆序的数组，快速排序的表现是最差的。反观另外两个算法，对于三种不同的数组，其执行所需要的时间和比较、交换的次数都是相对稳定的（但由于几种算法的运行时间都比较短，误差在视觉上会比较直观）。而往往我们在实际处理问题的时候，针对逆序和顺序的数组的排序的情况是比较少遇到的，对随机数组排序的优秀性能使得快速排序在实际应用过程中较另外两种算法来说更为普遍。对于未使用分治的几种算法，在面对大规模随机数据时，排序效果最好的是希尔排序算法，当然选择排序算法和插入排序算法也有不错的表现。相反，冒泡排序算法所需要的时间就相当的长。我们可以得出冒泡排序不适合处理大规模数据这一结论。综合几种情况下的表现，从时间上考虑，我们可以发现使用了一定的并归思想的希尔排序比较适合应用在处理实际问题当中。五、 程序中遇到的问题及解决办法 快速排序对顺序或者逆序数组进行排序（规模大致在30k的时候）的时候由于子函数开辟得太多，导致函数堆栈长度超过c编译器中设置的长度，从而使得内存溢出。在此缩小快速排序的数组长度来解决该问题。六、附录附件一：程序源代码/该程序在64位win7下测试通过，编译器为gcc 4.8.1#include #include #include #include #include #include #include #include using namespace std;#define orgsize 10000#define max_len 100000#define init_size 200000#define delta 30000#define record_size 100#define file_width 32#define reduction 5#define path c:usersaldesktopdata_struct_project#define timecount(start,end) (end) - (start) * 1.0 / 1000#define shell_div_delta 8class recordpublic:record()record(string sn,string at,int s,double t,unsigned _int64 cc,unsigned _int64 ec)sort_name = sn;arr_type = at;size = s;time = t;compr_count = cc;exchange_count = ec;void set(string sn,string at,int s,double t,unsigned _int64 cc,unsigned _int64 ec)sort_name = sn;arr_type = at;size = s;time = t;compr_count = cc;exchange_count = ec;string getname()return sort_name;string gettype()return arr_type;int getsize()return size;double gettime()return time;int getcompr_count()return compr_count;int getexchange_coune()return exchange_count;void showdata()coutsetw(8)sort type : sort_nameendl;coutsetw(8)arr type : arr_typeendl;coutsetw(8)arr size : sizeendl;coutsetw(8)time : timeendl;coutsetw(8)exchang:exchange_countendl;coutsetw(8)compare:compr_countendl;private:string sort_name;string arr_type;int size;double time;unsigned _int64 compr_count;unsigned _int64 exchange_count;class sortpublic:sort()record_count = 0;compr_count = 0;exchange_count = 0;virtual void sort_arr(int*,int) = 0;virtual void show_info() = 0;virtual void savarec()ofstream os;os.open(path + name + .txt).c_str();ossort typesetw(file_width)arr typesetw(file_width)arr sizesetw(file_width)timesetw(file_width)exchangesetw(file_width)compareendl;for (int i = 0; i record_count; +i)osreci.getname()setw(file_width)reci.gettype()setw(file_width)reci.getsize()setw(file_width)reci.gettime()setw(file_width)reci.getexchange_coune()setw(file_width)reci.getcompr_count()endl;os.close();virtual string test() clock_t t1 ,t2;int size = orgsize;int test1 = 9,5;int test2 = 5,9;int arrinit_size = 0;/random arrwhile(size max_len)coutendl;srand(unsigned) time(null);coutbuilding random arr of size random elemsendl;for (int i = 0; i size; +i)arri = rand();coutbuild finishedendl;coutstart sortingendl;t1 = clock();sort_arr(arr,size);/ for (int i = 0; i size; +i)/ coutarriendl;/ t2 = clock();coutsort finishedendl;recrecord_count.set(name,random,size,timecount(t1,t2),compr_count,exchange_count);recrecord_count.showdata();record_count += 1;size += rand() % delta;coutendl;compr_count = 0;exchange_count = 0;/random arr/reverse arrsize = orgsize;while(size max_len)/ if(name = quick_sort)break;coutendl;/ srand(unsigned) time(null);coutbuilding random arr of size reverse elemsendl;for (int i = 0; i size; +i)arri = i;coutbuild finishedendl;coutstart sortingendl;t1 = clock();sort_arr(arr,size);t2 = clock();coutsort finishedendl;recrecord_count.set(name,reverse,size,timecount(t1,t2),compr_count,exchange_count);recrecord_count.showdata();record_count += 1;size += rand() % delta;coutendl;compr_count = 0;exchange_count = 0;/reverse arr/orderly arrsize = orgsize;while(size max_len)/ if(name = quick_sort)break;coutendl;/ srand(unsigned) time(null);coutbuilding random arr of size orderly elemsendl;for (int i = 0; i size; +i)arri = size - i;coutbuild finishedendl;coutstart sortingendl;t1 = clock();sort_arr(arr,size);t2 = clock();coutsort finishedendl;recrecord_count.set(name,orderly,size,timecount(t1,t2),compr_count,exchange_count);recrecord_count.showdata();record_count += 1;size += rand() % delta;coutendl;compr_count = 0;exchange_count = 0;/orderly arrcouttest finishedendl;for (int i = 0; i record_count; +i)reci.showdata();savarec();return ;protected:string name;string info;record recrecord_size;int record_count;unsigned _int64 exchange_count;unsigned _int64 compr_count;class insert_sort : public sortpublic:insert_sort()name = insert_sort;info = ;virtual void sort_arr(int *a,int len)int temp,j;for (int i = 0; i aj & j -1) aj + 1 = aj; j -= 1; exchange_count += 1; compr_count += 1;aj + 1 = temp;exchange_count += 1;virtual void show_info()/ virtual string test();class merging_sort : public sortpublic:merging_sort()name = merging_sort;virtual void show_info()void merge(int *a,int *s,int start,int mid,int end)int i = start,j = mid + 1,k = start;while(i != mid + 1 & j != end + 1)if(ai aj)sk+ = ai+;else sk+ = aj+;exchange_count += 1;compr_count += 1;while(i != mid + 1)sk+ = ai+;exchange_count += 1;while(j != end + 1)sk+ = aj+;exchange_count += 1;for (int i = start; i = end; +i)exchange_count += 1;ai = si;/must refresh original arrvoid msort(int *a1,int *sorted,int start,int end)int m;if(start = end)compr_count += 1;sortedend = a1end;elsem = (start + end) / 2;msort(a1,sorted,start,m);msort(a1,sorted,m + 1,end);merge(a1,sorted,start,m,end);void sort_arr(int *a,int len)int sortedlen;msort(a,sorted,0,len - 1);/ for (int i = 0; i len; +i)/ coutsortedi= 1;div /= shell_div_delta)for(int i = div;i = 0;j -= div)if(aj aj - div)swap(aj,aj - div);exchange_count += 1;compr_count += 1;/ for (int i = 0; i len; +i)/ coutaiendl;class bubble_sort : public sortpublic:bubble_sort()name = bubble_sort;virtual void show_info()void sort_arr(int *a,int len)for (int i = 0; i len; +i)for (int j = 0; j len - i; +j)if(aj aj + 1)exchange_count += 1;swap(aj,aj + 1);compr_count += 1;/ for (int i = 0; i len; +i)/ coutaiendl;class quick_sort : public sortpublic:quick_sort()name = quick_sort;virtual void show_info()void sort_arr(int *a,int len)/considered override but hoping unify the interfaceqsort(a, 0, len - 100);/*这里原文第三个参数要减1否则内存越界*/ / for(int i = 0; i len - 1; i+) / cout ai = high) return; int first = low; int last = high; int key = afirst; while(first last) while(first = key) -last; compr_count += 1; afirst = alast; exchange_count += 1; while(first last & afirst = key) +first; compr_count += 1; alast = afirst; exchange_count += 1; afirst = key; exchange_count += 1; qsort(a, low, first-1); qsort(a, first+1, high);virtual string test() clock_t t1 ,t2;int size = orgsize / reduction;int arrinit_size = 0;/random arrwhile(size max_len / reduction)coutendl;srand(unsigned) time(null);coutbuilding random arr of size random elemsendl;for (int i = 0; i size; +i)arri = rand() ;coutbuild finishedendl;coutstart sortingendl;t1 = clock();sort_arr(arr,size);t2 = clock();coutsort finishedendl;recrecord_count.set(name,random,size,timecount(t1,t2),compr_count,exchange_count);recrecord_count.showdata();record_count += 1;couttime :timecount(t1,t2) size :sizeendl;size += (rand() % delta) / reduction;coutendl;compr_count = 0;exchange_count = 0;/random arr/reverse arrsize = orgsize / reduction;while(size max_len / reduction)/ if(name = quick_sort)break;coutendl;srand(unsigned) time(null);coutbuilding random arr of size reverse elemsendl;for (int i = 0; i size; +i)arri = i;coutbuild finishedendl;coutstart sortingendl;t1 = clock();sort_arr(arr,size);t2 = clock();coutsort finishedendl;recrecord_count.set(name,reverse,size,timecount(t1,t2),compr_count,exchange_count);recrecord_count.showdata();record_count += 1;couttime :timecount(t1,t2) size :sizeendl;size += (rand() % delta) / reduction;coutendl;compr_count = 0;exchange_count = 0;/reverse arr/orderly arrsize = orgsize / reduction;while(size max_len / reduction)/ if(name = quick_sort)break;coutendl;srand(unsigned) time(null);coutbuilding random arr of size orderly elemsendl;for (int i = 0; i size; +i)arri = size - i;coutbuild finishedendl;coutstart sortingendl;t1 = clock();sort_arr(arr,size);t2 = clock();coutsort finishedendl;recrecord_count.set(name,orderly,size,timecount(t1,t2),compr_count,exchange_count);recrecord_count.showdata();record_count += 1;couttime :timecount(t1,t2) size :sizeendl;size += (rand() % delta) / reduction;coutendl;compr_count = 0;exchange_count = 0;/orderly arrcouttest finishedendl;for (int i = 0; i record_count; +i)reci.showdata();savarec();return ;class selection_sort : public sortpu