排序专项练习

在比赛中排序题一般不会直接出，大部分会和其他考点一起出题，比较常见的形式是贪心算法

A

这个题有比较多的解法

解一

  • 先排序后去除偶数
  1. #include <algorithm>
  2. #include <cstdio>
  4. const int MAXN = 5e2 + 1;
  5. int n;
  6. int ar[MAXN];
  8. int main(void) {
  9.   scanf("%d", &n);
  10.   for (int i = 1; i <= n; i++) {
  11.     scanf("%d", &ar[i]);
  12.   }
  13.   std::sort(ar + 1, ar + 1 + n);
  14.   int flag = 0;
  15.   for (int i = 1; i <= n; i++) {
  16.     if (ar[i] % 2) {
  17.       if (flag) {
  18.         putchar(',');
  19.       } else {
  20.         flag = 1;
  21.       }
  22.       printf("%d", ar[i]);
  23.     }
  24.   }
  25.   return 0;
  26. }

B

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  5. using namespace std;
  7. const int MAXN = 1e2 + 1;
  8. int n, k;
  9. struct Node {
  10.   string name;
  11.   int time;
  12. } ar[MAXN];
  14. int cmp(Node a, Node b) { return a.time < b.time; }
  16. int main(void) {
  17.   cin >> n >> k;
  18.   for (int i = 1; i <= n; i++) {
  19.     cin >> ar[i].name >> ar[i].time;
  20.   }
  21.   sort(ar + 1, ar + 1 + n, cmp);
  22.   cout << ar[k].name << endl;
  23.   return 0;
  24. }
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  5. using namespace std;
  7. const int MAXN = 1e2 + 1;
  8. int n, k;
  9. struct Node {
  10.   string name;
  11.   int time;
  12.   int operator<(Node a) const { return this->time < a.time; }
  13. } ar[MAXN];
  15. int cmp(Node a, Node b) { return a.time < b.time; }
  17. int main(void) {
  18.   cin >> n >> k;
  19.   for (int i = 1; i <= n; i++) {
  20.     cin >> ar[i].name >> ar[i].time;
  21.   }
  22.   sort(ar + 1, ar + 1 + n);
  23.   cout << ar[k].name << endl;
  24.   return 0;
  25. }

C

  • 冒泡排序，模拟这个过程
  1. #include <cstdio>
  3. int n;
  4. int data[100001];
  5. int ans;
  7. int main(void) {
  8.   scanf("%d", &n);
  9.   for (int i = 1; i <= n; i++) scanf("%d", &data[i]);
  10.   for (int i = 1; i <= n; i++) {
  11.     for (int j = 1; j <= n - 1; j++)
  12.       if (data[j] > data[j + 1]) {
  13.         ans++;
  14.         int temp = data[j];
  15.         data[j] = data[j + 1];
  16.         data[j + 1] = temp;
  17.       }
  18.   }
  19.   printf("%d", ans);
  20.   return 0;
  21. }

D

  • 桶排序
  1. #include <cstdio>
  3. const int MAXN = 1e3 + 1;
  5. int n;
  6. int ar[MAXN];
  8. int main(void) {
  9.   scanf("%d", &n);
  10.   for (int i = 1; i <= n; i++) {
  11.     int temp;
  12.     scanf("%d", &temp);
  13.     ar[temp]++;
  14.   }
  15.   int maxn = 1;
  16.   for (int i = 2; i < MAXN; i++) {
  17.     if (ar[maxn] < ar[i]) {
  18.       maxn = i;
  19.     }
  20.   }
  21.   printf("%d", maxn);
  22.   return 0;
  23. }

E

  • 和上一题类似，一道非常经典的题
  1. #include <cstdio>
  3. const int MAXN = 1e3 + 1;
  5. int n;
  6. int ar[MAXN];
  8. int main(void) {
  9.   scanf("%d", &n);
  10.   int m = n;
  11.   for (int i = 1; i <= n; i++) {
  12.     int temp;
  13.     scanf("%d", &temp);
  14.     if (!ar[temp]) {
  15.       ar[temp]++;
  16.     } else {
  17.       m--;
  18.     }
  19.   }
  20.   printf("%d\n", m);
  21.   for (int i = 1; i < MAXN; i++) {
  22.     if (ar[i]) {
  23.       printf("%d ", i);
  24.     }
  25.   }
  26.   return 0;
  27. }

F

  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <string>
  6. using namespace std;
  8. const int MAXN = 41;
  10. int n;
  11. int b, g;
  12. double boy[MAXN];
  13. double girl[MAXN];
  15. int main(void) {
  16.   cin >> n;
  17.   for (int i = 1; i <= n; i++) {
  18.     string sex;
  19.     double temp;
  20.     cin >> sex >> temp;
  21.     if (sex == "male") {
  22.       boy[++b] = temp;
  23.     } else {
  24.       girl[++g] = temp;
  25.     }
  26.   }
  27.   sort(boy + 1, boy + b + 1);
  28.   sort(girl + 1, girl + 1 + g, greater<double>());  // 第三个参数使数据降序排列
  29.   for (int i = 1; i <= b; i++) {
  30.     printf("%.2lf ", boy[i]);
  31.   }
  32.   for (int i = 1; i <= g; i++) {
  33.     printf("%.2lf ", girl[i]);
  34.   }
  35.   return 0;
  36. }

