基础排序算法导图

这是一篇关于基础排序算法的思维导图，主要内容有1.计数排序⒉选择排序3.插入排序4.成绩排序5.最小和。

基础排序算法

• 4.成绩排序
  • 题目：考试结束了，大家最关心的就是自己的排名，现在就请你帮大家排个序。问题简化下，考试的科目只有数学和语文。
  • 输入输出描述： 输入：第一行一个整数n，表示学生的个数。接下来n行，每行三个数，表示一个学生的学号，数学成绩，语文成绩。 输出：对这n个学生进行排序，先按照总分从高到底排序，如果总分相同，再按数学成绩从高到低，如果数学成绩也相同就按学号从小到大排序。（因为总分相同，数学成绩相同，语文成绩肯定相同，1<=n<=1000）
  • 样例： 输入： 4 1 95 97 2 100 96 3 98 96 4 99 95 输出： 2 196 100 96 4 194 99 95 3 194 98 96 1 192 95 97
  • 思路：用函数cmp来判断哪个学生排在前面，哪个学生排在后面。其实相当于一个冒泡排序。
  • 代码演示： #include <bits/stdc++.h> using namespace std; struct student //包含了学生的数学成绩、语文成绩、总成绩和学号 { int math; int chinese; int total; int id; }; student a[1010]; bool cmp(student x,student y) //排序 { if (x.total != y.total){ return x.total > y.total; } if (x.math != y.math){ return x.math > y.math; } return x.id < y.id; } int main() { int n; scanf("%d",&n); for (int i = 0;i < n;i++) { scanf("%d%d%d",&a[i].id,&a[i].math,&a[i].chinese); //输入 a[i].total = a[i].math + a[i].chinese; } for (int i = 0;i < n - 1;i++) //冒泡排序 { for (int j = 0;j < n - i - 1;j++) { if (cmp(a[j],a[j+1])) { swap(a[j],a[j+1]); } } } for (int i = n-1;i >= 0;i--) //输出 { printf("%d %d %d %d\n",a[i].id,a[i].total,a[i].math,a[i].chinese); } return 0; }
• 5.最小和
  • 题目：现在有n个0到9的数字，需要用它们组成两个数，这两个数都不能有前导0，使得这两个数加起来最小。
  • 输入输出描述： 输入：第一行一个整数n，表示数字的个数第二行n个0-9的数字。 输出：输出得到的最小和。（2≤n≤16）
  • 样例： 输入： 4 3 0 2 1 输出： 33 解析：10+23=33
  • 思路：先排序，最小的数和第二小的数放在一起，后面放0，最后放剩下的数字。第一个数插入，再第二个数插入，重复下去，这样就能得到最小值了。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int a[20]; int main() { int n; scanf("%d",&n); for (int i = 0;i < n;i++) { scanf("%d",&a[i]); } for (int i = 0;i < n;i++) //选择排序 { int k = i; for (int j = i;j < n;j++) { if (a[j] < a[k]) { k = j; } } swap(a[i],a[k]); } if (a[0] == 0) //把第一个数换成一个不为0的数 { for (int i = 1;i<n;i++) { if (a[i] > 0) { swap(a[i],a[0]); break; } } } if (a[1] == 0) //把第二个数换成一个不为0的数 { for (int i = 2;i < n;i++) { if (a[i] > 0) { swap(a[i],a[1]); break; } } } int num1 = 0,num2 = 0; //num1是第一个数的值，num2是第二个数的值 for (int i = 0;i < n;i++) { if (i % 2 == 0)//i是偶数时，num1插入a[i] { num1 = num1 * 10 + a[i]; } else //i是奇数时，num1插入a[i] { num2 = num2 * 10 + a[i]; } } printf("%d",num1+num2); //输出 return 0; }
• 3.插入排序
  • 题目： 现在请你对这样的问题，进行回答。 已知一个空序列，有两种操作方式。 0 x：表示在序列中插入一个值为x的数 1 k：询问序列中排在第k位的数是几，序列保持从小到大排序。
  • 输入输出描述： 输入： 输入数据第一行，一个整数m，表示有m个操作。 接下m行，每行的格式为“0 x” 或“1 k” ，如题目描述。（m<=5000） 输出： 对于每个Q询问，输出相应的结果。Q询问时，序列中一定有数。
  • 样例： 输入： 5 0 2 0 1 1 2 0 0 1 1 输出： 2 0
  • 思路：其实不难，照着题目要求的去做就可以了。如果第一个数是0，就插入，长度加一。第一个数是1，sort排序之后（建议用sort），输出要求的数就可以了。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N=5010; int a[N]; int main(){ int n,len=1; scanf("%d",&n); for (int i=1;i<=n;i++) { int x; int k; scanf("%d%d",&x,&k);//输入 if (x == 0)//插入 { a[len] = k; len++; } else//输出 { sort(a,a+len+0); printf("%d\n",a[k]); } } return 0; }
• 2.选择排序
  • 题目： 排序是处理很多问题的预处理部分。 之前的题目中，数值范围比较小，通过记录每个数值出现的次数，再按照数值从小到大，该数值出现多少次，就输出多少个。 这种方法，不适用于数值范围很大的情况，因为数组无法开。不能开出A[100000000]这样1亿大小的数组，数组的总大小要控制在3千万以内。 除了计数排序，还有很多种排序方法。下面来介绍一种简单的排序算法，选择排序。 选择排序的思想是：从前往后依次得到每个位置上的数。对于第i个位置，在[i+1,n]这些位置中，找到一个最小值，记录它的位置k。把A[i]和A[k]的值进行交换。如： for(i=1;i<=n;i++) {//依次得到每个位置上的数 k=i;//先设这个位置上的数不动，就是最小的那个 for(j=i+1;j<=n;j++)//在[i+1,n]这个区间找最小值的位置 if(A[j]<a[k])k=j; if(k!=i){//交换A[i]和A[k] t=A[i]; a[i]=A[k]; a[k]=t; } }
  • 输入输出描述： 输入：第一行一个整数n，表示要排序的数个数。第二行n个元素，表示待排序的元素。（1<=n<=1000） 输出：输出n个数字，表示排序后的数字。
  • 样例： 输入： 5 -1 2 1 4 3 输出： -1 1 2 3 4
  • 思路：既然题目已经给我们了范例，就可以参照一下。注意！我们要一直枚举，直到完成排序，所以要判断 n * n 次。
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 1010; int a[N]; int main() { int n; scanf("%d",&n); for (int i = 0;i < n;i++) { scanf("%d",&a[i]); } for (int i = 0;i < n-1;i++)//嵌套循环 { for (int j = 0;j < n-1-i;j++) { if (a[j] > a[j+1]) swap(a[j],a[j+1]);//交换 } } for (int i = 0;i < n;i++) { printf("%d ",a[i]); } return 0; }
• 1.计数排序
  • 题目：输入n个0~100的数，把它们从小到大输出。
  • 输入输出描述： 输入：第一行一个整数n，不超过100，第二行n个0~100的整数。 输出：输出一个数组，表示排序后的数组。
  • 样例： 输入： 10 1 1 0 2 3 4 6 0 1 2 输出： 0 0 1 1 1 2 2 3 4 6
  • 思路：很简单，几种方式大家都可以使用：桶排序、冒泡排序、sort排序……
  • 代码演示（sort排序）： #include <bits/stdc++.h> using namespace std; int a[110]; int main() { int n; cin >> n; for (int i = 1;i <= n;i++) { cin >> a[i]; } sort(a,a+n+1);//sort排序 for (int i = 1;i <= n;i++) { cout << a[i] << ' '; } return 0; }