用C语言产生一组随机数,并用这组数来比较各种排序方法的效率（答得好给100+的分）

Question

每次进入程序生成100个随机数，采用顺序存储结构。
比较插入排序，折半排序，冒泡排序和快速排序4种排序。采用随机生成的数据，登记并比较各个排序方法的比较次数和交换次数，验证各个排序方法效率的理论分析的结果。
经过大量的统计计算，给出各种排序方法的平均效率的比较。
把统计结果与理论分析结论进行对照。

Answer 1

终于写完了...累死了,不过我得说一句,你这个分太少,一般不会有人像我这么无聊的..呵呵

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Recordtype int
void copy(Recordtype s[], Recordtype d[], int n);
/************************************************************************/
/* 直接插入法 */
/************************************************************************/
int cmpTforIs = 0;//记录插入法的比较次数
int ChgTforIs = 0;//记录插入法的交换次数
void InsertSort(Recordtype data[], int n);

/************************************************************************/
/* 折半插入法 */
/************************************************************************/
int cmpTforBinarys = 0;//记录冒泡的比较次数
int ChgTforBinarys = 0;//记录冒泡的交换次数
void BinarySearchInsertion(int numbers[], const int n);
/************************************************************************/
/* 冒泡法 */
/************************************************************************/
int cmpTforBs = 0;//记录冒泡的比较次数
int ChgTforBs = 0;//记录冒泡的交换次数
void Bubsort(Recordtype *start, Recordtype *end);
/************************************************************************/
/* 快排 */
/************************************************************************/
int cmpTforQs = 0;//记录快排的比较次数
int ChgTforQs = 0;//记录快排的交换次数
int quickPass(int start, int last, Recordtype record[]);
int quickSort(int start, int last, Recordtype record[]);
int main()
{
Recordtype Data[100];
Recordtype D[100];
srand(time(NULL));
printf("the rand 100 numbers are:\n");
for (int i=0; i<100; i++)
{
D[i] = rand()%1000;//便于观察,每次产生1000内的整数
printf("%d ", D[i]);
}
printf("\n\n\n");

copy(D, Data, 100);
BinarySearchInsertion(Data, 100);
printf("折半插入法的比较次数为%d,交换次数为%d\n", cmpTforBinarys, ChgTforBinarys);

copy(D, Data, 100);
InsertSort(Data, 100);
printf("直接插入法的比较次数为%d,交换次数为%d\n", cmpTforIs, ChgTforIs);

copy(D, Data, 100);
Bubsort(&Data[0], &Data[99]);
printf("冒泡法的比较次数为%d,交换次数为%d\n", cmpTforBs, ChgTforBs);

copy(D, Data, 100);
quickSort(0, 99, Data);
printf("快排的比较次数为%d,交换次数为%d\n", cmpTforQs, ChgTforQs);

printf("排序后的序列为\n");//你可以这块放在任意排序完毕的语句后面,检查排序的正确性
for (i=0; i<100; i++)
{
printf("%d ", Data[i]);
}
return 0;
}
void copy(Recordtype s[], Recordtype d[], int n)
{
for (int i = 0; i<n; i++)
{
d[i] = s[i];
}
}

void BinarySearchInsertion(int numbers[], const int n)
{
int middle=0;
for(int i = 1; i < n; i++)
{
int low = 0 ;
int high = i-1 ;
int temp = numbers[i] ;
while(low <= high)
{
cmpTforBinarys++;
middle = (low + high) / 2 ;
if(temp < numbers[middle])
{
high = middle - 1 ;
}
else
low = middle + 1 ;
}
for(int k = i ; k >middle; k--) //K>middle不能错
{
ChgTforBinarys++;
numbers[k] = numbers[k-1 ] ;
}
ChgTforBinarys++;
numbers[low] = temp ; //此处用 numbers[high+1] = temp ;也可
} //赋值语句不能弄错numbers[low]=
}

void InsertSort(Recordtype data[], int n)
{
for (int i = 1; i< n; i++)
{
int temp = data[i];
for(int j = i; j>0 && temp<data[j-1]; --j)
{
ChgTforIs++;
cmpTforIs++;
data[j] = data[j-1];
}
data[j] =temp;
}
}

void Bubsort(Recordtype *start, Recordtype *end)
{
int num = end - start + 1;
Recordtype temp;
int i, j;
Recordtype *a = start;
for (i = 0; i<num; i++)
{
for (j = 0; j<num-i; j++)
{
cmpTforBs++;
if (*(a+j-1) > *(a+j))
{
ChgTforBs++;
temp = *(a+j-1);
*(a+j-1) = *(a+j);
*(a+j) = temp;
}
}
}
}

int quickPass(int start, int last, Recordtype record[])
{
int s = start, l = last;
int temp = record[s];
while (s < l)
{
while (s<l && temp <= record[l] )
{
l--;
cmpTforQs++;
}

if (s<l)
{
record[s++] = record[l];
ChgTforQs++;
}

while (s<l && temp >= record[s])
{
s++;
cmpTforQs++;
}
if (s<l)
{
record[l--] = record[s];
ChgTforQs++;
}
}
record[s] = temp;
ChgTforQs++;
return s;
}
int quickSort(int start, int last, Recordtype record[])
{
int pos = 0;
if (start < last)
{
pos = quickPass(start, last, record);
quickSort(start, pos-1, record);
quickSort(pos+1, last, record);
}
return 0;
}

Answer 2

100就算写论文这个也没意思，写些10000000个数据的排序才是。统计次数完全是个累赘。
我试了10000000个数据的，插入排法最慢 = 45倍*qsort的时间，qsort =3.2倍堆排的时间。
看来大堆还是堆排快。