问题标题: 求c++结构体排序讲义

https://ke.codingtang.com/#/course/handout?id=315&lesson_id=5911

冒泡排序
一、冒泡排序
       冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有元素再需要交换，也就是说该数列已经排序完成。
       这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
image.png

（12比上面的数都小，经过多次与相邻数字交换，最后浮到了顶端）
如果我们要将下面的数从大到小排序，冒泡排序的过程是这样的
原序列：12 35 99 18 76

第一轮（从第一个数开始，相邻数字相比较、交换）：
12 35 99 18 76
35 12 99 18 76
35 99 12 18 76
35 99 18 12 76
35 99 18 76 12
此时末尾确定了最小的数 12

第二轮（还是从第1个数开始，相邻数字相比较、交换）：
35 99 18 76 12
99 35 18 76 12 （这里是35和18进行比较，不需要交换位置，18比35小）
99 35 18 76 12
99 35 76 18 12 （最后一位的12是确定的，不需要比较）
第二轮在末尾确定了第2小的数 18

第三轮：
99 35 76 18 12
99 35 76 18 12
99 76 35 18 12
第三轮在末尾确定了第3小的数 35

第四轮：
99 76 35 18 12
99 76 35 18 12

这里对于5个数，需要4轮排序，每轮确定第i小的数。
每轮比较的数字对数比上一轮少一对。

代码实现冒泡排序（将a数组中a[1]~a[n]的元素从小到大排序）
for(int i=1;i<=n-1;i++)//表示排序的轮数，共需n-1轮
     for(int j=1;j<=n-i;j++)//第i轮要确定第i大的数，放在后面，需要比较n-i对数字（因为后面i-1个数已经确定下来，不需要比较）
          if(a[j]>a[j+1])   //相邻的数字比较，如果前大后小，就需要交换位置
               swap(a[j],a[j+1]);
 

二、冒泡排序优化
下面是一个大小为6的数组，经过一轮冒泡排序就是有序的了。
image.png
第一轮中，46分别与20、33、38、43比较并交换了位置，与60比较后不交换位置，此时数组中元素20,33,38,43,46,60已经是有序的了，后面就没必要再继续进行排序。

冒泡排序优化的原理：基本冒泡排序算法的代码**进行了n-1轮冒泡排序。但实际上当某一轮排序过后序列已有序时，显然不需要再继续排序，排序轮数可能远小于n-1轮。

冒泡排序优化的代码实现
for(int i=1;i<=n-1;i++) {  
    bool flag=false;  //定义一个标志位，用来记录某轮排序是否有数据交换发生
    for(int j=1;j<=n-i;j++) {
        if(a[j]>a[j+1]) {
            swap(a[j],a[j+1]);
            flag=true;  //有数据交换，则改变标志位的值
        }
    }
    if(flag==false)  //如果标志位的值没改变，说明本轮排序没有数据交换，即数组本身已经有序了，那么退出循环
        break;
}

桶计数
引言
       假设有一堆标了号码的球散落一地，需要我们统计标号1的球有多少个？标号2的球有多少个？标号3的球有多少个？……
       如果我们对球不做整理，直接去数，可能眼睛数花了还没数对。
       此时我们准备好若干个桶：1号桶，2号桶，3号桶，…… 将每种标号的球投入对应的桶中，这样每个桶中球的个数就比较清楚了。
 

一．定义桶数组
1. 桶数组要定义在主函数外，或者定义时将数组元素值初始化为0。
因为我们要用数组元素来计数，每个数组元素的初值都要确保是0。

2. 桶数组的大小要根据要计数的数据的最大值来确定。
因为桶数组的下标对应要计数的数据，要保证桶数组计数时下标不越界。

二．桶数组计数的过程
对于某数组中的数，我们想要统计不同的数有分别有多少个。

image.png

则我们可以定义一个桶数组b[10]； （桶数组要保证最大下标不小于5）
image.png

