https://y.music.163.com/m/song/4143723/

>如何定义计算机科学

在克莱姆森国王理智而矜持的歌声中，让我们开始计算机的旅程。

计算机学最初被称为“计算学”，然后是“计算机技术”，然后才是“计算机科学”。这是因为计算机科学最初的目的就是更好地做计算。而当一个巨聪明的人发明了计算机后，大家发现利用这种通电的可爱小玩意才能最好地做计算。

计算机的应用很广泛，因为计算的应用很广泛，很少有事情不涉及到：就是小学生写作文，也得算字数吧？

因为计算机的应用如此广泛，所以计算机的使用涉及各个不同的领域，可以说几乎所有的理科都涉及到计算机。不可避免地，计算机学需要各种方面的知识：工程，通信，生物，物理...哦，等等，不能忘了最重要的数学。

不仅因为计算机的应用面广泛，使用计算机本身就需要很多知识，大体可以分为两种：

>如何计算

>如何使用计算机这种工具

>如何计算

著名的数学家，计算机学家迪克斯特拉（Dijkstra）曾经说过：“计算机之于计算机科学，就像天文望远镜之于天文学（Computer Science is no more about computers than Astronomy is about telescopes）。”

迪克斯特拉的意思是，计算机科学不需要计算机。有了计算机科学的知识，你不需要计算机也可以进行计算，只不过速度小小地慢个几十亿倍罢了。

他说的实际上就是如何计算的知识。一些放之四海而皆准，不根据你用的是人脑还是计算机而改变的计算理论知识，我们可以称其为理论计算机科学。举个实际的例子，a乘b就是a加上a，一共加b-1次。这种计算的结果不会因为使用的计算工具改变而改变。实际上，乘法就是一种最早提出的算法（Algorithm）。

在数学家的眼里，理论计算机科学就是数学的附庸。他们觉得“离散数学”（理论计算机科学很重要的一部分）就是一个不良定义词汇，可以直接归类为数学分析的子领域。某种程度上来说他们的想法是正确的。

但为了保住我身为一个计算机壬微不足道的自尊心，我会大声反驳这种观点，BB一些算法，形式语言之类的专有名词，然后搬来图灵等大仙用以佐证...扯远了，我们最后看看克莱姆森国王怎么说吧。

克莱姆森国王说：“知识真是致命的朋友（Knowledge is a deadly friend）。”

本串串首的图片为克莱姆森国王首专封面，发布于1969年，由一名乐队成员的程序员朋友以自己的脸作为母版绘制而成。那位程序员出生于1946年，于1970年死于心脏病发作，享年24岁。

知识是致命的朋友，希望你做好准备，还好这里有摇滚作为壮胆。

https://y.music.163.com/m/song/20045632/
>如何使用计算机这种工具

很多肥哥进这个串的目的可能是学习这个，很抱歉在前面唠叨了一堆影响你有效率地找到这里。

专职使用计算机工具的职业中，最常见的那个就叫做程序员。程序员吸收甲方的要求，然后将其打出来，像是把甲方的想法翻译成了一种（常常是带屎的）特殊的语言。这种语言可以让计算机看懂并执行。

人的话语是模糊的，而计算机的话语是清晰的，没有歧义的。从某种角度来看，计算机的话语是人通过各种理论所创造的，“直指大道”的话语。而人的语言则是自然所创造的语言，效率更低，但咱有文化。

说了这么多，但说出计算机的话语，也就是编程，只是使用计算机这种工具微乎其微的一小部分，就像你学语文的时候不会把“能说中文”看作语文这门学科的主要内容一样。

使用计算机这种工具还需要工程学的知识，每个程序员的键盘都是一把铲子，而程序员试图铲出一栋美丽的建筑。正如建筑工人不会把楼造的七扭八扭浪费使用者的时间一样，程序员也不会把代码写的需要很长时间来运行；也正如建筑工人不会把楼造的巨大无比一样，程序员不会把代码写的很长很大，并且让代码在运行时占用太多空间。

小与美不可兼得，时间和空间的完美利用也不可兼得，计算机工程和工程学一样，是妥协的艺术。

在搭建程序这栋建筑时，我们也需要关心建筑之间的一路顺风（po在这里尽可能地尝试用一个词来表示畅通无阻和安全）。一样的道理，计算机科学需要通信，密码学，网络安全等学科。一场阔佬的派对可能需要租用众多建筑，多线程的知识同理被需要。数据库，人工智能，电路...天哪，我们要的知识太多了。

许多利用计算机的技巧捆在一起，被我们称为“实践计算机科学”。

理论计算机科学就像Elephant Talk这首歌里用吉他模拟出来的象语，纯净，自然。而实践计算机科学则是人聒噪的话语，杂糅，充满沉淀。但不论如何，你没法用象语和人沟通，而人的话语也自有其有趣之处。

但在用计算机的语言沟通的时候，请在你心中培养数学的语言。实践计算机科学是外功，理论计算机科学是内功，练武不练功，到头一场空（赛博英雄传并感）。两者都学才是合理的，自然的，有效率的。

最后，我发誓接下来不会再多推这些莫名其妙的前卫摇滚了，肯定整老少咸宜的。

https://y.music.163.com/m/song/445702291

迟来的Q&A：
>这个串的目标群体是谁？
对计算机有兴趣的人，想要成为程序员的人，不知道今天听啥的摇滚爱好者，闲的没事干随便翻翻的人，想要巩固自己知识看看别人见解的人，和我自己。因为把我所学的知识写出来也是一种修行，若是大家能从我的文章里多挑点错，让我发现自己的漏洞，那就更好了。

>为什么是计算机和摇滚？
po是计算机从业者，也是摇滚爱好者。在学习计算机与听摇滚的过程中，po发现计算机和摇滚非常相似：
- 计算机发迹于50年代，摇滚也发迹于50年代
- 计算机是对于知识的表达，摇滚是对于情感的表达
- 摇滚中有很多主题有关机器人和计算机，计算机...也可以用来放摇滚
- 计算机由1和0构成，摇滚里也有很多1和0，比如说图里的这两位，他们曾经合唱过Under Pressure，但在感情上应该没有什么交叉
数字论证免了，总之Q.E.D

>这是个大工程吧，你打算写多久
不好说，直到我鸽

https://y.music.163.com/m/song/19703271

最后，学习计算机并不是什么需要沐浴更衣，集中思绪之类很复杂前摇的事情。如果你想要学习计算机，不要找理由了。

应该开始学习的时间是Right Now。

https://y.music.163.com/m/song/471969699

>1与0

每个人都知道1和0是计算机的根本，或者更严谨一点，二进制是计算机的根本。

进制是用有限的数字符号来表示所有的数值，二进制是用两个数字符号来表示数字。这两个符号是最小的自然数0，和第二小的自然数1。逢二进一，这就是二进制的规则。

https://blog.csdn.net/qi_ming88/article/details/77677305

↑这是二进制的基本加减乘除规则。其实二进制和十进制本质上没有区别，只是换了个方式表示数字罢了。

例如二进制数字101等于十进制数字5，二进制数字1100等于十进制数字12，101*1100（二进制）=5*12（十进制）=60（十进制）=111100（二进制）

https://zhuanlan.zhihu.com/p/75291280?utm_id=0

↑这是二进制和十进制互相转换的方法

我们可以人为地赋予1和0意义，例如我们可以认为1代表“有”，0代表“无”，因为任何数乘1得自身，乘0得0；可以认为1代表“正确”，0代表“错误”；1甚至可以代表We Will Rock You里的跺脚，0代表拍手。这样我们可以用110110来“编码”We Will Rock You这首歌。

编码（Encoding）就是将一种信息写为一种特定的格式。例如将音乐写作二进制一样。这样，二进制就可以用来表示信息。

我们还可以用数字来表示信息。例如我们可以用（十进制数字）0，1，2，3，4来表示头，左手，右手，左脚，右脚。这5个十进制数字转化成二进制就是0，1，10，11，100。根据这种表示信息的规则，我们在看见100时，可以通过既定的表示规则反向获取其代表的东西---右脚。

如何表示多个东西呢？一般来说，我们使用一个到多个字节来表示一样东西。

一个字节含八个比特，一个比特（bit，binary digit）含一个1或者0。

这是一个比特：1

这是一个字节：10001110

那么先左脚，再右脚就可以表示为00000011 00000100。我们似乎为每个肢体浪费了5个比特...不过为了秩序，这是可以接受的，如果不能接受，可以修改规则，让我们将三个比特作为一个单位，这样011 100就可以表示左脚然后右脚。但是11 100不行，因为两个数字之间的间隔是我为了方便加的。没有固定n个比特为一个单位的规则，我们不知道11100代表什么。

