头像

ssuunn

DTOJ




离线:2小时前


最近来访(61)
用户头像
zeng9999jian
用户头像
voyager1969
用户头像
SUPERDOGE
用户头像
xlz
用户头像
foxfuns
用户头像
18059832643
用户头像
陈平安
用户头像
lrf
用户头像
红鲤鱼与绿鲤鱼与驴
用户头像
zrzzrz
用户头像
zyz529
用户头像
大大怪
用户头像
jchhh
用户头像
于于
用户头像
itdef
用户头像
lixiaoqian
用户头像
路过的老年人
用户头像
wuwendongxi
用户头像
填海难....填心更难
用户头像
蓬蒿人


ssuunn
7小时前

这个嘛。。。
接着

上次的帖子

上次好像还没讲完。。。
担心这个帖子承受不了(太长了。。。)
所以就此结束。。。
现在继续!

还记得这个吗?从这里开始回顾吧!


稳定的排序

鸡尾酒排序(cocktail sort)— $O(n^2)$
原地归并排序— $O(n log_2 n)$如果使用最佳的现在版本
二叉排序树排序(binary tree sort)— $O(n log n)$期望时间;$O(n^2)$最坏时间;需要$O(n)$额外空间
鸽巢排序(pigeonhole sort)— $O(n+k)$;需要$O(k)$额外空间
基数排序(radix sort)— $O(n \times k)$;需要$O(n)$额外空间
侏儒排序(gnome sort)— $O(n^2)$
图书馆排序(library sort)— $O(n log_2 n)$期望时间;$O(n^2)$最坏时间;需要$(1+ε)n$额外空间
块排序(block sort)— $O(n log_2 n)$

不稳定的排序

Clover排序算法(Clover sort)— $O(n)$期望时间,$O(n^2)$最坏情况
梳排序— $O(n log n)$
平滑排序(smooth sort)— $O(n log_2 n)$
内省排序(introsort)— $O(n log_2 n)$
耐心排序(patience sort)— $O(n log_2 n + k)$最坏情况时间,需要额外的$O(n + k)$空间,也需要找到最长的递增子序列(longest increasing subsequence)

不实用的排序

(奇葩的排序)

猴子Bogo排序 — $O(n × n!)$,最坏的情况下期望时间为无穷,不过最好时间复杂度为$O(1)$。
Stupid排序 — $O(n^3)$;递归版本需要$O(n^2)$额外存储器
珠排序(bead sort)— $O(n)$ or $O(\sqrt n)$,但需要特别的硬件
煎饼排序 — $O(n)$,但需要特别的硬件
臭皮匠排序(stooge sort)算法简单,但需要约$O(n^{2.7})$的时间


我在上次的帖子的评论区发的:
有时间我会把下面这些排序算法其中一部分的代码
新创一个帖
放到上面
以免这个帖被挤爆。。。
当然就是这个帖子啦~~


。。。废话说了那么多。。。

也该切入正题了。。。


鸡尾酒排序

鸡尾酒排序是冒泡排序的优化版,又叫“快乐小时排序”(啥意思,完全不理解为啥取这个名字)。
在下面这种特殊数据中会体现出它的优势:

2 3 4 5 6 7 8 1
              ^

get到重点了吗?
从数据中可以发现:2~8都是排好序的,只有一个1在最后面
来看看冒泡排序的做法:

排序前:2 3 4 5 6 7 8 1
第一轮:2 3 4 5 6 7 1 8
第二轮:2 3 4 5 6 1 7 8
第三轮:2 3 4 5 1 6 7 8
第四轮:2 3 4 1 5 6 7 8
第五轮:2 3 1 4 5 6 7 8
第六轮:2 1 3 4 5 6 7 8
第七轮:1 2 3 4 5 6 7 8
第八轮:1 2 3 4 5 6 7 8 (没有数据交换,排序成功)

这个数据用冒泡排序法经过了八轮。
来试试鸡尾酒排序吧!
鸡尾酒排序:
如果现在正在进行第奇数轮,就从前往后遍历
如果现在正在进行第偶数轮,就从后往前遍历

排序前:2 3 4 5 6 7 8 1
第一轮:2 3 4 5 6 7 1 8
第二轮:1 2 3 4 5 6 7 8     !!!
第三轮:1 2 3 4 5 6 7 8 (没有交换数据,排序成功)

天哪!鸡尾酒排序只用了三轮就解决了!
来看看代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int cnt = 0;
    while (1) {
        int f = 0; cnt++;
        if(cnt & 1)
            for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) swap(a[i], a[i + 1]), f = 1;
        else
            for (int i = n;i > 1; i--) if(a[i] < a[i - 1]) swap(a[i], a[i - 1]), f = 1;
        if(!f) break;
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
}

