泉州暑假集训Day 1

c++

编程语言学习记录 c++

发布日期: 2023-07-23

文章字数: 504

阅读次数:

PS: This is a note.

数据排序

①选择排序: 不稳定的排序

e.g. 输入n个数,将n个数从小到大排序

sort(a,a+n);
for(int i=0;i<n;i++)
{
    cout<<a[i]<<" ";
}

②冒泡排序: 从后往前排列元素

核心代码

for(int i=1;i<=n;i++)
{
    for(int j;j<=n-i;j++)
    {
        if(a[j]>a[j+1])
        {
            int t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
        }
    }
}

e.g. 将6,3,1,2,5,4从小到大排序

for(int i=1;i=n;i++)
{
    for(int j=1;j<=n;j++)
    {
        swap(a[i],a[j+1]);
    }
}

注: swap是交换函数

③插入排序: 将元素插入一个有序表中

e.g. d

④桶排序: 若待排序值在一个有限范围内时，可设置有限桶，最后输出各个桶的值，得出有序表的值

e.g. 明明的随机数

⑤快速排序: 最好的内部排序方法

e.g. de

注: sort是快排函数,详细可从C语言中文网查看

⑥归并排序: 两个组的比较

e.g. ddasd

⑦希尔排序: 直接插入排序算法的一种更高效的优化算法，非稳定排序算法，类似于宏观调控

e.g. dh

⑧基数排序: 属于分配式排序

e.g. dl

⑨堆排序: 一种近似完全二叉树的结构

e.g. dm

递推算法

递推算法例题

e.g. 数字三角形

e.g. 斐波那契数列(1,1,2,3,5,8……)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,fn,fn_1=1,fn_2=1,f[101]={0,1,1,2};
    cin>>n;
    for(int i=3;i<=n;i++)
    {
        //原代码
        f[i]=f[i-1]+f[i-2];
        //优化后
        fn=fn_1+fn_2;
        fn_2=fn_1;
        fn_1=fn;
    }
    cout<<f[n]<<endl<<fn;
    return 0;
}