在计算机这个实体中，1和0被表示为电流。当电流通过一个管道的时候，如果我们检测到一段时间的电压较高，我们称其为高电平，并认为我们收到了一个1。当一段时间电压低时，我们收到了一个0。

特殊的电路结构会吸取两条流入的电流，并根据其电平高低，输出一条高电平或者低电平的电流。从抽象意义上来看，就是输入两个可以为1或者0的数，然后输出一个可以为1或者0的数。

我们把这种吸收两条电流，流出一条电流的结构叫做逻辑门（logic gate）。

https://s2.shizhz.me/s2e2

↑这是一个简单的逻辑门介绍

许许多多的逻辑门拼凑在一起，可以形成复杂的结构。例如一个叫做累加器的结构，可以实现输入两个数，每个数由很多个比特组成，输出一个由很多比特组成的数，这个输出的数是输入的两数之和（具体结构自行百度）。

实际上，逻辑门在被发明前，输入两个1或0然后输出1个1或0的运算规则就已经被发明了，它叫做布尔运算（boolean operation）。这并不是什么很值得惊讶的事情，毕竟根据输入的两个二进制数字的不同来输出不同的数字，只有16种不同的输出规则。若假定两个输入符合交换律，那么只有8种。如果排除掉无意义的输出规则（不管输入啥，都输出1/都输出0），那么只有6种。如果假设输出正好相反的规则为1种规则，那么只有3种。这三种规则是“与”（AND），“或”（OR）和“异或”（XOR）。

上面的种类数字是哪里来的？请百度布尔运算，百度真值表，然后自行思考一下。

总而言之，布尔运算是二进制数字除了加减乘除以外还拥有的一种特殊运算规则。放到实际中，可以用逻辑门这种电路单元来模拟。

>为什么计算机用二进制？

计算机使用二进制的一个原因是在设计电路的时候可以运用布尔运算的理论，并将1和0看作“是”和“否”这两种传统逻辑学中符合“排中律”的逻辑。

但这并非是其全部原因。

https://www.zhihu.com/question/314924440?utm_id=0

↑根据这个证明，我们可以证明出以自然常数e作为进制时，计算机处理储存的信息的效率最高。但e进制在计算机中难以从底层实现，也不符合人类的普遍认知，难以让人接受。所以我们使用二进制或者三进制。实际上，苏联曾经使用过三进制来建立计算机，但是苏联没了，所以我们还是用二进制计算机。

>>No.60417637
哦对了，还有一种特殊的运算叫做取反（NEG），只接受一个输入。输入1（高电平电流）时，它输出0（低电平电流）。输入0时，它输出1。

正是有了这个运算，我们才能把6种不同的运算缩减到3种。

比如说定义AND运算：
输入1和1，输出1
输入1和0，或者0和1，输出0
输入0和0，输出0

那么输出正好和它相反的运算（NAND）为：
输入1和1，输出0
输入1和0，或者0和1，输出1
输入0和0，输出1

这个运算就相当于先AND再NEG，就不需要专门定义为特殊的运算了。

https://y.music.163.com/m/song/3424884

>计算机本质与抽象化

计算机是做什么用途的？简单来说，对计算机输入数据，计算机处理数据，计算机输出数据。这就是计算机的本质。

输入和输出数据的过程根据计算机的不同而不同，例如通过键盘可以输入键位信息，而通过显示屏可以输出图像信息。

处理数据的过程极为复杂。从物理的角度，无数电流流经电路，电平不断变化，这就是数据的处理。从数学的角度，计算机根据指令对数据进行有条件的，存在循环的，会终止的更改，使其变为我们想要的样子。从软件工程的角度，无数底层指令在我们输入高级编程语言时被一齐使用，以更改一个或多个存储于某处的数字（我们称其为变量）。

为了不让我们在思考数学公式时还要陷于对于用什么编程语言的思考，或者在编程时还要进行对于逻辑门中电平会怎样流动的回想，我们引入了一种叫做“抽象化”的东西，以屏蔽不必要的细节。

抽象化，就是把一个现实存在的，有复杂机理的东西封装（encapsulate）为不透明的黑盒，而我们没必要透过黑盒去了解其原理，也能使用这个黑盒。

计算机本身就是一个巨大的黑盒。一个人不需要懂计算机有啥零件，也可以流畅地使用计算机。这个人不需要知道什么是累加器，也可以在计算机上进行加减乘除运算。