二叉排序树排序

排序方法:

puts("二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree)。");
puts("对于每一个节点:");
puts("如果左子树不为空,则左子树上所有节点的值均小于它的值。");
puts("如果右子树不为空,则右子树上所有节点的值均大于它的值。");
puts("每次在二叉排序树中插入数值,最后输出中序遍历求出排序结果。");

不系很了解二叉排序树的童鞋们可以自己上网查找O~

#include<bits/stdc++.h>
#define LL long long
#define INF 0x7FFFFFFF
using namespace std;
const int N = 1e8 + 10;
int n, idx, rt;
int a[N], t[N];
int ch[N][2];
void insert(int &x, int val) {
    if (!x) {
        x = ++ idx;
        t[x] = val;
        return;
    }
    else {
        if(val < t[x]) insert(ch[x][0], val);
        else insert(ch[x][1], val);
    }
}
void dfs(int x) { //中序遍历二叉排序树
    if(!x) return;
    dfs(ch[x][0]);
    printf("%d ", t[x]); //输出
    dfs(ch[x][1]);
}
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i <= n; i++) insert(rt, a[i]);
    dfs(rt);
    puts("");
    return 0;
}

侏儒排序

有一个侏儒对花盆进行排序。
他每次只关注自己在的位置上的花盆和往后一个位置的花盆
如果这两个花盆的顺序是正确的,那么他就往前走一个位置。
否则把这两个花盆交换,往后走一个位置。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    int s = 1;
    while(s <= n) {
        if(a[s - 1] <= a[s] || s == 0) s++;
        else swap(a[s], a[s - 1]), s--;
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
} 

非常qi pa奇葩的猴子排序

。。。
这是什么鬼东东。。。
明显用来折磨人的
不TLE才怪。。。
定理:给一只猴子一个键盘,在无限长的时间里,这只猴子肯定能敲出指定的文本,如《莎士比亚全集》。
很奇葩啊。。。
猴子排序就是。。。每次把数组打乱,然后检查数组是否有序。。。

这这这过分了。。。

