# C/C++の算法笔记

说明一下emmm

个人表达能力有限,仅供参考,以后会慢慢改进的!

文中提供的所有参考算法代码仓库:GitHub - Natsuki-Kaede/cpp-algorithm: A algorithm repo for study.(opens new window)

# 排序!

# 计数排序

现在给出几个不同的整数值,如何将它们排序呢?

计数排序可以简单快速地将它们排序,基本原理如下:

定义一个一维数组a[i],我们将每个a[i]称为一个“桶”,i的值要大于该组数据的最大值

对于每个数据,我们把它装进相应的桶里,如 233 这个数据我们让计数器a[233]加1,代表233这个数字出现了一次。若出现了n次,则加n次1进行计数

此时,我们若从a[0]开始打印,一直打印到a[i],每个“桶”中的计数器计了几次就打印几次,即可实现我们想要的效果

如:将 123 , 233 , 433 ,666 , 1000 进行从小到大的排序,代码如下:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a[1001]; //要大于最大的数据1000
    int i , j , step;
    for (i = 0 ; i <= 1001 ; i++)
    {
        a[i] = 0; //将每个计数器初始化为0
    }
    for (i = 1 ; i <= 5 ; i++)
    {
        cin >> step; //读入数据,可用scanf,性能也更好
        a[step]++; //读入的数据所对应的计数器进行计数
    }
    for (i = 0 ; i <= 1001 ; i++) //依次判断
    {
        for(j = 1 ; j <= a[i] ; j++) //数据出现了几次,就打印几次(因为有计数器)
        {
            cout << i;   //输出
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

运行后,输入任何 1000 以内的5个整数,均可以从小到大排序输出

从大到小输出只需要倒序改成i--即可

该计数排序缺点:只能使用整数,只能排数据后输出数据,而且非常浪费空间,输入的数据有多大,就需要定义一个多大的一维数组!

计数排序对应源码:cpp-algorithm/Algorithm-Easy-Bucket-Sort at main · Natsuki-Kaede/cpp-algorithm · GitHub(opens new window)

# 冒泡排序

如果需要排序的是小数,或者数据巨大,又或者排序后需要输出它们对应的变量名而非数值,桶排序显然不适合这些场景。

冒泡排序的原理是再给出的一组数据中,每次对比两个数据并把它们按照要求排序,每对整组数据进行一次这样的排序后,会有一个最大/最小数据归位,多次排序后将全部归位,这样排序的缺点也是显而易见的,时间复杂度高,为O($N^2$),性能和效率相对较差。

代码实现: