Question

如果用C语言编写一个程序实现以下功能： 1、产生N个随机数（N可以更改） 2、用选择排序和堆排

如果用C语言编写一个程序实现以下功能：
1、产生N个随机数（N可以更改）
2、用选择排序和堆排序对产生的随机数进行排序
3、计算两种排序算法各自的时间
（急急急！！！！！！！）

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//获取N个0~999的随机数,方便打印阅读
int *getRandNum(int n)
{
 int i;
 int *p;
 
 p=(int *)malloc(sizeof(int)*n);
 srand(time(NULL));
 for (i=0; i<n; i++)
 {
  p[i] = rand()%1000;//随机数范围可修改这里。
 }
 return p;
}
void selection(int *src, int len)
{
 int i, j, k, temp;
 
 for(i=0; i<len; i++)
 {
  for (j=i+1, k=i; j<len; j++)
  {
   
   if(src[k] > src[j])
   {
    k=j;
   }
  }
  temp=src[i];
  src[i]=src[k];
  src[k]=temp;
 }
}
void display(int *src, int len)
{
 int i;
 
 for (i=0; len > 0 && i<len; i++)
 {
  printf("%3d ", src[i]);
 }
 printf("\n");
 
}
#define NUM  20
int main(void)
{
 int *data;
 
 data = getRandNum(NUM);
 display(data, NUM);
 selection(data, NUM);
 display(data, NUM);
}

追问

几个功能没有同时实现

我想要堆排序和选择排序同时出现，并且有选择提示

追答

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
int heapSize =0;
//获取随机数,方便打印阅读
int *getRandNum(int n)
{
 int i;
 int *p;
 
 p=(int *)malloc(sizeof(int)*n);
 srand(time(NULL));
 for (i=0; i<n; i++)
 {
  p[i] = rand();//随机数范围可修改这里。
 }
 return p;
}

int Left(int index)
{
 return ((index<<1)+1);
}
int Right(int index)
{
 return ((index<<1)+2);
}
void swap(int *a, int *b)
{
 int temp=*a;
 *a=*b;
 *b=temp;
}
void maxHeapify(int array[], int index)
{
 int largest = 0;
 int left = Left(index);
 int right = Right(index);
 
 if((left<=heapSize) && (array[left]>array[index]))
  largest = left;
 else
  largest = index;
 
 if((right <= heapSize) && (array[right]>array[largest]))
  largest = right;
 
 if(largest!=index)
 {
  swap(&array[largest], &array[index]);
  maxHeapify(array, largest);
 }
}

代码太长，拷贝不上去楼主再追问下。

追问

好的

再把剩下的发给我吧

追答

void buildMaxHeap(int array[], int length)
{
 int i;
 heapSize = length;
 for(i=(length>>1); i>=0; i--)
  maxHeapify(array, i);
}
void heap_sort(int array[], int length)
{
 int i;
 
 buildMaxHeap(array, (length -1));
 for(i=(length-1);i>=1; i--)
 {
  swap(&array[0],&array[i]);
  heapSize--;
  maxHeapify(array, 0);
 }
 
}
void selection(int *src, int len)
{
 int i, j, k, temp;
 
 for(i=0; i<len; i++)
 {
  for (j=i+1, k=i; j<len; j++)
  {
   
   if(src[k] > src[j])
   {
    k=j;
   }
  }
  temp=src[i];
  src[i]=src[k];
  src[k]=temp;
 }
}
void display(int *src, int len)
{
 int i;
 
 for (i=0; len > 0 && i<len; i++)
 {
  printf("%d ", src[i]);
 }
 printf("\n");
 
}

还有。。。。

追问

嗯嗯

？

把剩下的发给我吧

追答

#include
#define NUM 10000
int main(void)
{
int *data;
int *data2;
struct timeval begin,end;
double selectTime, heapTime;
data = getRandNum(NUM);
data2 = (int *)malloc(sizeof(int)*NUM);
memcpy(data2, data, sizeof(int)*NUM);
display(data, NUM);
printf("选择排序中。。。\n");
gettimeofday(&begin,NULL);
selection(data, NUM);
gettimeofday(&end,NULL);
selectTime = end.tv_sec-begin.tv_sec+(end.tv_usec-begin.tv_usec)/1000000.0;
display(data, NUM);

printf("堆排序中。。。\n");
gettimeofday(&begin,NULL);
heap_sort(data2,NUM);
gettimeofday(&end,NULL);
heapTime=end.tv_sec-begin.tv_sec+(end.tv_usec-begin.tv_usec)/1000000.0;
display(data2, NUM);
printf("N=%d, 选择排序耗时= %lf秒, 堆排序耗时=%lf秒\n", NUM, selectTime, heapTime);
free(data);
free(data2);
}

//多给点分吧，啊啊这么长的代码，写了一个下午呢。

追问

非常感谢你！

顺便问下，这程序有点小问题，麻烦你再帮忙修改下

cpp(64) : error C2084: function 'void __cdecl buildMaxHeap(int [],int)' already has a body

.cpp(113) : fatal error C1083: Cannot open include file: 'sys/time.h': No such file or directory

fatal error C1083: Cannot open include file: 'sys/time.h': No such file or directory

我是用Visual C++编译器运行的

Answer 2

#include <stdio.h>
#include <time.h>

int main()
{
int a[15] = {0};
int count = 0;

srand(time(NULL));
while ( 1 )
{
int r = rand()%15 + 1;

if (++a[r] > 1)
continue;
else
{
printf("%02d ", r);
if (count++ > 15)
break;
}
}
return 0;
}

追问

您的回答只是随机数的产生，下面的两个功能还没实现。