各类排序算法及比较

选择排序:

每次选择还未排序的值中最小的一个,和第一个交换.

思路很清晰,代码很好写,时间复杂度为O(n^2).

伪代码:

1
2
3
4
5
6
7
8
9

// 要排序的数组: data[n]
循环i从0到n-1:
    min = 0x7fffffff
    pos = 0
    循环j从i到n-1:
        如果 min > data[j]:
            pos = j
            min = data[j]
    交换data[pos]与data[i]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int i,j,min,pos,t;
for(i = 0; i < n; ++ i){
    min = 0x7fffffff;
    pos = 0;
    for(j = i; j < n; ++ j){
        if(min > data[j]){
            pos = j;
            min = data[j];
        }
    }
    t = data[i];
    data[i] = data[pos];
    data[pos] = t;
}

冒泡排序

枚举相邻的两个,如果前者大于后者,交换.

经过每一轮比较,最大的一个一定会跑到数组最后面,就像气泡浮出水面的过程,因此叫做冒泡排序.

思路简单,代码好写,时间复杂度O(n^2).

伪代码:

1
2
3
4
5

// 要排序的数组: data[n]
循环i从0到n-2:
    循环j从0到n-i-2:
        如果 data[j] > data[j+1]:
            交换data[j], data[j+1];

代码1:

1
2
3
4
5
6
7
8
9
10

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

代码2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int sorted = 0;
int t = 0;
while( !sorted ){ //当还没排序好
    sorted = 1; //先认为已经排序好
    for( int i = 1; i < n; ++ i ){
        if( data[i - 1] > data[i] ){
            t = data[i - 1];
            data[i - 1] = data[i];
            data[i] = t;
            sorted = false;// 还没排序完毕
        }
    }
    n--; // 最后一位已经排序好, 可以不用管它了
}

借助标志位sorted,能使得程序在已经排序完毕之后提前退出.

代码的格式与变量的命名

(今天没题了)

正确的代码格式能够让你一眼就看清楚代码的架构,同时,当你拿着你的代码问别人的时候, 正确的代码格式会让别人更愿意回答你的问题,别人也能更轻松找到你代码中的错误.

那么,如何才是正确的代码格式呢?

大括号与缩进

大括号的风格有两种:换行与不换行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// 换行
for(...)
{
    blah;
    blah;
    if(foo)
    {
        blah;
    }
    else
    {
        blah;
    }
}
// 不换行
for(...){
    blah;
    blah;
    if(foo){
        blah;
    }else{
        blah;
    }
}

个人更习惯后者.需要注意的就是 每遇到一个左大括号,下一行一定要多缩进一格,遇到一个右大括号,下一行少缩进一格.这样的结构能够让我们更清楚地看到多层if与for之间的层次结构关系.

在一般的IDE上,选中多行代码按Tab键(Q左边的)即可给这几行代码的开头添加一个锁紧,按shitf-Tab即可去掉一个缩进.

同时,大部分IDE的默认设置均是使用空格缩进,每次缩进4个空格.在某些IDE上(比如DevCPP)默认设置是使用制表符缩进,这种设置的代码在粘贴到别的地方的时候可能出现格式错位,建议修改为空格缩进.

修改方式: Devcpp中依次打开工具(Tools)-编译器选项(Compiler Options),把左下角的"标签"(tab)选项卡中的"使用tab字符"去掉,将tab位置(Tab size)修改为4.

其他IDE的修改方式大同小异.

空格

在< > = != == ^ * + - &&等运算符的左右加上空格,如:

1
2
3
4
5
6
7
8
9
10

if(a < 1){
    ;
}
if(a != 1){
    ;
}
if(foo ^ bar){
    ;
}
foo = bar;

在每一个逗号的后面添加一个空格,如:

1

printf("%d%d%d%d", a, b, c, d);

在for循环中的分号后面加一个空格,如:

1
2
3

for(int i = 1; i < 0; ++i){ // PS: 在某些环境下, for循环中使用++i比i++快一丢丢

}

在! &等一元运算符(只有一个参数的运算符)后不加空格,如:

1
2
3
4