一开始桶数组中所有元素的值都是0，然后我们遍历a数组，开始计数：

遍历a数组：1，2，3，2，3，5，1，5，2，3
遇到1，b[1]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;
遇到5，b[5]++ ;
遇到1，b[1]++ ;
遇到5，b[5]++ ;
遇到2，b[2]++ ;
遇到3，b[3]++ ;

所以最后b[1]=2，b[2]=3，b[3]=3，b[4]=0，b[5]=2。
表示原来的数组中 1有2个，2有3个，3有3个，4没有，5有2个。
/*
因为讲义里没给例样，所以我自己附一个
int a[n+1];
int n; 
for(int i=1;i<=n;i++){
    cin>>t;
    a[t]++;
}
*/
 

一、桶排序的原理
       利用桶数组记录序列中每个数字出现的次数。由于用桶数组的下标对应序列中的数字，所以只要按下标从小到大的顺序，将桶数组记录的数字输出即可（注意桶数组的下标是对应数字，而桶元素的值对应该数字出现的次数）
 

二、桶排序的过程
       如果需要排序的数据在一个明显有限范围内（整型）时，我们可以用数组下标与数值一一对应，将每个数值放进与它对应的数组元素（桶）中，然后按照顺序输出各桶的值，将得到有序的序列。

比如：对于序列
image.png
从小到大排序：

定义一个桶（即数组）数组a[10]
桶数组a的所有元素赋初值为0，然后将每个数字计入对应桶元素中，
image.png

最后，按照从小到大的顺序遍历桶数组，如果桶元素a[i]的值非0，说明该元素下标对应的数字出现过，并且a[i]的值就是i这个数的个数，即要输出a[i]个i。

代码实现
如果要输入n个不超过1000的数字，使用桶排序从小到大输出，代码如下：

int a[1001];    //每个数的范围在1~1000 ，所以定义a[1001] （1~1000的桶）
int main(){
    int n ,t;
    cin>>n;
    for(int i=1;i<=n;i++){    //输入n个数
        cin>>t;
        a[t]++;        //用桶的下标存这个数，桶的值++
    }
    for(int i=1;i<=1000;i++){    //遍历桶数组
        for(int j=1;j<=a[i];j++){    //输出a[i]个i（a[i]为0则不输出）
            cout<<i<<' '; 
        }
    }
    return 0;
}
 

桶去重+桶的练习
一．桶去重的原理
       利用桶数组对输入的数据进行统计，如果某数字出现过，那么以该数字作下标的桶数组元素值必然大于0，因此我们可以知道在一个范围内那些数字出现，哪些数字没出现过。
       而对于出现过的数字，不管它出现了几次，输出时都只输出一遍，即完成了去重的功能。

二．桶去重的过程
对于某数组中的数，先利用桶数组记录某个数的个数。

image.png

定义b数组记录a数组中每个数字出现的次数：
image.png

如果要求按照原数组中的顺序输出所有数字（重复的只输出一次）
则需要遍历a数组，对每个数字做判断，是否对应的桶元素值大于0，如果大于0，则输出这个元素，但同时要把桶元素清零，防止后面输出同样的数字（去重）。

对上述数组来说，有如下过程：
遍历a数组，
遇到1，判断b[1]是大于0的，输出1，并将b[1]=0;
遇到2，判断b[2]是大于0的，输出2，并将b[2]=0;
遇到3，判断b[3]是大于0的，输出3，并将b[3]=0;
遇到2，判断b[2]是0，不输出;
遇到3，判断b[3]是0，不输出;
遇到5，判断b[5]是大于0的，输出5，并将b[5]=0;
遇到1，判断b[1]是0，不输出;
遇到5，判断b[5]是0，不输出;
遇到2，判断b[2]是0，不输出;
遇到3，判断b[3]是0，不输出;

所以最终输出的结果是1,2,3,5。
 

