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

实验题目：各种查找及排序算法比较

实验内容：

内部排序算法——插入排序（直接插入排序、折半插入排序）、交换排序

（冒泡、快速排序）、选择排序（直接选择排序、堆排序）和归并排序（2-路归并排序）的具体实现。 目的与要求：

掌握各种内部排序算法的特点，并对一整型数组排序，比较不同算法的速度。

实验算法：

1）、数据结构描述：

主函数中的a数组保存需要排序数组，将数组作为自变量输入到各种

排序算法的函数中，各个函数返回值为排序之后的数组，在主函数中以一个循环体输出。

2）、函数和算法描述：

主函数main先用循环体保存数组a，然后输出菜单，通过switch语

句调用排序函数，将数组排序后输出。

InsertSort为直接插入排序对应的函数，并附有插入元素到数组的

功能，函数主体是从数组第二个元素开始与其前的元素一一比较大小，并且插入到合适位置使得该元素的大小位于相邻元素之间。

BinsertSort为折半插入排序对应的函数，函数主体是在如上所述进

行插入时，先比较待插入元素与其前的有序列的中心元素的大小关系，以此循环来判断插入位置。

BubbleSort为冒泡排序对应的函数，为二重循环结构，外循环每循

环一次，决定出待排序部分的最大值并置于待排部分的末端，内循环对相邻两个元素大小作比较，进行调换。

Partition QuickSort为快速排序对应的函数，建有两个指针，从待排部分两端进行扫描，一次循环之后，将极大值和极小值各置于一端。 SelectMinKey SSSort为选择排序对应的函数，每循环一次，直接

选出待排序部分中最小的元素并置于已排序部分之后，直至待排部分长度为0。

Merge MSort MergeSort为归并排序对应的函数，先将数组元素每

两个一组并在组内排序，再将每两组和为一组进行排序，依次循环，直至分组长度与数组长度相同。

HeapAdjust HeapSort为堆排序对应的函数，通过循环，将数组调整为大顶堆形式，输出一次即可得到有序序列。 3）、时空分析：

设数组元素数为N，分析各排序算法的平均时间复杂度： 直接插入排序：O(N2) 折半插入排序：O(N2) 冒泡排序：O(N2)

快速排序：O(Nlog(N))

选择排序：O(N2)

归并排序：O(Nlog(N)) 堆排序： O(Nlog(N)) 实验结果：