哪怕是一个资深的软件工程师，也可以选择放弃了解一个程序的基本原理，只要知道输入一样数据，对应的输出应该是什么就可以。

那么，一个程序员可以在不知道计算机基本原理的情况下进行编程吗？

我的回答是，可以，但仅限于可以。缺乏了对于各种数学和工程原理的认知，一个程序员在遇到深奥问题时不知道如何解决。更重要的是，缺乏了基础知识的根基与基础知识所代表思想的指引，一个程序员没法更进一步地学习。

学习是计算机相关从业者很重要的一环。IEEE将“终身学习”作为软件工程师应有的品质。计算机相关的理论很容易化为实际的程序，所以计算机的发展很快，跟不上发展的节奏就会被远远落下。

抽象化是一道隐藏着智者的高墙。你能听见来自墙的另一边的声音，却不知道那是谁传出的，就像平克弗洛伊德的迷墙一样。对于未知的恐惧，是否能激励你学习各种原理呢？

https://y.music.163.com/m/song/19553390

>算法

算法，Algorithm，顾名思义，即计算的方法。在计算机学的意义下，算法接受输入，进行计算，然后输出。与“计算机”这种概念不同的是，每个算法都是为了一种设计算法时就预先定下的理念或者目的所创造的，也就是说，其目的性很强。而计算机可以用来干繁多的事物。

用个粗鲁的比方：榨汁机和人都需要吃水果，但榨汁器有着将水果转化为果汁的目的，而人广泛来说没有这么明确的目的。

算法在数学意义上可以理解为一种函数，function。Function这个词本身就有功能的意思。举个例子，加法是一种算法，其接受两个变量（不要忘了，变量是存储于某处的数据，之后会有更加明确的定义），输出一个数字，那个数字是变量中两数之和。

就像把一个盒子（变量）里的苹果（数据）和另一个盒子（变量）里的香蕉（数据）同时放进“乘法”这种榨汁机里，它们会变成处理好的果汁（数据）。别忘了再拿个杯子（变量）把果汁（数据）装进去。

我们写作：
c←x(a,b)

其中x指代乘法，a，b与c为变量。a与b为输入，箭头符号指赋值，即让输出的数字被装到c中，或者说更改c的内容，使其与输出的数字相同。这样，我们想要这个数字的时候就可以问c要。

为了写法简便，我们用等于号（=）来替代箭头符号，此时的等于号表示赋值而不是相等。

也就是，c=x(a,b)

乘法这种算法用x(a,b)的形式不符合我们的数学认知，所以我们可以简写为a*b，即c=a*b。

这代表使用算法将a与b相乘，将算法的返回值（即算法输出的那个值）赋值给c。

而乘法的实现原理，是将a与b的每一位相乘，将得到的结果在进位后相加。如果不知道二进制乘法是怎么进行的，建议先自行学习二进制乘法。大多数情况下用不到，但身为计算机系不会这个有点丢人，而且终究还是有用的。

好好珍惜这个简单的算法，一般的算法不会这么简单。

一个人的脑中藏着无数个变量，而这些变量在神经元的电信号传播中不断变换。我们是藏在变量之中的游魂。

又如同马克思曾经说过的，“一切已死的先辈们的传统，像梦魇一样纠缠着活人的头脑”。我们在潜移默化之中，已经被文化传统赋予了一些先辈的值。

https://y.music.163.com/m/song/3955886

算法是计算机学中我最喜欢的一部分：优雅，美丽，包含着数学的纯粹和计算机的伟力。在学习算法的过程中，你会接触的大数远远大过世界上所有原子数量的总和，你会遇到的计算次数轻易超出群星之数。你会看见均称美丽的树与图。算法是计算机的灵魂。当学习算法时，请试图保持Maria一样的热情。

我很久没关心算法的教科书更新了。如果想要学习算法，我会推荐比较老的《算法导论（Introduction to Algorithms）》。

但这里还是简单地解释一下算法这种研究的目的和意义。在了解算法之前，请确保你有一些基本的函数和统计学知识。例如什么是“期望值”，什么样的函数比什么样的函数增长更快。

天道无情。对于世界来说，没有聪明的东西，没有愚蠢的东西。一切方法都只是方法。

但对于一个内卷严重的人类社会来说，这个世界上存在“笨方法”和“聪明方法”，这是大家都知道的事情。

