数据结构与算法分析_选择问题
本帖最后由 mingcxx 于 2016-9-10 20:42 编辑题目：编写一个程序解决选择问题。令k = N / 2。画出表格显示你的程序对于N为不同值时的运行时间。
（设有一组N个数确定其中第k个最大者，称选择问题（selection problem）。）
思路：读入前k个数到临时数组tmp（并按降序排列）。然后逐个读取后续数字X，当X大于第k个数时，将其加入数组tmp（并按降序排列）。最后返回位置k-1上的值。
实现：#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10000
int select(int arr[], int n, int k);
int main(void)
{
int * arr;
int value;
clock_t elapse;
system("color 0A");
srand((unsigned)time(NULL));
arr = (int *)malloc(sizeof(int) * N);;
for (int j = 0; j < N; j++)
{
arr = rand() % 100000;
printf("%d ", arr);
}
putchar('\n');
elapse = clock();
value = select(arr, N, N / 2);
elapse = clock() - elapse;
printf("Value: %d, elapsed: %.4lfs\n", value, (double)elapse / 1000);
free(arr);
system("pause");
return 0;
}
/*选择数组中第k个最大者*/
int select(int arr[], int n, int k)
{
int * tmp;
int i, j, ret;
tmp = (int *)malloc(sizeof(int) * k);
tmp = arr;
for (i = 1; i < k; i++) //读入k个元素并降序排列
{
tmp = arr;
for (j = i; j > 0; j--)
{
if (arr > tmp)
{
tmp = tmp;
tmp = arr;
}
}
}
for (i = k; i < n; i++) //读入arr
{
if (tmp < arr)
{
tmp = arr;
for (j = k - 1; j > 0; j--)
{
if (arr > tmp)
{
tmp = tmp;
tmp = arr;
}
}
}
}
ret = tmp;
free(tmp);
return ret;
}记录：
小记：该算法在输入数据量较少时，可以在合理的时间内给出结果。如果数据量过大，这个算法就不切实际了。
页:
[1]