我们来康康猴子排序的特奇葩代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int check() {
    for (int i = 1;i < n; i++) if(a[i] > a[i + 1]) return 0;
    return 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    while (1) {
        random_shuffle(a + 1, a + 1 + n);   //随机打乱数组的系统函数 
        if(check()) break;
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
} 


分享 网课有感

ssuunn
1天前
网课有感·其一
语数英体狂轰乱炸       //这。。。
无数蒟蒻枯(哭)黄了啊
小白菜啊地里黄啊       //好有道理啊
一堆作业好恐慌啊       //好有道理啊
凌晨一点作业才发       //运用了夸张的修辞手法,生动形象地描写了学生们的无奈╮(╯▽╰)╭
不仅如此网络还卡       //这句很有道理。。。

网课有感·其二
上课链接发一大堆       //哎。。。学生的切身体会。。。
我整理地真是悲催       //悲催啊。。。
上课连线经常卡退       //网络质量差也是常有的事。。。┭┮﹏┭┮
校园何时可以回归       //欸我也不知道。。。


分享 比赛公告

ssuunn
4天前

我自己搞了个比赛
在洛谷上

点我进入比赛




ssuunn
7天前

感兴趣的可以试下

题目描述
数独是一个有趣的游戏。你需要在一个$9 \times 9$的矩阵中的每个格子中填入1 ~ 9的数字,使得没有两个相同的数字填入同一行、同一列或同一个九宫格中。

整个矩阵被划分为9个九宫格,若两个格子同时在最左三列、最右三列或中间三列,且同时在最左三行、最右三行或中间三行,则这两个格子在同一九宫格中。

现在有一个数独的初始状态,出题人想对其进行一些修改和询问操作。需要注意:在操作时,初始状态中的数也可以被删除或者合并时被替换。

向目前状态中的指定位置填入一个数:但有可能这个位置已经有一个数了,此时你需要输出一行Error!,然后不进行这次修改操作;在指定的这个位置没有数的情况下,这个数已经与之前存在的在同一行、列或九宫格中的数构成冲突,此时,你需要按照行、列、九宫格的顺序,找到第一种冲突的情况,输出一行Error:row!,Error:column!或Error:square!,然后不进行这次修改操作;否则,你需要输出OK!,并在指定位置填入该数。

删除目前状态中的一个位置上的数:若这个位置没有数字,此时你需要输出一行Error!,然后不进行任何操作;否则你需要输出一行OK!,并将该位置的数删除。

查询目前状态中的某个位置能填入多少种数字;若被查询的位置已经有数字了,你需要输出一行Error!;否则,输出一行一个整数n表示能填入的数字个数,随后nn行每行一个整数,按照从小到大的顺序输出能填入的数字。

将之前的第i次操作后的数独状态和第j次操作后的数独状态进行合并,作为当前状态。需要注意:对于所有的5种操作,包括但不限于出现Error!或是没有进行任何修改,均被算作一次操作。合并时以行为第一关键字,列为第二关键字的顺序依次考虑每个格子,若第i次操作后的数独状态中该位置有数且不会与之前冲突则优先填入;否则,在不会与之前冲突的情况下,填入第j次操作后的数独状态中该位置的数。若均没有数字或均与本次合并中已填入的数字冲突,则不填入任何数。输出一行,包含空格隔开的两个整数,表示最终的结果中有多少数字来自第ii次操作后的数独状态中,多少来自第jj次操作后的数独状态中。

查询整个数独的状态,你需要使用方阵格式将整个数独目前的状态输出。方阵格式是一个$19 \times 19$的二维字符数组,具体格式如下,其中用0表示该位置还未填入数字。

+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|5|7|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|7|1|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|9|8|7|6|5|4|3|2|1|
+-+-+-+-+-+-+-+-+-+

输入格式
输入的前19行为一个二维字符数组,为数独的初始状态的方阵格式。

随后一行一个整数T表示操作的次数。

随后T行,每行为下列形式:

Insert x y k,表示在(x,y)位置插入数kk。

Delete x y,表示删除(x,y)位置的数。

Query x y,表示查询(x,y)位置能填入且不会出现冲突的数。

Merge i j,表示合并第i次操作后的状态和第j次操作后的状态。

Print,表示查询整个数独的状态。

其中x表示行数,从上到下分别为1到9,y表示列数,从左到右分别为1到9。

输出格式
对于每个操作,你需要按照题目描述进行对应的输出

输入样例

+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|5|7|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|7|1|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|9|8|7|6|5|4|3|2|1|
+-+-+-+-+-+-+-+-+-+
9
Insert 7 1 2
Insert 8 1 2
Insert 8 2 2
Query 8 9
Delete 6 1
Delete 8 1
Insert 1 1 1
Merge 6 4
Print

输出样例

OK!
Error:column!
Error:square!
6
4
5
6
7
8
9
OK!
Error!
OK!
13 1
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|5|7|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|2|0|0|0|7|1|0|0|0|
+-+-+-+-+-+-+-+-+-+
|0|0|0|0|0|0|0|0|0|
+-+-+-+-+-+-+-+-+-+
|9|8|7|6|5|4|3|2|1|
+-+-+-+-+-+-+-+-+-+



ssuunn
8天前

大家对这个有了解吗?

当然这个可以让输出更花样,不再那么单调看着不舒服

大家可以看看:

#include <iostream>
#include "windows.h"
using namespace std;
int main()
{
    cout << "原色testCOLOR(没有设置字体颜色)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY |FOREGROUND_RED |FOREGROUND_GREEN | FOREGROUND_BLUE);//设置三色相加
    cout << "白色testCOLOR(红色绿色蓝色相加)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);//设置红色
    cout << "红色testCOLOR(设置的颜色为红色)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN);//设置绿色
    cout << "绿色testCOLOR(设置的颜色为绿色)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_BLUE);//设置蓝色
    cout << "蓝色testCOLOR(设置的颜色为蓝色)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED |FOREGROUND_GREEN);//设置红色和绿色相加
    cout << "黄色testCOLOR(红色和绿色相加色)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED |FOREGROUND_BLUE);//设置红色和蓝色相加
    cout << "粉色testCOLOR(红色和蓝色相加色)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN |FOREGROUND_BLUE);//设置绿色和蓝色相加
    cout << "青色testCOLOR(绿色和蓝色相加色)" << endl;
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);//设置颜色,没有添加颜色,故为原色
    cout << endl;

    system("pause");
    return 0;
}

#include <windows.h> 
#include <stdio.h>

void print_black()      //黑色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,0);
} 

void print_blue()       //蓝色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,1);
}

void print_green()      //绿色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,2);
}

void print_reseda()     //浅绿色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,3);
}

void print_red()        //红色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,4);
}

void print_purple()     //紫色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,5);
}

void print_yellow()     //黄色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,6);
}

void print_white()      //白色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,7);
}

void print_gray()       //灰色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,8);
}

void print_bluish()     //淡蓝色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,9);
}

void print_ondine()     //淡绿色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,10);
}

void print_light_ondine()   //淡浅绿色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,11);
}

void print_reddish()        //淡红色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,12);
}

void print_lavender()       //淡紫色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,13);
}

void print_faint_yellow()   //淡黄色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,14);
}

void print_gloss_while()    //亮白色
{
    HANDLE hOut;        //  获取输出流的句柄
    hOut = GetStdHandle(STD_OUTPUT_HANDLE);   
    SetConsoleTextAttribute(hOut,15);
}

int main() 
{ 
     print_blue();          //蓝色
     printf("\t蓝色\n");
     print_gloss_while();
     print_green();         //绿色
     printf("\t绿色\n");
     print_gloss_while();
     print_reseda();        //浅绿色
     printf("\t浅绿色\n");
     print_gloss_while();
     print_red();           //红色
     printf("\t红色\n");
     print_gloss_while();
     print_purple();        //紫色
     printf("\t紫色\n");
     print_gloss_while();
     print_yellow();        //黄色
     printf("\t黄色\n");
     print_gloss_while();
     print_white();         //白色
     printf("\t白色\n");
     print_gloss_while();
     print_gray();          //灰色
     printf("\t灰色\n");
     print_gloss_while();
     print_bluish();        //淡蓝色
     printf("\t淡蓝色\n");
     print_gloss_while();
     print_ondine();        //淡绿色
     printf("\t淡绿色\n");
     print_gloss_while();
     print_light_ondine();  //淡浅绿色
     printf("\t淡浅绿色\n");
     print_gloss_while();
     print_reddish();       //淡红色
     printf("\t淡红色\n");
     print_gloss_while();
     print_lavender();      //淡紫色
     printf("\t淡紫色\n");
     print_gloss_while();
     print_faint_yellow();  //淡黄色
     printf("\t淡黄色\n");
     print_gloss_while();   //亮白色
     printf("\t颜色\n");

     system("pause");
     return 0; 
}

/*
颜色函数SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),前景色 | 背景色 | 前景加强 | 背景加强);
    前景色:数字0-15 或 FOREGROUND_XXX 表示  (其中XXX可用BLUE、RED、GREEN表示) 
    前景加强:数字8 或 FOREGROUND_INTENSITY 表示
    背景色:数字16 32 64 或 BACKGROUND_XXX 三种颜色表示 
    背景加强: 数字128 或 BACKGROUND_INTENSITY 表示
主要应用:改变指定区域字体与背景的颜色
前景颜色对应值: 
  0=黑色                8=灰色  
   1=蓝色                9=淡蓝色        十六进制                                  
  2=绿色                10=淡绿色       0xa          
  3=湖蓝色              11=淡浅绿色     0xb 
  4=红色                12=淡红色       0xc  
  5=紫色                13=淡紫色       0xd          
  6=黄色                14=淡黄色       0xe          
  7=白色                15=亮白色       0xf 
  也可以把这些值设置成常量。
*/
#include <stdio.h>
#include <windows.h>
void color(short x) //自定义函根据参数改变颜色 
{
    if(x>=0 && x<=15)//参数在0-15的范围颜色
        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), x);    //只有一个参数,改变字体颜色 
    else//默认的颜色白色
        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 7);
}
int main()
{       
    printf("此处为没调用颜色函数之前默认的颜色\n");
    //调用自定义color(x)函数 改变的颜色
    color(0);   printf("黑色\n");
    color(1);   printf("蓝色\n");
    color(2);   printf("绿色\n"); 
    color(3);   printf("湖蓝色\n");
    color(4);   printf("红色\n");
    color(5);   printf("紫色\n");
    color(6);   printf("黄色\n"); 
    color(7);   printf("白色\n");
    color(8);   printf("灰色\n");
    color(9);   printf("淡蓝色\n");
    color(10);  printf("淡绿色\n");
    color(11);  printf("淡浅绿色\n"); 
    color(12);  printf("淡红色\n");
    color(13);  printf("淡紫色\n");
    color(14);  printf("淡黄色\n");
    color(15);  printf("亮白色\n");
    color(16);    //因为这里大于15,恢复默认的颜色 
    printf("回到原来颜色\n");
    //直接使用颜色函数
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED | FOREGROUND_INTENSITY | BACKGROUND_GREEN | BACKGROUND_INTENSITY);
    printf("红色字体   前景加强 绿色背景 背景加强\n"); 
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),15 | 8 | 128 | 64);
    printf("亮白色字体 前景加强 红色背景 背景加强\n"); 
    //声明句柄再调用函数 
    HANDLE JB = GetStdHandle(STD_OUTPUT_HANDLE);//创建并实例化句柄 
    SetConsoleTextAttribute(JB, 2 | 8);
    printf("颜色及对应数字表:\n");
    for(int i = 0;i < 1000;i ++){
        //color(16);printf(" "); 
        SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), i);
        printf("%-3d", i);
        color(16);printf(" "); 
        if(i % 16 == 0) printf("\n");
    }
    color(16);
    return 0;
    //类似的函数还有system("color XX");(X是十六进制0~F之间的数,不过这种函数改变的是整个画面,而不能让多处局部变色;
}

