ZhangYang's Blog

算法

发表于 | 分类于

算法简介

以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳：

输入：一个算法必须有零个或以上输入量。

输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。

有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。

有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

排序算法

中国学生学不好排序算法主要是因为这些算法的名字是外国人取的

体育委员两两摸头法（冒泡排序）

体育老师一指禅法（选择排序）

起扑克牌法（插入排序）

强迫症收扑克牌法（基数排序）

快排

归并排序

堆排序

排序可视化：https://visualgo.net/bn/sorting

伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
a <- {
    '0':4,
    '1':6,
    '2':3,
    '3':2,
    '4':1,
    'length': 5
}
轮数 = 1
左手指向的下标 
while(轮数 < a['length'])
    左手指向的下标 = 0
    while(左手指向的下标 <= a['length'] - 1 - 轮数)
        if a[左手指向的下标] < a[左手指向的下标+1]
            // 什么也不做
        else
            // 交换左右的位置
            t <- a[左手指向的下标]
            a[左手指向的下标] <- a[左手指向的下标+1]
            a[左手指向的下标+1] <- t
        end
        左手指向的下标 <- 左手指向的下标+1
    end
    轮数 <- 轮数 + 1
end
print a
/////////
轮数  左手指向的下标最大值（从0开始）
1        3
2       2
3       1
4       0

冒泡排序算法流程图

image

选择排序算法流程图

image

排序