鱼C论坛

 找回密码
 立即注册
查看: 2338|回复: 0

[技术交流] 数据结构与算法分析_选择问题

[复制链接]
发表于 2016-9-10 20:37:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 mingcxx 于 2016-9-10 20:42 编辑

题目:编写一个程序解决选择问题。令k = N / 2。画出表格显示你的程序对于N为不同值时的运行时间。

(设有一组N个数确定其中第k个最大者,称选择问题(selection problem)。)

思路:读入前k个数到临时数组tmp(并按降序排列)。然后逐个读取后续数字X,当X大于第k个数时,将其加入数组tmp(并按降序排列)。最后返回位置k-1上的值。

实现:
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>

  4. #define N 10000

  5. int select(int arr[], int n, int k);

  6. int main(void)
  7. {
  8.     int * arr;
  9.     int value;
  10.     clock_t elapse;

  11.     system("color 0A");

  12.     srand((unsigned)time(NULL));
  13.     arr = (int *)malloc(sizeof(int) * N);;
  14.     for (int j = 0; j < N; j++)
  15.     {
  16.         arr[j] = rand() % 100000;
  17.         printf("%d ", arr[j]);
  18.     }
  19.     putchar('\n');

  20.     elapse = clock();
  21.     value = select(arr, N, N / 2);
  22.     elapse = clock() - elapse;
  23.     printf("Value: %d, elapsed: %.4lfs\n", value, (double)elapse / 1000);

  24.     free(arr);
  25.     system("pause");
  26.     return 0;
  27. }

  28. /*选择数组中第k个最大者*/
  29. int select(int arr[], int n, int k)
  30. {
  31.     int * tmp;
  32.     int i, j, ret;

  33.     tmp = (int *)malloc(sizeof(int) * k);
  34.     tmp[0] = arr[0];
  35.     for (i = 1; i < k; i++)            //读入k个元素并降序排列
  36.     {
  37.         tmp[i] = arr[i];
  38.         for (j = i; j > 0; j--)
  39.         {
  40.             if (arr[i] > tmp[j - 1])
  41.             {
  42.                 tmp[j] = tmp[j - 1];
  43.                 tmp[j - 1] = arr[i];
  44.             }
  45.         }
  46.     }

  47.     for (i = k; i < n; i++)            //读入arr[k]
  48.     {
  49.         if (tmp[k - 1] < arr[i])
  50.         {
  51.             tmp[k - 1] = arr[i];
  52.             for (j = k - 1; j > 0; j--)
  53.             {
  54.                 if (arr[i] > tmp[j - 1])
  55.                 {
  56.                     tmp[j] = tmp[j - 1];
  57.                     tmp[j - 1] = arr[i];
  58.                 }
  59.             }
  60.         }
  61.     }

  62.     ret = tmp[k - 1];
  63.     free(tmp);
  64.     return ret;
  65. }
复制代码
记录:
360截图20160910203454419.jpg
小记:该算法在输入数据量较少时,可以在合理的时间内给出结果。如果数据量过大,这个算法就不切实际了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 17:08

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表