当然网上也有大家可以上网查查看O~




ssuunn
8天前

一日闲来无事(啊呸,是闲的没事做),随便搞了个东东。。。

望各位行个方便资瓷 资瓷 资瓷

#include <bits/stdc++.h> //啊虽然直接万能头就🆗了。。。好样的我还搞了这么多
//万能头 
#include <windows.h>
//windows头文件 
#include <algorithm>
//STL 通用算法
#include <bitset>
//STL 位集容器
#include <cctype>
//字符处理
#include <cerrno>
//定义错误码
#include <cfloat>
//浮点数处理
#include <ciso646>
//对应各种运算符的宏
#include <climits>
//定义各种数据类型最值的常量
#include <clocale>
//定义本地化函数
#include <cmath>
//定义数学函数
#include <complex>
//复数类
#include <csignal>
//信号机制支持
#include <csetjmp>
//异常处理支持
#include <cstdarg>
//不定参数列表支持
#include <cstddef>
//常用常量
#include <cstdio>
//定义输入/输出函数
#include <cstdlib>
//定义杂项函数及内存分配函数
#include <cstring>
//字符串处理
#include <ctime>
//定义关于时间的函数
#include <cwchar>
//宽字符处理及输入/输出
#include <cwctype>
//宽字符分类
#include <deque>
//STL 双端队列容器
#include <exception>
//异常处理类
#include <fstream>
//文件输入/输出
#include <functional>
//STL 定义运算函数(代替运算符)
#include <limits>
//定义各种数据类型最值常量
#include <list>
//STL 线性列表容器
#include <locale>
//本地化特定信息
#include <map>
//STL 映射容器
#include <memory>
//STL通过分配器进行的内存分配
#include <new>
//动态内存分配
#include <numeric>
//STL常用的数字操作
#include <iomanip>
//参数化输入/输出
#include <ios>
//基本输入/输出支持
#include <iosfwd>
//输入/输出系统使用的前置声明
#include <iostream>
//数据流输入/输出
#include <istream>
//基本输入流
#include <iterator>
//STL迭代器
#include <ostream>
//基本输出流
#include <queue>
//STL 队列容器
#include <set>
//STL 集合容器
#include <sstream>
//基于字符串的流
#include <stack>
//STL 堆栈容器
#include <stdexcept>
//标准异常类
#include <streambuf>
//底层输入/输出支持
#include <string>
//字符串类
#include <typeinfo>
//运行期间类型信息
#include <utility>
//STL 通用模板类
#include <valarray>
//对包含值的数组的操作
#include <vector>
//STL 动态数组容器

using namespace std;
int main(){
    system("pause"); 
    return 0;
}

搞个这个帖让大家康康,大佬们如果还有别的头文件欢迎发在评论区!

现在我对全部大佬表示$Orz$!




ssuunn
24天前

在这之前。。。声明:
我还有这个排序算法的第二篇
点击下面的链接:

c++排序算法整理2

当然这些都是废话直接sort多好。。。

//放眼望去。。。好眼熟啊。。。
//当然身为神犇大佬的你不希望自己渺小到只会用sort。。。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);//<--!!!!!AC必备经典代码。。。。。
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
}

像上面这样简洁的代码难道不XIANG吗。。。(蒟蒻的心里话)

切入正题:

十种常见排序算法可以分为两大类:

比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。 包括插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序和归并排序

非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。包括计数排序、桶排序和基数排序