G

  • 可以使用算法复杂度小于等于解答 - 图1#card=math&code=O%28n%5Clog%20n%29)的排序算法

快速排序

  1. #include <cstdio>
  2. #include <iostream>
  4. const int MAXN = 1e5 + 1;
  6. int n;
  7. int ar[MAXN];
  8. int temp[MAXN];
  10. void qsort(int l, int r);
  12. int main(void) {
  13.   scanf("%d", &n);
  14.   for (int i = 1; i <= n; i++) {
  15.     scanf("%d", ar + i);
  16.   }
  17.   qsort(1, n);
  18.   for (int i = 1; i <= n; i++) {
  19.     printf("%d ", ar[i]);
  20.   }
  21.   return 0;
  22. }
  24. void qsort(int l, int r) {
  25.   if (l >= r) return;
  26.   int mid = ar[l];
  27.   int i = l;
  28.   int j = r;
  29.   while (i < j) {
  30.     while (i < j && ar[j] >= mid) {
  31.       j--;
  32.     }
  33.     if (i < j) {
  34.       std::swap(ar[i], ar[j]);
  35.     }
  36.     while (i < j && ar[i] <= mid) {
  37.       i++;
  38.     }
  39.     if (i < j) {
  40.       std::swap(ar[i], ar[j]);
  41.     }
  42.   }
  43.   qsort(l, i - 1);
  44.   qsort(i + 1, r);
  45. }

归并排序

  1. #include <cstdio>
  3. const int MAXN = 1e5 + 1;
  5. int n;
  6. int ar[MAXN];
  7. int temp[MAXN];
  9. void msort(int l, int r);
  11. int main(void) {
  12.   scanf("%d", &n);
  13.   for (int i = 1; i <= n; i++) {
  14.     scanf("%d", ar + i);
  15.   }
  16.   msort(1, n);
  17.   for (int i = 1; i <= n; i++) {
  18.     printf("%d ", ar[i]);
  19.   }
  20.   return 0;
  21. }
  23. void msort(int l, int r) {
  24.   if (l == r) return;
  25.   int mid = (l + r) / 2;
  26.   msort(l, mid);
  27.   msort(mid + 1, r);
  28.   int i = l;
  29.   int j = mid + 1;
  30.   int k = l;
  31.   while (k <= mid && j <= r) {
  32.     if (ar[j] < ar[k]) {
  33.       temp[i++] = ar[j++];
  34.     } else {
  35.       temp[i++] = ar[k++];
  36.     }
  37.   }
  38.   while (k <= mid) {
  39.     temp[i++] = ar[k++];
  40.   }
  41.   while (j <= r) {
  42.     temp[i++] = ar[j++];
  43.   }
  44.   for (int i = l; i <= r; i++) {
  45.     ar[i] = temp[i];
  46.   }
  47. }

堆排序

  • 比较懒，所以用stl实现这个，优先队列默认是大根堆，我们对存入的数据取反就可以得到一个小根堆，然后取数据的时候再取反就可以对数据进行还原。大一的同学还没学过数据结构，可以先去了解一下堆的特性
  1. #include <cstdio>
  2. #include <queue>
  4. int n;
  5. std::priority_queue<int> heap;
  7. int main(void) {
  8.   scanf("%d", &n);
  9.   for (int i = 1; i <= n; i++) {
  10.     int temp;
  11.     scanf("%d", &temp);
  12.     heap.push(-temp);
  13.   }
  14.   while (!heap.empty()) {
  15.     printf("%d ", -heap.top());
  16.     heap.pop();
  17.   }
  18.   return 0;
  19. }

H

  • 贪心经典题
  • 以b排序然后冲前向后搜索不交叉的段
  1. #include <algorithm>
  2. #include <cstdio>
  4. const int MAXN = 1e6 + 1;
  6. int n;
  7. int ans;
  8. struct Node {
  9.   int a, b;
  11.   int operator<(const Node node) const {
  12.     return b >= node.b ? b == node.b && a < node.a ? 1 : 0 : 1;
  13.   }
  14. } node[MAXN];
  16. int main(void) {
  17.   scanf("%d", &n);
  18.   for (int i = 1; i <= n; i++) {
  19.     int a, b;
  20.     scanf("%d%d", &a, &b);
  21.     node[i].a = a;
  22.     node[i].b = b;
  23.   }
  24.   std::sort(node + 1, node + 1 + n);
  25.   int end = 0;
  26.   for (int i = 1; i <= n; i++) {
  27.     if (node[i].a >= end) {
  28.       ans++;
  29.       end = node[i].b;
  30.     }
  31.   }
  32.   printf("%d", ans);
  33.   return 0;
  34. }

