一、【实验目的】
(1) 理解插入排序算法的实现过程；
（2）理解不同排序算法的时间复杂度及适用环境；
（3）了解算法性能测试的基本方法。
二、【实验内容】
1、以下是一个通过随机数来测试排序算法运行时间的程序，中间留出了加入排序算法的部分。其中可以通过修改RANDNUM的值来更改测试的数据量:
#include "stdio.h"
#include <stdlib.h>
#include <time.h>
#define RANDNUM 10000 //随机数的个数
void main（）
{
int iRandNum[RANDNUM];//存放随机数
clock_t first，second; //记录开始和结束时间（以毫秒为单位）
int i;
for（i=0;i<RANDNUM;i++）
{//产生1万个随机数
iRandNum[i]=rand（）%RANDNUM;
}
first=clock（）; //开始时间
//此处加入排序程序
second=clock（）;//结束时间
//显示排序算法所用的时间
}
2、从选择、交换、插入排序算法中任选至少3种排序算法（希尔排序、快速排序、堆排序三选二），在无序状态下进行多次运行，记录运行时间，并比较测试结果。
提示:在程序的实现过程中要用到以下函数，请大家在实验之前自学这几个函数的用法:
1）随机函数rand（）
- 时间函数clock（）
实验参考界面如下（此界面测试数据仅选用了两种算法，提交的报告以实验要求为准。）:
三、实验源代码
#include "stdio.h"
#include <iostream>
#include<cstring>
#include <stdlib.h>
#include <time.h>
using namespace std;
int N = 10000; //随机数的个数
//插入入排序
void insertSort(int arr[])
{
int n = N;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 将 key 插入到已排序的序列中
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
//希尔排序
void shellSort(int arr[]) {
int n = N;
int i, j, gap, temp;
for (gap = n / 2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
temp = arr[i];
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
//快速排序
void quickSort(int s[], int l, int r)
{
if (l < r)
{
//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
//堆排序
void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end) {
// 建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) {
// 若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else {
// 否則交換父子內容再繼續子節點和孫節點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heapSort(int arr[], int len) {
int i;
// 初始化，i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
//输出数组 a 的前20为元素，元素不足20个则输出全部
void print(int a[])
{
int n = N < 20 ? N : 20;
for(int i=0;i<n;i++)
cout << a[i] << " ";
cout << endl;
}
//产生随机数填充a数组
void init(int a[])
{
for(int i=0;i<N;i++)
a[i]=rand()%1000000;
}
double getQuickSortTime(int a[])
{
// cout << "排序前数组的前20位元素：\n";
// print(a);
clock_t first,second; //记录开始和结束时间(以毫秒为单位)
first=clock(); //开始时间
quickSort(a,0,N-1);
second=clock();//结束时间
// cout << "排序后数组的前20位元素：\n";
// print(a);
return (double)(second - first) / CLOCKS_PER_SEC;
}
double getShellSortTime(int a[])
{
clock_t first,second; //记录开始和结束时间(以毫秒为单位)
// cout << "排序前数组的前20位元素：\n";
// print(a);
first=clock(); //开始时间
shellSort(a);
second=clock();//结束时间
// cout << "排序后数组的前20位元素：\n";
// print(a);
return (double)(second - first) / CLOCKS_PER_SEC;
}
double getHeapSortTime(int a[])
{
clock_t first,second; //记录开始和结束时间(以毫秒为单位)
// cout << "排序前数组的前20位元素：\n";
// print(a);
first=clock(); //开始时间
heapSort(a,N);
second=clock();//结束时间
// cout << "排序后数组的前20位元素：\n";
// print(a);
return (double)(second - first) / CLOCKS_PER_SEC;
}
void testSort()
{
double quick = 0.0;
double shell = 0.0;
double heap = 0.0;
int cnt = 10;//测试次数
int a[N];//存放随机数
for(int i = 0; i < cnt; i++)
{
// if(i%5 == 0)
// N *= 10;
init(a);
int t[N];
memcpy(t,a,N);
quick += getQuickSortTime(t);
memcpy(t,a,N);
shell += getShellSortTime(t);
memcpy(t,a,N);
heap += getHeapSortTime(t);
}
// cout.precision(5);
cout.setf(ios::fixed);
cout << "基于"<< N <<"个元素的随机数组进行排序，测试"<<cnt<<"次取平均值的结果如下：\n";
cout << "快速排序：" << quick/cnt << "s\n";
cout << "希尔排序：" << shell/cnt << "s\n";
cout << " 堆排序 ：" << heap/cnt << "s\n";
}
int main()
{
testSort();
// cout << "排序前数组的前20位元素：\n";
// print(iN);
// heapSort(iN,N);
//显示排序算法所用的时间
// cout << "排序后数组的前20位元素：\n";
// cout <<"first: " << first << " second: " << second << endl;
// cout << "排序耗费的时间：";
// cout << (double)(second - first) / CLOCKS_PER_SEC << "s" << endl;
}
四、实验结果
基于10000个元素的随机数组进行排序，测试10次取平均值的结果如下：
快速排序：0.008402s
希尔排序：0.001554s
堆排序 ：0.001759s
五、实验总结
奇了怪了