算法时/空复杂度:
插入排序:平均时间复杂度$O(n^2)$,最坏时间复杂度$O(n^2)$,最好时间复杂度$O(n)$,空间复杂度$O(1)$
希尔排序:平均时间复杂度$O(n^{1.3})$,最坏时间复杂度$O(n^2)$,最好时间复杂度$O(n)$,空间复杂度$O(1)$
选择排序:平均时间复杂度$O(n^2)$,最坏时间复杂度$O(n^2)$,最好时间复杂度$O(n^2)$,空间复杂度$O(1)$
堆排序:平均时间复杂度$O(nlog_2n)$,最坏时间复杂度$O(nlog_2n)$,最好时间复杂度$O(nlog_2n)$,空间复杂度$O(1)$
冒泡排序:平均时间复杂度$O(n^2)$,最坏时间复杂度$O(n^2)$,最好时间复杂度$O(n)$,空间复杂度$O(1)$
快速排序:平均时间复杂度$O(nlog_2n)$,最坏时间复杂度$O(n^2)$,最好时间复杂度$O(nlog_2n)$,空间复杂度$O(nlog_2n)$
归并排序:平均时间复杂度$O(nlog_2n)$,最坏时间复杂度$O(nlog_2n)$,最好时间复杂度$O(nlog_2n)$,空间复杂度$O(n)$
计数排序:平均时间复杂度$O(n+k)$,最坏时间复杂度$O(n+k)$,最好时间复杂度$O(n+k)$,空间复杂度$O(n+k)$
桶排序:平均时间复杂度$O(n+k)$,最坏时间复杂度$O(n^2)$,最好时间复杂度$O(n)$,空间复杂度$O(n+k)$
基数排序:平均时间复杂度$O(n \times k)$,最坏时间复杂度$O(n \times k)$,最好时间复杂度$O(n \times k)$,空间复杂度$O(n + k)$


提前声明:如果有点懵可以看看最后面的链接🔗,有配动图详细解释。

高危预警⚠⚠⚠⚠⚠⚠⚠⚠⚠⚠


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

算法描述
1.比较相邻的元素。如果第一个比第二个大,就交换它们两个;
2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
3.针对所有的元素重复以上的步骤,除了最后一个;
4.重复步骤1~3,直到排序完成。
总共要循环$n-1$次

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = n;i > 1; i--)
        for(int j = 1;j < i; j++)
            if(a[j] > a[j + 1]) swap(a[j], a[j + 1]); //交换两个数
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
}

2、选择排序(Selection Sort
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1;i < n; i++) {
        int w = i, Min = a[i];
        for (int j = i;j <= n; j++) if(Min > a[j]) w = j, Min = a[j]; //寻找🔎最小数和它的位置
        swap(a[i], a[w]);
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
}

3、插入排序(Insertion Sort
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int a[MAXN], n;
int main(){
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) {
        scanf("%d", &a[i]); int x = i - 1;
        while(a[x] > a[x + 1] && x > 0) swap(a[x], a[x + 1]), x--;
    }
    for (int i = 1;i <= n; i++) printf("%d ", a[i]); puts("");
    return 0;
}

4、希尔排序(Shell Sort
1959年$Shell$发明,第一个突破$O(n^2)$的排序算法(听起来挺厉害的。。。),是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

选择一个增量序列$t1,t2,t3,.. . tk$,其中$ti>tj,tk=1$;
按增量序列个数$k$,对序列进行$k$趟排序;
每趟排序,根据对应的增量ti,将待排序列分割成若干长度为$m$的子序列,分别对各子表进行直接插入排序。仅增量因子为$1$时,整个序列作为一个表来处理,表长度即为整个序列的长度。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
int main(){
    scanf("%d", &n);
    for (int i = 0;i < n; i++) scanf("%d", &a[i]);
    for (int step = n / 2; step > 0; step /= 2)
        for (int i = 0;i < step; i++)
            for (int j = i + step;j < n; j += step)
                if(a[j] < a[j - step]) {
                    int temp = a[j];
                    int k = j - step;
                    while (k >= 0 && temp < a[k]) {
                        swap(a[k + step], a[k]);
                        k -= step;
                    }
                }
    for (int i = 0;i < n; i++) printf("%d ", a[i]); puts("");
    return 0;
}

5、归并排序(Merge Sort
归并排序是建立在归并操作上的一种有效的排序算法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

算法描述
把长度为n的输入序列分成两个长度为$n/2$的子序列;
对这两个子序列分别采用归并排序;
将两个排序好的子序列合并成一个最终的排序序列。

参考代码:

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN], T[MAXN];
void Mergesort(int l, int r) {
    if (l == r) return; //区间内只有一个数,返回
    int mid = l + r >> 1; //相当于(l + r) / 2
    Mergesort(l, mid); //递归左半部分
    Mergesort(mid + 1, r); //递归右半部分
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) //合并
        if (a[i] <= a[j]) T[k++] = a[i++];
        else T[k++] = a[j++];
    while (i <= mid) T[k++] = a[i++];
    while (j <= r) T[k++] = a[j++];
    for (int q = l; q <= r; q++) a[q] = T[q]; //转移
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    Mergesort(1, n);
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}