scanf("%d%d%d", &a, &b, &c);
if(!a){
    ;
}

变量和函数的命名

有意义的变量名字能够让阅读你代码的人立刻理解变量的意义是什么,方便代码交流.

变量命名并没有清晰的规范,以下的都是作者的个人经验

循环变量命名: i j k

和总量大小有关的变量命名: m n

数组的命名: data[MAXN][MAXN] array[MAXN][MAXN]

标志的命名: flag
如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int isPrime(int n){
    int flag = 0;
    for(int i = 2; i * i <= n; ++ i){
        if(n % i == 0){
            flag = 1; // 表明找到因子
            break;
        }
    }
    if(flag){
        // 如果有因子
        return 0;
    }else{
        return 1;
    }
}

字符串命名: str1 str2

用英文单词命名: scores[MAXN] students[MAXN]

如果名字中要有多个英文单词,有两种命名方式:

1. 驼峰命名法(camel case)第一个字母小写,之后每个单词的首字母大写:
   thisIsAVeryLongVariableNameForSomeVeryStupidReason
2. 蛇形命名法(snake case)单词和单词之间用下滑线连接
   this_is_a_very_long_variable_name_for_some_very_stupid_reason

两种命名方式均被广泛使用,根据个人习惯选择即可. 作者印象里c语言常用的是蛇形命名法,但不确定

(不推荐,但是比无意义命名好)汉语拼音命名: xueshengfenshu[MAXN]

函数命名:

英文单词命名,尽量动词开头,如:
is_prime get_numbers solve

算法名字命名,如:
dfs dfs prim dijkstra

绝对不能用的命名: mian

代码差错指北

如题,这是随缘更新的指北.

不严谨的统计显示,程序员的工作时间中, 10%用于构思和写代码, 30%用于debug, 60%用于纠结该给变量起什么名字.

那么问题来了, 抢答!! PHP天下第一!!,如何DEBUG才是高效的DEBUG呢?

LOG调试法

打LOG无论是在学习中还是在工作中都是极其重要的DEBUG方式. 1 那么就有人问了,啥是打LOG?

LOG能帮我们:

对程序运行情况的记录和监控；

了解程序的运行状态

总而言之, LOG就是程序运行时输出的帮助我们辨别程序运行状态的输出.

通过LOG看变量的值

这点很显然,程序执行到一半输出变量的值就能知道变量的值是多少. 废话 需要注意的是,不仅仅能打印变量的值,还能打印表达式的值.

举个例子:优秀的X同学在做某道题的时候写出了以下的代码

1
2
3
4
5
6

long a;
scanf("%d",&a); // 注意这里有一个错误: 应该是%ld

if(a==-1){
    执行某些代码
}

他输入了-1之后,发现本应执行的if语句内代码并没有被执行.于是他就在第三行插入了printf("%d",a==-1);,发现输出的值是0,意味着a并不等于-1.意识到 a!=-1 之后,优秀的X同学就意识到了scanf处出现了错误.

通过LOG判断程序执行的位置

看到上面的例子后,各位可能有个疑惑: “X同学是怎么知道程序没有执行if语句内的内容呢?”

(做手势:看看本节标题)你是不是心中浮现了一个玄妙的想法:只要在if语句内输出点东西就好了啊!是不是特别神奇! (夸张脸)

说时迟,那时快,只见X同学飞快的敲下了以下代码

1
2
3
4
5
6
7

long a;
scanf("%d",&a); // 注意这里有一个错误: 应该是%ld

if(a==-1){
    printf("这个东西应该输出的啊???");// 当然并没有输出
    执行某些代码
}

当他按下了神圣的F11键之后, “当场他就懵了”,陷入了沉思.

通过LOG查看递归调用的函数

这点可能课内还没有学到,可以等讲完课后回来复习(观众留存度++)

对于一个递归函数,比如汉诺塔:

1
2
3
4
5
6
7
8
9
10
11

void hanoi(int n, char from, char via, char to) {
    printf("将要从%c通过借助%c移动%d个盘子到%c\n",from,via,n,to);
    if (n == 1)
        move(from, to);
    else {
        hanoi(n - 1, from, to, via);
        move(from, to);
        hanoi(n - 1, via, from, to);
    }
    printf("已经从%c通过借助%c移动%d个盘子到%c\n",from,via,n,to);
}

