找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1546|回复: 0
收起左侧

[米群网刷题小分队] [PAT-B] 1098 Insertion or Heap Sort

[复制链接]
发表于 5-3-2015 11:07 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

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

x
1098 Insertion or Heap Sort

判断是插入排序还是堆排序的中间一步,和1089很像,其实只要把两种排序都实现了就好了…… 暴力做

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>

  5. using namespace std;

  6. int a[102], b[102], c[102];

  7. void print(int *a, int n) {
  8.         for (int i = 0; i < n; ++i) {
  9.                 if (i) {
  10.                         putchar(' ');
  11.                 }
  12.                 printf("%d", a【i】);
  13.         }
  14.         puts("");
  15. }

  16. bool same(int *a,int *b, int n) {
  17.     for (int i = 0; i < n; ++i) {
  18.         if (a【i】 != b【i】) {
  19.             return false;
  20.         }
  21.     }
  22.     return true;
  23. }

  24. void insertion(int *a, int i) {
  25.         int temp = a【i】;
  26.         for (--i; (i >= 0) && (a【i】 > temp); --i) {
  27.                 a[i + 1] = a【i】;
  28.         }
  29.         a[i + 1] = temp;
  30. }
  31.        
  32.        
  33.        
  34. bool make1(int n) {
  35.     for (int i = 1; i < n; ++i) {
  36.         insertion(c, i);
  37.         if (same(c, b, n)) {
  38.             puts("Insertion Sort");
  39.             insertion(c, i + 1);
  40.             print(c, n);
  41.             return true;
  42.         }
  43.         
  44.     }
  45.     return false;
  46.    
  47. }

  48. void down(int *a, int i, int n) {
  49.         for (;;) {
  50.                 int left = (i << 1) | 1;
  51.                 if (left >= n) {
  52.                         break;
  53.                 }
  54.                 int right = left + 1;
  55.                 int x = ((right < n) && (a[right] > a[left]))?right:left;
  56.                 if (a【i】 > a[x]) {
  57.                         break;
  58.                 }
  59.                 swap(a[x], a【i】);
  60.                 i = x;
  61.         }
  62. }

  63. void deleteMax(int *a,int &n) {
  64.         swap(a[0], a[--n]);
  65.         down(a, 0, n);
  66. }

  67. void make2(int n) {
  68.        
  69.         puts("Heap Sort");
  70.         for (int i = (n >> 1) - 1; i >= 0; --i) {
  71.                 down(a, i, n);
  72.         }
  73.         int m = n;
  74.         while (!same(a, b, n)) {
  75.                 deleteMax(a, m);
  76.         }
  77.         deleteMax(a, m);
  78.         print(a, n);
  79.                
  80. }
  81.        
  82.                
  83.                

  84. int main() {
  85. int n;
  86.         scanf("%d", &n);
  87.         for (int i = 0; i < n; ++i) {
  88.                 scanf("%d", a + i);
  89.         }
  90.         memcpy(c, a, sizeof(int) * n);
  91.         for (int i = 0; i < n; ++i) {
  92.                 scanf("%d", b + i);
  93.         }
  94.         if (!make1(n)) {
  95.                 make2(n);
  96.         }
  97.         return 0;
  98. }
复制代码


本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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