东北小蟹蟹

排序算法介绍
前言一般来说,最简单的算法是模拟,其次则是排序(sort)。你要知道,很久以前的NOIP(现CSP)还没有排序这个...
扫描右侧二维码阅读全文
01
2019/10

排序算法介绍

前言

一般来说,最简单的算法是模拟,其次则是排序(sort)
你要知道,很久以前的NOIP(现CSP)还没有排序这个东西。当时的OIer,都是手打排序模板的。不过有过这样回忆的现在应该已经AFO了。
sort的功能很强大,但是自己动手打一份代码,一是有成就感,二,是可以魔改排序模板,根据题目需要调整。三、可以进行思维的训练。
当然在赛场上如果没有特殊需求,千万别浪费时间,该sortsort
好,废话不多说,get started!

另:本文中的排序算法一些(时间复杂度为nlogn的比较性排序算法,或非比较性排序算法+离散化)可以在luogu p1177上进行测试

非比较性排序

什么叫做非比较性排序?如果一个排序没有比较操作,就称它为非比较性排序。
这里我们会讲计数排序和桶排序。主讲计数排序,桶排大概说一下。基数排序实在是过于冷门。。代码写着还费劲,就不讲了

计数排序

例题再现

东北小蟹蟹他们班进行了语文小测,满分10分。
输入5名同学的成绩。比如:
2,8,5,3,8.
让你对这5名同学的成绩进行升序排列和降序排列。对于这个样例,则是:
2,3,5,8,8
8,8,5,3,2.
测试什么的自行lemon
好,思考一下:怎么做才能让它排序呢?

方法介绍

在这里,我们只需要一个一维数组就ok了。具体是怎么操作的呢?
这里满分为10分。好,我们申请一个大小为15的数组。(csp中防爆+5是个好习惯)
int a[15];
a[i]代表i分人的数量。目前没有处理任何同学,所以初始值都为0。
这时,

2分的同学低着头缓缓走了过来,你给a[2]加上了1。a[2]的值是1.
8分的同学趾高气扬地走了过来,你给a[8]加上了1。a[8]的值是1.
5分的同学愁眉不展地走了过来,你给a[2]加上了1。a[5]的值是1.
3分的同学十分兴奋地跑了过来,你给a[3]加上了1。a[3]的值是1.
8分的同学边哭边叹气走了过来,你给a[8]加上了1。a[8]的值是2.

注意是给对应位置的值+1,并不是设成1。如果那样,有重复分就乱了。

好啦,现在:

a[0]=0
a[1]=0
a[2]=1
a[3]=1
a[4]=0
a[5]=1
a[6]=0
a[7]=0
a[8]=2
a[9]=0
a[10]=0

ok,接下来该怎么办?
我们发现数组下标是有规律的。那我们就可以按照数组下标依次输出了

for(int i=0;i<=10;i++)
    if(score[i])
        printf("%d ",i);

棒!结束了!
哎等等等等。题目不是还让降序输出吗?那好:

for(int i=10;i;i--)//倒序输出
    if(score[i])
        printf("%d ",i);

棒!over了!
哎等等等等。如果有重复成绩,你这个代码只会输出一次,不符合要求!、
那我们怎么改?score记录的是当前分数的有多少人。那么,可以再套一个循环呀!

for(int i=0;i<=10;i++)
    for(int j=0;j<score[i];j++)
        printf("%d ",i);

棒!完结了!
愤怒的吃瓜群众:好人做到底,代码写全了!

代码

好的。下为完整代码:

#include <iostream>
#include <cstdio>
using namespace std;
int score[15];
int tmp;
int main()
{
    for(int i=0;i<5;i++)
    {
        scanf("%d",&tmp);
        score[tmp]++;
    }
    for(int i=0;i<=10;i++)
        for(int j=0;j<score[i];j++)
            printf("%d ",i);
    printf("\n");
    for(int i=10;i;i--)
        for(int j=0;j<score[i];j++)
            printf("%d ",i);
    return 0;
}

优缺点分析

设M为数据中的最大值,N为数据总数。这篇文章以后提到的排序优缺点分析同样基于此。

此算法的时间复杂度毫无疑问的O(N),贼快。
但空间复杂度是O(M)???
如果有三个数据,分别是1,100000,1234567890,计数排序直接当场去世。
小数呢?也当场去世。
所以总结,计数排序的时间复杂度嗖嗖的,但空间复杂度很感人,所以,他不算是常用的算法。

附加练习:

东北小蟹蟹他们班进行了语文大考,满分120分。
输入nn名同学的名字和成绩,格式如下:

7
ABCD 1
dbxxx 10
xiaomeng 55
xiaohua 99
xiaoming 119
chinese_teacher 120
bibibi 0

对成绩进行降序排列处理并输出:

chinese_teacher:120
xiaoming:119
xiaohua:99
xiaomeng:55
dbxxx:10
ABCD:1
bibibi:0

提示:可以用结构体,也可以成绩和名字进行同步排序。

桶排序

方法介绍

Last modification:October 18th, 2019 at 09:32 am
东北小蟹蟹已经穷的叮当都响不了啦!!qwq

Leave a Comment

One comment

  1. 兄主的仙人掌

    前排兹瓷!