三、非正整数数据使用桶排序时的处理办法
将数据先转化为正整数！
       如输入一组负数，先将负数统一加上一个固定值变成正整数，接着进行桶排序，输出时再将元素减去固定值后输出。
       如输入一组小数，先将小数乘以一个固定值（10或100或1000……）使得这些数变成正整数，接着就可以进行桶排序，输出时再将元素除以固定值还原。
/*
因为讲义里没给例样，所以我自己附一个
for(int i=1;i<=n;i++){
        cin>>a[i];
        t[a[i]]++;
    }
for(int i=1;i<=n;i++){
    if(t[a[i]]){
        cout<<a[i]<<' ';
        t[a[i]]=0; 
    }
}
*/

四舍五入、分段收费问题
引言
       以前的课程中学过使用printf保留固定小数位数输出，但printf保留几位小数是不是遵从四舍五入呢？
       答案是不一定，比如：

printf("%.1f",3.25);
在不同的计算机上可能输出不同的结果，有的输出3.2，有的输出3.3，不一定遵从四舍五入。
       因此，我们需要用特殊的方法来实现四舍五入保留小数输出。

一、四舍五入保留n位小数
1. 什么是四舍五入
       在保留指定位数小数的时候，如果后一位的数字大于等于5，那么该位置+1（有进位需要进位）；如果小于5，那么该位置不变。

例如：
2.385保留两位小数的结果为2.39
12.96保留一位小数的结果为13.0
7.856保留两位小数的结果为7.86

2. 四舍五入的方法（保留n位小数）
将数字乘10，乘n次； (将小数要保留的部分都乘到整数位上）
加上0.5后取整；（若小数点后第一位数字大于等于5，就会进位，小于5则不进位）
最后再除以10.0，除n次。（将先前扩大的倍数还原）
例如对 3.25 四舍五入保留1位小数:
这是想要保留的部分：image.png
乘10，将想要保留的部分乘到整数位：image.png
加上0.5，如果后一位大于等于5，就会往整数位进1：image.png
取整：image.png
最后除以之前扩大的倍数10.0，还原：image.png

3. 四舍五入代码实现（以保留1位小数为例）
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    double s=3.25;
    printf("%.1f",int(s*10+0.5)/10.0);
    return 0;
}
4. 四舍五入保留n位小数
公式：int ( a * 10n + 0.5 ) / ( 10.0n )

五、 水费、打车费一类问题
1） 乘坐出租车时，在一定里程内，只会收取起步价；
2） 超过起步的里程再根据情况加收费用。

这类问题类似于数学中的分段函数。

在编程中，我们使用if-else，根据车子所开距离的不同分不同的情况讨论。

经典例题：1387 计算水费，1082 乘车费用

1387
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
    int w;
    double f;
    cin>>w;
    if(w<=152) 
        f=2.66*w;
    else if(w<=240)   
        f=2.66*152+3.55*(w-152);
    else   
        f=2.66*152+3.55*(240-152)+6.22*(w-240);
    f=(long long)(f*100+0.5)/100.0;     //注意数据f*100超出int范围，要用long long
    printf("%.2f",f); 
    return 0;
}
1082
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
        int n,m;
        double p;
        cin>>n>>m;
    if(n<=2.5) 
        p=6+m/5;
    else if(n<=10) 
        p=6+(n-2.5)*1.2+m/5;
    else 
        p=6+1.2*7.5+(n-10.0)*1.8+m/5;
        p=(int)(p+0.5);
            printf("%.0f",p);
        return 0;
}

例题选讲
分数序列之和 1021
（1）解题思路：先将序列的规律用代码体现出来，循环求和即可。
（2）核心代码：

#include<iostream>
#include <cstdio>
using namespace std;
int n,a,b,t; 
int main(){
    cin>>n;
    a=1;
    b=2;
    for(int i=1;i<=n;i++){
        sum+=(double)b/a;
        t=b;
        b=a+b;  //找到规律
        a=t;
    }
    printf("%.5f",(int)(sum*100000+0.5)/100000.0);   //四舍五入保留5位小数
    return 0;
}

