数据结构实验--各种排序算法的比较

《数据结构实验--各种排序算法的比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验题目：各种查找及排序算法比较实验内容：内部排序算法——插入排序（直接插入排序、折半插入排序）、交换排序（冒泡、快速排序）、选择排序（直接选择排序、堆排序）和归并排序（2-路归并排序）的具体实现。目的与要求：掌握各种内部排序算法的特点，并对一整型数组排序，比较不同算法的速度。实验算法：1）、数据结构描述：主函数中的a数组保存需要排序数组，将数组作为自变量输入到各种排序算法的函数中，各个函数返回值为排序之后的数组，在主函数中以一个循环体输出。2）、函数和算法描述：主函数main先用循环体保存数组a，然后输出菜单，通过switch语句调用

2、排序函数，将数组排序后输出。InsertSort为直接插入排序对应的函数，并附有插入元素到数组的功能，函数主体是从数组第二个元素开始与其前的元素一一比较大小，并且插入到合适位置使得该元素的大小位于相邻元素之间。BinsertSort为折半插入排序对应的函数，函数主体是在如上所述进行插入时，先比较待插入元素与其前的有序列的中心元素的大小关系，以此循环来判断插入位置。BubbleSort为冒泡排序对应的函数，为二重循环结构，外循环每循环一次，决定出待排序部分的最大值并置于待排部分的末端，内循环对相邻两个元素大小作比较，进行调换。Partit

3、ionQuickSort为快速排序对应的函数，建有两个指针，从待排部分两端进行扫描，一次循环之后，将极大值和极小值各置于一端。SelectMinKeySSSort为选择排序对应的函数，每循环一次，直接选出待排序部分中最小的元素并置于已排序部分之后，直至待排部分长度为0。MergeMSortMergeSort为归并排序对应的函数，先将数组元素每两个一组并在组内排序，再将每两组和为一组进行排序，依次循环，直至分组长度与数组长度相同。HeapAdjustHeapSort为堆排序对应的函数，通过循环，将数组调整为大顶堆形式，输出一次即可得到有序

4、序列。3）、时空分析：设数组元素数为N，分析各排序算法的平均时间复杂度：直接插入排序：O(N2)折半插入排序：O(N2)冒泡排序：O(N2)快速排序：O(Nlog(N))选择排序：O(N2)归并排序：O(Nlog(N))堆排序：O(Nlog(N))实验结果：由实验结果和分析，这里的七种算法相比较：在元素个数比较少时，堆排序的速度最慢，简单排序算法比较有优势。当元素个数增加，冒泡排序的耗时增加显著，高级排序算法（归并，堆，快速）有优势。当元素个数增加至非常大师，归并排序和快速排序较堆排序更快。源代码：#include#i

5、nclude#defineN20int*InsertSort(inta[],intp){inti,j;for(i=1;a[i]!=88;i++){}a[i]=p;a[i+1]=88;for(i=2;a[i]!=88;i++)if(a[i]

6、]!=88;i++){}a[i]=p;a[i+1]=88;for(i=2;a[i]!=88;++i){a[0]=a[i];l=1;h=i-1;while(l<=h){m=(l+h)/2;if(a[0]=h+1;--j)a[j+1]=a[j];a[h+1]=a[0];}returna;}int*BubbleSort(inta[]){inti,j,temp,l;for(i=1;a[i]!=88;i++){}l=i;i=0;for(j=1;a[j]!=88;j++){for

7、(i=0;ia[i+1]){temp=a[i];a[i]=a[i+1];a[i+1]=temp;}}returna;}intPartition(inta[],intlow,inthigh){intpivotkey;a[0]=a[low];pivotkey=a[low];while(low=pivotkey)--high;a[low]=a[high];while(low

8、a[low];}a[low]=a[0];returnlow;}int*QuickSort(inta[],intl,inth){intp;if(l