6、快速排序(Quick Sort
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

参考代码:

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN];
void quickSort(int l, int r) {
    if (l >= r) return;
    int i = l, j = r, base = a[l]; //base取最左边的数为基准数
    while(i < j) {
        while (a[j] >= base && i < j) j--;
        while (a[i] <= base && i < j) i++;
        if (i < j) swap(a[i], a[j]);
    }
    a[l] = a[i]; a[i] = base; //基准数归位
    quickSort (l, i - 1); //递归左边
    quickSort (i + 1, r); //递归右边
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    quickSort(1, n);
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}

7、堆排序(Heap Sort
堆排序(Heap-sort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

参考代码:

#include  <bits/stdc++.h>
using namespace std;
int n;
const int MAXN = 1e8 + 10;
int h[MAXN], size;
void down(int u) {
    int t = u;  // t记录最小值
    if (2 * u <= size && h[2 * u] < h[t]) t = 2 * u; // 左儿子
    if (2 * u + 1 <= size && h[2 * u + 1] < h[t]) t = 2 * u + 1; // 右儿子
    if (t != u) { //需要调整
        swap(h[t], h[u]);
        down(t); //递归
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &h[i]);
    size = n;
    for (int i = n / 2; i >= 1; i--) down(i); //初始化堆
    while (n--) {
        printf("%d ", h[1]);
        h[1] = h[size]; size--;
        down(1); 
    }
    return 0;
}

参考代码2(优先队列):

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n;
priority_queue<int, vector<int>, greater<int> >q; //小根堆
int main() {
    scanf("%d", &n); int x;
    for (int i = 1;i <= n; i++) scanf("%d", &x), q.push(x);
    while (!q.empty()) {
        printf("%d ", q.top()); //入队
        q.pop(); //出队
    }
    return 0;
}

8、计数排序(Counting Sort
计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

参考代码

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
long long n, cnt[MAXN];
int main() {
    scanf("%lld", &n); int x = 0, Max = -0x3f3f3f, Min = 0x3f3f3f; //初始化最大值和最小值
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &x); cnt[x]++; //统计
        Max = max(Max, x); Min = min(Min, x); //更新最大值和最小值
    }
    for (int i = Min;i <= Max; i++)
        while(cnt[i]) cnt[i]--, printf("%d ", i); //输出
    return 0;
}

9、桶排序(Bucket Sort
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

感谢$xlz$大佬给的桶排代码!

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, Min = MAXN, Max = 0, sum[MAXN];
bool f[45];
vector<int> bucket[45];//定义桶,这里定义40个桶
void insertsort(int s) {
    for (int i = 0;i < bucket[s].size(); i++)
        for (int j = i;j >= 1; j--) if(bucket[s][j - 1] > bucket[s][j]) swap(bucket[s][j], bucket[s][j - 1]);//这里是从小到大排序
    for (int i = 0;i < bucket[s].size(); i++) printf("%d ", bucket[s][i]); //由于每个桶都是有序的,所以可以输出这个桶,节省了一次遍历的时间
}
void bucketsort() {
    for (int i = 1;i <= n; i++)
        bucket[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))].push_back(sum[i]), f[int((sum[i] - Min) / ((Max - Min + 1) / 40.0))] = 1;//运用最大最小值来合理分配桶
    for (int i = 0;i <= 40; i++) if(f[i]) insertsort(i); //如果当前桶有数值,则对桶内的数进行排序(这里用选择排序)
}
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++) {
        scanf("%d", &sum[i]);
        Min = min(Min, sum[i]), Max = max(Max, sum[i]); //为了能够合理利用空间,确保第一个桶和最后一个桶都有数,所以存储最大最小值
    }
    bucketsort();
    return 0; 
}