室友调试法

把室友扥(den)过来,完整的讲述你程序的思路给他听, (不用管室友是否真的在听),一般讲到一半你就会意识到你哪儿错了

小黄鸭调试法

没有室友?找一只小黄鸭放在桌子上给它讲述你的程序思路.

大概每日一题

首先,给各位道个歉.昨天由于沉迷学习忘了更新, 绝对不是忙于抢新题库的一血

那么,

作天的题

题目描述

1
2
3
4
5

本关任务：计算正整数num的各位上的数字之积。
例如：
输入：2583  经过(2x5x8x3) 输出：240
输入：102   经过(1x0x2)   输出：0
输入：136   经过(1x3x6)   输出：18

输入

1

一个数num

输出

1

运算结果(一个整数)

做题思路1

循环,每次取一位,和ans变量相乘.

伪代码:

1
2
3
4
5
6
7

ans = 1
输入num
k = 1
while(num / k != 0):
    ans *= (num/k)%10 // num去掉后面的位数后取最后一位
    k *= 10
输出ans

这种思路的核心在于,设置中间变量k.每次把num除k来去掉尾部多余的位数之后取最后一位累乘.

做题思路2

循环,每次取num的最后一位,和ans变量相乘后去掉最后一位

伪代码:

1
2
3
4
5

ans = 1
读入num
while num != 0:
    ans *= (num%10) // ans乘以num的最后一位
    num /= 10       // 核心: 去掉num的最后一位

这个思路的核心在于,每次取最后一位num用于计算后去掉最后一位.
相比第一个思路的好处是 省略了一个中间变量.

1024特别节目

今天是1024程序员节

不知道能为各位做点什么,
给各位画幅画吧

1
2
3
4

 
  O  
~~~~~
~~~~~

一副海上明月图送给大家

每日一题

公众号新开了个栏目,叫大概每日一题.

那么问题来了,为啥叫大概每日一题呢?

鸽子表情包

今天的题

题目描述:

1

找出具有m行n列二维数组Array的“鞍点”，即该位置上的元素在该行上最大，在该列上最小，其中1<=m,n<=10。

输入:

1

第一行有两个数m和n，下面有m行，每行有n个数。

输出:

1

Array[i][j]=x

做题思路

这道题的思路还是比较清晰的:枚举每一行,寻找这一行里最大的数在第几列,寻找那一列最小的数,看看这一行最大的数是不是这一列最小的数.

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

输入m,n
循环i从0到m-1
    循环j从0到n-1
        读入data[i][j]

循环i从0到m-1
    max=data[i][0]
    pos=0
    循环j从0到n-1
        如果data[i][j] 大于 max
            更新max与pos
    
    flag = 1
    循环j从0到n-1
        如果data[j][pos]小于max
            flag = 0
    如果flag=1 说明data[i][pos]是鞍点
        输出,退出程序
输出none

注意点

在找数组的最小值的时候有两种实现方式:

1
2
3
4
5
6
7
8

int min = 0x70000000;
int pos = -1;
for(int i = 0; i < n;++ i){
    if(min < data[i]){
        min = data[i];
        pos = i;
    }
}

与

1
2
3
4
5
6
7
8

int min = data[0];
int pos = 0;
for(int i = 1; i < n;++ i){
    if(min < data[i]){
        min = data[i];
        pos = i;
    }
}

第一种方式将min设为极大值(或将max设为极小值),第二种方式奖min设为数组第一项的值.

这两种方式都是正确的,要注意的就是

1. 使用第一种方式时设置的极大值一定要很大.
   1. int所能存储的最大值是0x7fffffff,所以对于以上情况把min设置为0x7ffffff是安全的.
   2. 对于要比较min+data[i]和data[i]的大小的时候, min的初值应设置为int所能存储的最大值的一半,以保证min+data[i]仍在int范围内.对于这种情况, 0x3f3f3f3f是一个安全的值.
2. 使用第二种方式一定要把pos变量初始化为0