I

  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <iostream>
  5. using namespace std;
  7. const int MAXN = 3e2 + 1;
  9. int n;
  10. struct Node {
  11.   int chinese;
  12.   int math;
  13.   int english;
  14.   int id;
  16.   int operator<(const Node a) const {
  17.     int total_a = chinese + math + english;
  18.     int total_b = a.chinese + a.math + a.english;
  19.     if (total_a < total_b) {
  20.       return 0;
  21.     } else if (total_a == total_b && chinese < a.chinese) {
  22.       return 0;
  23.     } else if (total_a == total_b && chinese == a.chinese && id > a.id) {
  24.       return 0;
  25.     } else {
  26.       return 1;
  27.     }
  28.   }
  29. } stu[MAXN];
  31. int main(void) {
  32.   cin >> n;
  33.   for (int i = 1; i <= n; i++) {
  34.     int a, b, c;
  35.     cin >> a >> b >> c;
  36.     stu[i].chinese = a;
  37.     stu[i].math = b;
  38.     stu[i].english = c;
  39.     stu[i].id = i;
  40.   }
  41.   sort(stu + 1, stu + 1 + n);
  42.   for (int i = 1; i <= 5; i++) {
  43.     cout << stu[i].id << " " << stu[i].chinese + stu[i].math + stu[i].english
  44.          << endl;
  45.   }
  46.   return 0;
  47. }

J

  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  5. const int MAXN = 1e5 + 1;
  7. int n;
  8. int array_a[MAXN];
  9. int array_b[MAXN];
  10. int ans;
  12. int main(void) {
  13.   scanf("%d", &n);
  14.   for (int i = 1; i <= n; i++) {
  15.     scanf("%d", array_a + i);
  16.   }
  17.   for (int i = 1; i <= n; i++) {
  18.     scanf("%d", array_b + i);
  19.   }
  20.   std::sort(array_a + 1, array_a + 1 + n);
  21.   std::sort(array_b + 1, array_b + 1 + n);
  22.   for (int i = 1; i <= n; i++) {
  23.     ans += abs(array_a[i] - array_b[i]);
  24.   }
  25.   printf("%d", ans);
  26.   return 0;
  27. }

K

  1. #include <algorithm>
  2. #include <cstdio>
  4. const int MAXN = 2e4 + 1;
  6. int n, b;
  7. int ar[MAXN];
  8. int ans;
  10. int main(void) {
  11.   scanf("%d%d", &n, &b);
  12.   for (int i = 1; i <= n; i++) {
  13.     scanf("%d", ar + i);
  14.   }
  15.   std::sort(ar + 1, ar + 1 + n, std::greater<int>());
  16.   int total = 0;
  17.   for (int i = 1; i <= n; i++) {
  18.     total += ar[i];
  19.     if (total > b) {
  20.       ans = i;
  21.       break;
  22.     }
  23.   }
  24.   printf("%d", ans);
  25.   return 0;
  26. }

L

  • 求逆序对有很多种方法因为归并排序的特性所以归并排序可以求逆序对，只需要在归并排序上添加一条语句就行，也可以使用线段树求解
  1. #include <cstdio>
  3. const int MAXN = 1e5 + 1;
  4. int a[MAXN];
  5. int n;
  6. long long ans;
  7. int c[MAXN] = {0};
  9. void msort(int l, int r);
  11. int main(void) {
  12.   scanf("%d", &n);
  13.   for (int i = 1; i <= n; i++) scanf("%d", a + i);
  14.   msort(1, n);
  15.   printf("%lld", ans);
  16.   return 0;
  17. }
  19. void msort(int l, int r) {
  20.   if (l == r) return;
  21.   int mid = (l + r) / 2;
  22.   msort(l, mid);
  23.   msort(mid + 1, r);
  24.   int i = l;
  25.   int j = mid + 1;
  26.   int k = l;
  28.   while (k <= mid && j <= r) {
  29.     if (a[j] < a[k]) {
  30.       c[i++] = a[j++];
  31.       ans += mid - k + 1;
  32.     } else
  33.       c[i++] = a[k++];
  34.   }
  35.   while (k <= mid) c[i++] = a[k++];
  36.   while (j <= r) c[i++] = a[j++];
  37.   for (int i = l; i <= r; i++) a[i] = c[i];
  38. }

M

  • 贪心算法
  1. #include <algorithm>
  2. #include <cstdio>
  4. const int MAXN = 1e3 + 1;
  6. struct array {
  7.   int time;
  8.   int p;
  9. } Array[MAXN];
  10. int n;
  11. int temp = 0;
  12. double ans = 0.0;
  14. bool cmp(struct array a1, struct array a2) { return a1.time < a2.time; }
  16. int main(void) {
  17.   scanf("%d", &n);
  18.   for (int i = 1; i <= n; i++) {
  19.     scanf("%d", &Array[i].time);
  20.     Array[i].p = i;
  21.   }
  22.   std::sort(Array + 1, Array + 1 + n, cmp);
  23.   for (int i = 1; i <= n; i++) {
  24.     printf("%d ", Array[i].p);
  25.     temp += Array[i].time;
  26.     if (i != n)
  27.       ans += temp;
  28.     else
  29.       puts("");
  30.   }
  31.   printf("%.2lf", ans / (n * 1.0));
  32.   return 0;
  33. }