算法设计与分析

实验名称：归并排序与快速排序平均时间之比较 （验证型实验）

实验目标：

（1） 通过实验比较归并排序与快速排序算法在平均情况下哪一个更快。

（2） 加深对时间复杂度概念的理解。

实验任务：

以C/C++语言编写归并排序算法6.3及快速排序算法6.6，并在SPLIT阶段采用三者的平均值选择中间作为划分元素。

（2）生成20组数据（例如 n =5000 i ，1≤ i ≤20）。所有数据均属于区间（0,105）内的整数。对于每一组数据，在快速排序和归并排序算法之间进行测试，并记录各自所需的时间（以毫秒为单位）。

（3）基于实验数据和结果进行比较分析，最终得出了快速排序与归 merge sort算法平均时间比较的结论。

实验设备及环境：

PC；C/C++等编程语言。

实验主要步骤：

(1) 明确实验目标和具体任务；

(2) 理解实验所涉及的两个分类算法；

(3) 编写程序实现两个分类算法；

(4) 设计实验数据并运行程序、记录运行的结果；

(5) 根据实验数据及其结果得出结论；

一、代码 ：

1. 快速排序

 int Split(int a[],int low,int high) {

    
     int i=low,temp;
    
     if(a[low]< a[(low+high)/2]