算法是对于一种问题提出的，那么我就举一个简单的问题：排序问题。这个问题要求输入一串数字，例如9，5，2，7（注意，一串数字也可以是一个输入，这一点之后会详细说明，但结合“许多字节可以存放许多个数据”的说法，你们应该可以初步理解）；然后输出从小到大排列后的数字，也就是2，5，7，9。

那么，有什么笨方法可以进行这样的排序呢？科学家能想到的（想一个笨方法也需要聪明的脑袋），最笨的方法是将数字随机打乱，然后从前往后确认一遍这串数字是否以从小到大排列，确认的方法是从第二个数开始，比较第n个数和第n-1个数，如果第n个数据比第n-1个数小，那么说明并没有排列好，停止检查，重新打乱，再次检查，直到排列好。

按平均期望来说，随机打乱n个数，假设这些数都不相同，打乱后正好排好序的可能性是1/(n!)，也就是说平均n!次打乱之后可以得到一次正好排列好的。别忘了我们每次打乱顺序之后都要检查一遍是否排列好。假设每次检查都要比较n/2次（实际上大多数情况下比这个少，取决于数的分布规律），那么我们平均需要比较n/2*(n!)次。

但是如果运气很好，理论上来说我们只要打乱一次就能获得排列好的数字。此时只需要1次打乱数字，n/2次比较大小（运气好不代表我们可以省略比较大小的过程，算法可不知道自己运气好，它只会执行它被要求做的事情）。

但如果运气最差，那么我们在有限次打乱中永远获得不了排列好的数字，因为这种可能性是存在的：m次打乱获得不了排列好的数字的可能性是(1-1/(n!))^m。仅当m趋向于无限时，这个可能性趋向于0，也就是我们一定能获得排序好的数字。

也就是说，这个算法平均情况下大概需要进行n!次打乱和n/2*(n!)次比较，最好情况下约需要进行1次打乱和n/2次比较，最差情况下需要无限次打乱。

我们说这种算法是不明智的，我们不会使用这种算法，是因为我们进行了类似于上述的分析，发现它花费的计算时间理论上来说非常多，不值得我们使用。

这种算法的名字叫做猴子算法，灵感出自猴子莎士比亚打字机。或者叫它Bogosort也可以，sort是排序的意思，Bogo是这种算法的名字。在常规情况下，这种排序方式就是浪费资源。但在量子计算机的环境下，这种算法颇有启发性。

>>No.60436181
补充一点，n是大于1的正整数，否则只有一个数的列表必定是排序好的（或者必定是没有排序好的，反正没有研究的价值）

https://y.music.163.com/m/song/20045638

在介绍一个优美的好方法（并不是最好）之前，我们得先简单地了解一下算法界常用的，用于评估一个算法好不好的指标。

这个评估指标被称作复杂度。我们会根据算法在消耗时间，占用空间方面的大小和输入数据的大小的比例来判断这个算法好不好用。我们还会根据算法的最优表现（对于n个输入，理论最短结束的时间或最小花费的空间），最差表现和平均表现（期望值表现）来判断复杂度。

关于复杂度的定义，请参阅算法导论，我记得这本书的很前面就有这个定义。

在你了解什么是复杂度之后，我会简单地介绍什么是数据类型和数据结构。

对于计算机来说，一切都是0和1的数据，正如对世界来说，一切都是基本粒子。

但是粒子的组合也有不同的性状，例如常温下是液体的水和常温下是固体的铁是不一样的。数据亦然。数据的性状由其用途分类。根据用途不同，我们可以分出类似于这些的数据类型：

- 整数（int）：可以用于表示“个数”
- 布尔值（boolean）：仅有两种布尔值：正确与错误，用于表示“是否”的判断
- 字符（char）：单个的字符，如“a”或者“♡”，一般来说算法中仅考虑英文字符就足够了。字符本质上是一个代表了字符的数字（想想二进制代表不同肢体的例子）
- 列表（array）：一个收纳了单个或多个数据类型的数据的集合，根据用途不同，定义不同。例如前文的“9，5，2，7”就是一个只存放整数的列表。列表中的每一个东西被称为它的元素（element）。在某些编程语言的定义下，列表甚至可以有无限个元素，但同一时间只能取出有限个元素
- 字符串（string）：仅存放字符的列表。
...

