算法分析及设计实验报告

排序问题求解 实验日志

实验题目：

排序问题求解

实验目的：

1）以排序（分类）问题为例，掌握分治法的基本设计策略。 2）熟练掌握一般插入排序算法的实现； 3）熟练掌握快速排序算法的实现； 4) 理解常见的算法经验分析方法； 实验要求： 1. 生成实验数据.

要求：编写一个函数datagenetare，生成2000个在区间[1,10000]上的随机整数，并将这些数输出到外部文件data.txt中。这些数作为后面算法的实验数据。 2. 实现直接插入排序算法. 3. 实现快速排序算法. 实验主要步骤：

#include #include #include #include

#define RAND_MAX 10000 #define Max 1000

int I_Change_count = 0; //插入排序比较计数器 int I_Move_count = 0; //插入排序移动计数器 int S_Change_count =0; //选择排序比较计数器 int S_Move_count = 0; //选择排序移动计数器 int Q_Change_count = 0; //快速排序比较计数器 int Q_Move_count = 0; //快速排序移动计数器

void main() { long num; long Array[Max],Brray[Max],Crray[Max];//分别用来保存随机数 作为两个排序的对象 int A_Length; int Low = 0; int High; time_t t; void InsertSort(long Array[],int A_Length);

//void SelectSort(long Brray[],int A_Length); void QuickSort(long Crray[],int Low,int High); srand((unsigned) time(&t));/*用时间初始化随机函数*/ int T,i; printf(\输入你想要比较的数的个数，本算法是按照2的次方来计算的:\ scanf(\ A_Length = (int)pow(2.,T); if(A_Length > 1000) { exit(0); //如果比较次数大于100000，退出程序 } High = A_Length - 1; printf(\比较的个数为：%d\\n\ printf(\原序列=========================\\n\ for(i=0;i

列

度度

列

SelectSort(Brray,A_Length); for(int i=0;i

void InsertSort(long Array[],int A_Length) { int i,j; long signal;

for(i = 1;i < A_Length;i++) //依次插入Array[1]，…，Array[n-1]

if(Array[i]

signal = Array[i]; j=i-1; //signal是哨兵，且是Array[i]的副本 do{ //从右向左在有序区Array[1．．i-1]中查找Array[i]的插入位置

I_Change_count ++; //比较成功时直接执行 所以比较计数器放在此处 Array[j+1]=Array[j];//将关键字大于Array[i]的记录后移 I_Move_count ++; j--;

}while(signal < Array[j]);//当signal≥Array[j]时终止 I_Change_count ++;//比较失败时，循环跳出 比较计数器自加一次 Array[j+1]=signal; //Array[i]插入到正确的位置上 }//endif }