循环取位数+最大公约数、最小公倍数
一、循环取位数
1. 提取个位数
对于一个n而言，模10可以用来提取个位数
1） 123/10=12…3 得到的余数是3
2） 这个余数即是个位数。

2. 三位数提取各个位数
1） 提取个位 a%10
2） 提取十位 a/10%10
3） 提取百位 a/100

3. 任意位提取各位数
原理：
就是把数字变到个位上再进行求余。

1） 即提取个位就除以1，提取十位就除以10，提取百位就除以100，提取千位就除以1000…
2） 然后求余10

4. 循环提取正整数n的每一位
原理：每次都提取n的最后一位（n%10），然后将n的最后一位除掉(n/=10)，重复这个过程，就能把n的每一位都取出来。

代码实现：
int n,a[100],cnt=0;
cin>>n;
while(n){
    a[++cnt]=n%10;
    n/=10;
}
//a数组存储了n中从低位到高位的每一位数字
``
二、 最大公约数
1. 定义
最大公约数，也称最大公因数、最大公因子。
指两个或多个整数共有因数中最大的一个。

如：求15和12的最大公约数
15的约数（因数）有：1,3,5,15
12的约数（因数）有：1,2,3,4,6,12
15和12公共的约数：1,3
则15和12的最大公约数是3

2. 编程求解两个整数a和b的最大公约数
方法一：枚举法
从a和b中较小的数开始往下枚举，找到的第一个a和b的公约数就是最大公约数。

#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=min(a,b);i>=1;i--){
         if(a%i==0 && b%i==0){
         cout<<i;
         break;
         }
    }
    return 0;
}

方法二：辗转相除法
原理：
用较大数 m 除以较小数 n，得到的余数 r作为下次运算中的较小数m，原来的n作为下次运算中的较大数。如此反复，直到最后余数是0为止，最后的除数就是这两个数的最大公约数。

代码实现：
#include<iostream>
using namespace std;
int main()
{
    int a,b,r; //求a，b的最大公约数，r表示余数
    cin>>a>>b;
    while(a%b!=0) {
        r=a%b;
        a=b;
        b=r;
    }
    cout<<b;
    return 0;
}
三、 最小公倍数
1. 定义
两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。

2. 编程求解两个整数a和b的最大公约数
方法一：枚举法
从a和b中较大的数开始往上枚举，找到的第一个a和b的公倍数就是最小公倍数。

#include<iostream>
using namespace std;
int main()
{
    int a,b,i;
    cin>>a>>b;
    i=max(a,b);
    while(1){
        if(i%a==0 && i%b==0){
            cout<<i;
            break;
        }
        i++;
    }
 return 0;
} 
方法二：公式法求最小公倍数
步骤：
1） 先求出a和b的最大公约数，设为x。
2） a 和 b 的最小公倍数：a*b/x 。

代码实现：
#include<iostream>
using namespace std;
int gcd(int a,int b){
    while(a%b!=0){
        int r=a%b;
        a=b;
        b=r;
    }
    return b;
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<a*b/gcd(a,b);
    return 0;
}

因数、平方根、质数
一、 基**概念
1. 因数
因数，或称为约数 ，定义：整数a/整数b (b≠0) 的商正好是整数而没有余数，我们就说b是a的因数。
例如：10%2==0， 2就是10的因数；
10%3!=0， 3就不是10的因数。

2. 开平方根函数
C++语言中开平方根函数是sqrt(x)
求实数x的平方根，得到的是一个double类型的结果。
添加头文件

#include <cmath>
sqrt函数可以求任意正数的平方根：

cout<<sqrt(4)<<endl;   //输出2
cout<<sqrt(0.36)<<endl;  //输出0.6
3. 质数
质数：又称素数，指只能被1和它本身整除的大于1的自然数。（注意1不是质数！）
如7只能被1和7整除，则7是质数。
10能被1、2、5、10整除，则10不是质数。