对于上述数据类型中的每一个，我们都有一些独特的操作。例如对于整数，我们可以加减乘除；对于列表，我们可以增加元素，修改元素，删除元素，引用元素（即获取一个元素的值）等。

也正像我们可以通过创造工具的方式利用外物来代替自身来作业，我们可以赋予数据类型特殊的意义，以使其成为一种稳定的结构，即数据结构。这种结构有两个作用：

>方便我们使用
包括方便我们可视化，理解，提出相关理论，分析，利用和转化。

>作为算法的前提
一些算法可以简单地解决难题，是因为其输入是一种稳定的，有可以被利用的独特性质的数据结构。

事实上，一些睿智的学者甚至证明了某些应用于不同数据结构的难题可以互相转化（reduction）。PNP问题的提出就利用到了一些转化。

数据结构需要维护。当数据结构发生变化的时候，我们需要进行一些操作来使其性质不发生变化，就像你不能把随便什么东西随意扔在你的桌子上，然后声称它还是被整理好的桌子。

接下来的排序算法中，我用到“列表”这种数据类型，和“被排序好的列表”这种数据结构。

听一听Discipline，它会让你感受到变化与秩序的伟力。

https://y.music.163.com/m/song/20045638

在介绍一个优美的好方法（并不是最好）之前，我们得先简单地了解一下算法界常用的，用于评估一个算法好不好的指标。

这个评估指标被称作复杂度。我们会根据算法在消耗时间，占用空间方面的大小和输入数据的大小的比例来判断这个算法好不好用。我们还会根据算法的最优表现（对于n个输入，理论最短结束的时间或最小花费的空间），最差表现和平均表现（期望值表现）来判断复杂度。

关于复杂度的定义，请参阅算法导论，我记得这本书的很前面就有这个定义。

在你了解什么是复杂度之后，我会简单地介绍什么是数据类型和数据结构。

对于计算机来说，一切都是0和1的数据，正如对世界来说，一切都是基本粒子。

但是粒子的组合也有不同的性状，例如常温下是液体的水和常温下是固体的铁是不一样的。数据亦然。数据的性状由其用途分类。根据用途不同，我们可以分出类似于这些的数据类型：

- 整数（int）：可以用于表示“个数”
- 布尔值（boolean）：仅有两种布尔值：正确与错误，用于表示“是否”的判断
- 字符（char）：单个的字符，如“a”或者“♡”，一般来说算法中仅考虑英文字符就足够了。字符本质上是一个代表了字符的数字（想想二进制代表不同肢体的例子）
- 列表（array）：一个收纳了单个或多个数据类型的数据的集合，根据用途不同，定义不同。例如前文的“9，5，2，7”就是一个只存放整数的列表。列表中的每一个东西被称为它的元素（element）。在某些编程语言的定义下，列表甚至可以有无限个元素，但同一时间只能取出有限个元素
- 字符串（string）：仅存放字符的列表。
...

对于上述数据类型中的每一个，我们都有一些独特的操作。例如对于整数，我们可以加减乘除；对于列表，我们可以增加元素，修改元素，删除元素，引用元素（即获取一个元素的值）等。

也正像我们可以通过创造工具的方式利用外物来代替自身来作业，我们可以赋予数据类型特殊的意义，以使其成为一种稳定的结构，即数据结构。这种结构有两个作用：

>方便我们使用
包括方便我们可视化，理解，提出相关理论，分析，利用和转化。

>作为算法的前提
一些算法可以简单地解决难题，是因为其输入是一种稳定的，有可以被利用的独特性质的数据结构。

事实上，一些睿智的学者甚至证明了某些应用于不同数据结构的难题可以互相转化（reduction）。PNP问题的提出就利用到了一些转化。

数据结构需要维护。当数据结构发生变化的时候，我们需要进行一些操作来使其性质不发生变化，就像你不能把随便什么东西随意扔在你的桌子上，然后声称它还是被整理好的桌子。

接下来的排序算法中，我用到“列表”这种数据类型，和“被排序好的列表”这种数据结构。

听一听Discipline，它会让你感受到变化与秩序的伟力。

>>No.60447359
说实话，关于数据结构和数据类型的定义我有些记不清了，如果有问题的话请告诉我，非常感谢

https://y.music.163.com/m/song/18860373

那么，我开始介绍归并排序（Mergesort），包括其算法的运作机制，原理，具体实现，改进方案，复杂度与缺点。

