C语言课程设计：shell排序、堆排序、快速排序、归并(递归和非递归)排序5种算法效率分析！求能运行的源码！

Question

1.随机生成1000个整数序列（0-20000范围内）采，用shell排序、堆排序、快速排序、归并(递归和非递归)排序5种算法，输出各种算法运算时间。
2.在最好、最坏情况下（正序0-999，逆序999-0），用上述5种算法排序，实测运算时间。
不要图形界面。。只要求输出5种排序运行的时间。。
只要符合要求的第一个回答追加100分！

Answer 1

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <Windows.h>
void shellSort(int *a,int len)
{
int step;
int i,j;
int temp;
for(step=len/2; step>0;step/=2)
{
for(i=step;i<len;i++)
{
temp = a[i];
for(j=i-step;(j>=0 && temp < a[j]);j-=step)
{
a[j+step] = a[j];
}
a[j+step] = temp;
}
}
}

void swap(int *a,int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void heapify(int *a,int n,int k)
{
int l,r,lg = -1;

l = 2*k;
r = l+1;

if (l <= n && a[l-1] > a[k-1])
{
lg = l;
}
else
{
lg = k;
}

if (r <= n && a[r-1] > a[lg-1])
{
lg = r;
}

if (lg != k)
{
swap(&a[lg-1],&a[k-1]);
heapify(a,n,lg);
}
}

void build_heap(int a[],int n)
{
for (int i=n/2+1; i>0; i--)
{
heapify(a,n,i);
}
}

void heap_sort(int a[],int n)
{
build_heap(a,n);

for (int i=n; i>0; i--)
{
swap(&a[0],&a[i-1]);
heapify(a,i-1,1);
}
}

int partitions(int a[],long p,long q)
{
long i,j=p-1;

for (i=p; i<q; i++)
{
if (a[i-1] <= a[q-1])
{
j++;
swap(&a[i-1],&a[j-1]);
}
}

j++;
swap(&a[j-1],&a[q-1]);

return j;
}

void quicksort(int a[],long p,long q)
{
long i;

if (p<q)
{
i = partitions(a,p,q);
quicksort(a,p,i-1);
quicksort(a,i+1,q);
}
}

void merge(int *a,int start, int mid, int end)
{
int n1 = mid - start + 1;
int n2 = end - mid;
int *left = (int *)malloc(sizeof(int)*n1), *right=(int *)malloc(sizeof(int)*n2);
int i, j, k;

for (i = 0; i < n1; i++) /* left holds a[start..mid] */
left[i] = a[start+i];
for (j = 0; j < n2; j++) /* right holds a[mid+1..end] */
right[j] = a[mid+1+j];

i = j = 0;
k = start;
while (i < n1 && j < n2)
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];

while (i < n1) /* left[] is not exhausted */
a[k++] = left[i++];
while (j < n2) /* right[] is not exhausted */
a[k++] = right[j++];
free(left);
free(right);
}

void MergeSort(int *a,int start, int end)
{
int mid;
if (start < end)
{
mid = (start + end) / 2;

MergeSort(a,start, mid);
MergeSort(a,mid+1, end);
merge(a,start, mid, end);
}
}
double gettime(LARGE_INTEGER t,LARGE_INTEGER t1,LARGE_INTEGER t2)
{
double time;
if (t.LowPart==0 && t.HighPart==0)
time = -1;
else
{
time = (float)(t2.LowPart - t1.LowPart);
if (time < 0) time += 2^32;
time /= (t.LowPart+t.HighPart * 2^32);
}
return time;
}
int main()
{
const int NUM = 1000;
srand(time(NULL));
int data[NUM];
int i;
for (i=0; i<NUM; ++i)
{
data[i] = rand()/(RAND_MAX/20000+1);
}

LARGE_INTEGER t,t1,t2;
QueryPerformanceFrequency(&t);

QueryPerformanceFrequency(&t1);
shellSort(data,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%0.4f\n",gettime(t,t1,t2));

QueryPerformanceFrequency(&t1);
heap_sort(data,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%0.4f\n",gettime(t,t1,t2));

QueryPerformanceFrequency(&t1);
quicksort(data,1,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%0.4f\n",gettime(t,t1,t2));

QueryPerformanceFrequency(&t1);
MergeSort(data,0,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%0.4f\n",gettime(t,t1,t2));

return 0;
}追问

C:\Program Files\MSBuild\Microsoft.Cpp\v4.0\Platforms\Win32\Microsoft.Cpp.Win32.Targets(147,5): error MSB6006: "CL.exe" exited with code 2.
在VS和VC都编译时出错了。。头文件的问题吧。。。请问你用的什么编译环境？

追答

vc6

追问

Stack around the variable 'data' was corrupted.
运行出的结果全是0.0000
你能不能再检查下，谢谢

追答

运行结果为零很正常啊，这已经很高的计时精度了，但是执行时间很短，把主函数改一下：

LARGE_INTEGER m_swFreq, m_swStart, m_swStop;
void Stopwatch(int start0stop1)
{
float m_etime;
if (start0stop1==0)
{
QueryPerformanceCounter(&m_swStart);
}
else
{
QueryPerformanceCounter(&m_swStop);
if (m_swFreq.LowPart==0 && m_swFreq.HighPart==0) m_etime = -1;
else
{
m_etime = (float)(m_swStop.LowPart - m_swStart.LowPart);
if (m_etime < 0) m_etime += 2^32;
m_etime /= (m_swFreq.LowPart+m_swFreq.HighPart * 2^32);
printf("time:%.3f\n",m_etime);;
}
}
}
int main()
{
QueryPerformanceFrequency(&m_swFreq);
const int NUM = 1000;
srand(time(NULL));
int data[NUM];
int i;
for (i=0; i<NUM; ++i)
{
data[i] = rand()/(RAND_MAX/20000+1);
}

Stopwatch(0);
shellSort(data,NUM);
Stopwatch(1);

for (i=0; i<NUM; ++i)
{
data[i] = rand()/(RAND_MAX/20000+1);
}
Stopwatch(0);
heap_sort(data,NUM);
Stopwatch(1);

for (i=0; i<NUM; ++i)
{
data[i] = rand()/(RAND_MAX/20000+1);
}
Stopwatch(0);
quicksort(data,1,NUM);
Stopwatch(1);

for (i=0; i<NUM; ++i)
{
data[i] = rand()/(RAND_MAX/20000+1);
}
Stopwatch(0);
MergeSort(data,0,NUM);
Stopwatch(1);

return 0;
}