判断正整数n是否为质数的方法：
看n是否有除了1与n之外的因数，即我们可以把2~n-1的每个数都试一遍，看是否能整除n。
如果有能整除n的，则n就不是质数；
2~n-1都不能整除n，则n就是质数。

代码实现（定义函数实现）
bool isprime(int x){   //定义函数isprime用于判断某数是否为质数，是质数则返回true，不是质数则返回false
    if(x==1) return false;  //特殊判断，1不是质数
    for(int i=2;i<=x-1;i++){
        if(x%i==0) return false;  //有除了1和x以外的因数，x不是质数
    }
    return true;   //排除掉以上情况，x就是质数
}
代码优化
上述代码循环条件 i<=x-1 可以优化为i<=sqrt(x) ，即我们不需要把2~x-1的所有数都试一遍，只需要试2~sqrt(x)范围内是否有x的因数即可。

解释：x可以看做两整数相乘：x=a*b。
如果a是较小的因数，则a的范围在 1~sqrt(x)之间，排除掉1，如果在 2~sqrt(x)范围内找不到a，那另一个因数b也自然找不到。
所以找因数时范围只要在2~sqrt(x)内就够了。

bool isprime(int x){   //定义函数isprime用于判断某数是否为质数，是质数则返回true，不是质数则返回false
    if(x==1) return false;  //特殊判断，1不是质数
    for(int i=2;i<=sqrt(x);i++){
        if(x%i==0) return false;  //有除了1和x以外的因数，x不是质数
    }
    return true;   //排除掉以上情况，x就是质数
}
注意使用sqrt函数要加上头文件 cmath

4. 合数
与质数相对，除了能被1和其本身整除，还能被其它数整除的数，叫做合数。

我现在只能给你这么多

王旭杰在2022-02-25 22:13:35追加了内容

然后.............

豆呢？？？

质因数
一、 质因数的概念
质因数：又名素因数或质因子，在数论里是指能整除给定正整数的质数。

对于给定的正整数n，如果一个数a既是它的因数，同时也是质数，那么就说a是n的质因数。
if(n%a==0 && a是质数） a就是n的质因数。

1没有质因数
质数只有1个质因数，就是它本身
合数至少有1个质因数
例如：
5只有1个质因数，5本身。(5是质数。)
6的质因数是2和3。
9的质因数只有3。
 

二、 如何求正整数n的最小质因数
一个数n，除了1之外的最小因数一定是质数。
证明：

如果n是质数，那么除1之外，最小的因数是它本身，是质数。

如果n不是质数，那么在2–sqrt(n)之间必定存在n的因数，那么最小的因数可能是合数吗? 答案是不可能，假设最小的因数是合数，那么，这个合数必定还有因数，这个合数就不可能是最小的因数。

所以找n的最小质因数，只要从2开始往上枚举，找到n的第一个因数就是n的最小质因数。

int n,ans;
cin>>n;
for(int i=2;i<=n;i++){
    if(n%i==0){
        ans=i;
        break;
    }
}
cout<<ans;
 

三、 如何对正整数n分解质因数
每个合数都可以写成几个质数相乘的形式，这个过程就叫分解质因数

例如：
10=2*5
12=2*2*3
100=2*2*5*5

可以从2开始枚举n的因数，由上面的分析知：找到的第一个因数一定是n的最小质因数p。
可以先把n中所有的最小质因数p分离出来，此时n也变小（得到新的n），除1外它必然不含有小于等于p的因数，所以可以继续往上枚举，找新的n的最小因数，即原数的第二小质因数……

代码实现：
int n,cnt=0;
cin>>n;
cout<<n<<'=';
for(int i=2;i<=n;i++){
    while(n%i==0){
        n/=i;
        cnt++;
        if(cnt==1){
            cout<<i;
        }else{
            cout<<"*"<<i;
        }
    }
}