首先，为了普适性，我们拿的例子是一个仅包含数字的列表：[1.0, 3.1, 2.5, 5.6, 0.7]。

“[”代表列表的开始，“]”代表其结束，其中每一个被逗号分割的数字都是一个该列表的元素。

归并排序的运行机制如下：
将列表从中间切开，分成两个列表[1.0, 3.1]与[2.5, 5.6, 0.7]（如果为奇数，我们在这里默认切成(n-1)/2和(n+1)/2的长度，反过来也不会有什么影响）。

为了方便表示，我们写作[1.0, 3.1/2.5, 5.6, 0.7]表示我们在“/”的地方切了一次，分成了两份。

对每个切开后的列表再次切开，例如[1.0, 3.1]将变为[1.0]和[3.1]（注意，[1.0]并不是1.0，前者是含一个元素的列表，后者是一个数字）。

像这样，每次一切为二，在经过三次切割后可得[1.0/3.1/2.5/5.6/0.7]。

这是归并排序的第一步，分开。对于长度为n（含n个元素）的列表，需要花费的时间为lg(n)，其中lg为以2为底的log（不知道什么是log？请自行学习对数）。

分久必合，下一步是合。

在最后一次切割结束后，对于每一轮切割过后的两半，将这两半合起来，以一个保证其从小到大排列的方式。

什么意思？我们还是看刚才的例子。

在最后一轮中，[5.6, 0.7]被拆分为[5.6]，[0.7]。现在我们想以从大到小排列的顺序来合并这两个数，方法很简单：比较一次5.6，0.7的大小。0.7小，所以0.7排前面，5.6排后面，两个列表合并为[0.7，5.6]。

在倒数第二轮（也就是第二轮）中，[2.5]和[5.6, 0.7]被拆分开来。因为我们已经将[5.6, 0.7]在拆分后有序组合，使其变为[0.7, 5.6]，我们需要让2.5先和[0.7, 5.6]中的第一个数0.7比，比0.7大之后再和5.6比。比5.6小，则排5.6前面，变为[0.7, 2.5, 5.6]。

同理，[1.0, 3.1]和[0.7, 2.5, 5.6]比。1.0大于0.7小于2.5，则排在两者之间。3.1因为在1.0后，而0.7小于1.0，所以3.1必定大于0.7，从2.5开始比。比2.5大，比5.6小，所以排两者之间。

列表被排序完成。

被排序的列表带来了秩序。秩序的作用会在下文中提到，在其原理之后，在具体实现之前，但是我们可以先听听Disorder，感受一下无序是多么痛苦的一件事吧。

>>No.60460658
为了普适性的意思是我不只用整数。但实际上，因为和数字有关的操作只有比较大小，用整数和浮点数（就是小数）是一样的

https://y.music.163.com/m/song/4336908

归并排序为何是合理的？为什么这种方法可以将列表从小到大排序？也许许多人已经感觉出来了它的正确性，但是算法不需要感觉，只需要证明。

归并排序由两段重复组成：重复的分解和重复的拼接。分解这个步骤仅提供拼接的顺序，或者说“分解”本身就是对于这种拼接顺序的解释。

我们将这种重复的拼接定义为一种循环（loop）。循环就是不停地做一件事，在这里就是不停地以排序的方式合二为一。在每一个循环中，所有小的列表被两两相拼，使其数量减半，长度翻倍（在假设列表长度是2的次方的情况下）。

在循环的时候，我们希望每个被拼接的列表保持一个特质，那就是它们都是有序的，是从小到大排列的。这种在循环中保持的特性被称为“循环不变式（loop invariant）”。

我们用数学归纳法（如果不知道这个是什么，请先自行了解数论基础，或者试着直接理解以下内容）看看循环不变式在循环中有没有被保持。

在拼接开始的时候，每一个列表仅有一个元素。一个元素的列表我们在这里默认已经从小到大排序，所以循环开始的时候所有列表是有序的。

在每一个循环中，一个列表由两个小列表拼接而成。拼接方式是比较列表中数的大小，大的摆后面，小的摆前面，如前文所叙述的一样。通过这种摆法，我们保证了没有大的数在小的数前面，即列表在循环后依然有序。

循环的结束条件是所有列表归一。因为列表在拼接后始终有序，最后所得的列表也是有序的。

论证完毕，循环不变式成立，循环后可以得到有序列表。

列表在每个循环中慢慢变好，Getting Better all the time。