10、基数排序(Radix Sort
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

参考代码:

#include <bits/stdc++.h>
using namespace std;
int maxbit(int data[], int n) {
    int d = 1, p = 10; //d保存最大的位数 
    for (int i = 0;i < n; i++) while(data[i] >= p) p *= 10, d++;
    return d;
}
void radixsort(int data[], int n) { //基数排序 
    int d = maxbit(data, n);
    int tmp[n];
    int cnt[15], i, j, k, radix = 1;
    for (i = 1;i <= d; i++) { //进行d次排序
        memset(cnt, 0, sizeof(cnt)); //清空计数器
        for (j = 0;j < n; j++) {
            k = (data[j] / radix) % 10;
            cnt[k]++;
        }
        for (j = 1;j < 10; j++) cnt[j] += cnt[j - 1];
        for (j = n - 1;j >= 0; j--) {
            k = (data[j] / radix) % 10;
            tmp[cnt[k] - 1] = data[j];
            cnt[k]--;
        }
        for (j = 0;j < n; j++) data[j] = tmp[j];
        radix *= 10;
    }
}
const int MAXN = 1e8 + 10;
int n, array[MAXN];
int main(){
    scanf("%d", &n);
    for (int i = 0;i < n; i++) scanf("%d", &array[i]);
    radixsort(array, n);
    for (int i = 0;i < n; i++) printf("%d ", array[i]); puts("");
}

如释重负。。。

还没呢。。。

搜了些算法时间复杂度分析大家可以康康:


稳定的排序

鸡尾酒排序(cocktail sort)— $O(n^2)$
原地归并排序— $O(n log_2 n)$如果使用最佳的现在版本
二叉排序树排序(binary tree sort)— $O(n log n)$期望时间;$O(n^2)$最坏时间;需要$O(n)$额外空间
鸽巢排序(pigeonhole sort)— $O(n+k)$;需要$O(k)$额外空间
基数排序(radix sort)— $O(n \times k)$;需要$O(n)$额外空间
侏儒排序(gnome sort)— $O(n^2)$
图书馆排序(library sort)— $O(n log_2 n)$期望时间;$O(n^2)$最坏时间;需要$(1+ε)n$额外空间
块排序(block sort)— $O(n log_2 n)$

不稳定的排序

Clover排序算法(Clover sort)— $O(n)$期望时间,$O(n^2)$最坏情况
梳排序— $O(n log n)$
平滑排序(smooth sort)— $O(n log_2 n)$
内省排序(introsort)— $O(n log_2 n)$
耐心排序(patience sort)— $O(n log_2 n + k)$最坏情况时间,需要额外的$O(n + k)$空间,也需要找到最长的递增子序列(longest increasing subsequence)

不实用的排序

(奇葩的排序)

猴子Bogo排序 — $O(n × n!)$,最坏的情况下期望时间为无穷,不过最好时间复杂度为$O(1)$。
Stupid排序 — $O(n^3)$;递归版本需要$O(n^2)$额外存储器
珠排序(bead sort)— $O(n)$ or $O(\sqrt n)$,但需要特别的硬件
煎饼排序 — $O(n)$,但需要特别的硬件
臭皮匠排序(stooge sort)算法简单,但需要约$O(n^{2.7})$的时间


参考资料:

十大经典排序算法(超详细配动图解释)



活动打卡代码 AcWing 1323. 出现

ssuunn
28天前

哦天哪

#include<bits/stdc++.h>
using namespace std;
int n, a[1010];
int main(){
    cin >> n; int x;
    for(int i = 1;i <= n; i++) cin >> x, a[x] = 1;
    for(int i = 0;i <= 1000; i++) if(!a[i]) {cout << i << endl; break;}
    return 0;
}

$2^{2^{2}}$



活动打卡代码 AcWing 132. 小组队列

ssuunn
28天前
#include <bits/stdc++.h>
using namespace std;
int t, f[1000010], top = 0;
string s;
queue<int> q[1010];

void Queue() {
    q[0] = queue<int>();
    for (int i = 1; i <= t; i++) {
        int n; scanf("%d", &n);
        while (n--) {
            int x; scanf("%d", &x);
            f[x] = i;
        }
        q[i] = queue<int>();
    }
    printf("Scenario #%d\n", ++top);
    while (cin >> s && s[0] != 'S') {
        if (s[0] == 'E') {
            int x; scanf("%d", &x);
            if (q[f[x]].empty()) q[0].push(f[x]);
            q[f[x]].push(x);
        }
        else {
            int x = q[0].front();
            printf("%d\n", q[x].front());
            q[x].pop();
            if (q[x].empty()) q[0].pop();
        }
    }
    puts("");
}

int main() {
    while (cin >> t && t) Queue();
    return 0;
}



ssuunn
28天前
#include<bits/stdc++.h>
using namespace std;
int h[100010], st[100010], l[100010], r[100010];
int n;
int main(){
    while(cin>>n) {
        if(!n) break;
        for(int i = 1; i <= n; i ++)  scanf("%d", &h[i]);
        h[0] = h[n + 1] = -1;
        int top = -1;
        st[++top] = 0;
        for(int i = 1; i <= n; i ++){
            while(h[st[top]] >= h[i])  top --;
            l[i] = i - st[top];
            st[++top] = i;
        }
        top = -1;
        st[++top] = n + 1;
        for(int i = n; i; i --) {
            while(h[st[top]] >= h[i])  top--;
            r[i] = st[top] - i;
            st[++top] = i;
        }
        long long res = 0;
        for(int i = 1; i <= n; i ++)  res = max(res, (long long)h[i] * (l[i] + r[i] - 1));
        printf("%lld\n", res);
    }
    return 0;
}