一般讨论的排序都是内部排序，所谓外部和内部，是针对排序时的条件而言的，内部指所有的数据都可以直接拿到，而外部就是每次只能拿到一部分数据，最典型的现实场景

• 对数组进行排序，整个数组当然都是在内存里的，可以直接拿到
• 而对磁盘数据（比如文件）进行排序，要先把数据读进内存，而且限于内存的大小，内存中在某一时刻只能有一部分数据

外部排序的限制在于从磁盘读数据是一件很麻烦的事情，因为在磁盘上的数据存储并不是和在内存中那样是连续的，有个地址就可以直接访问，而是分散的，而且每次找一个数据都得寻道，旋转，再数据传输，排序的结果还得再写回磁盘，实际磁盘I/O的时间会远超在内存上操作的时间，所以要尽可能减少对磁盘的访问，I/O次数也成为外部排序时主要考虑的代价

这时候可以选什么排序算法来进行外部排序呢，很明显，选择排序，冒泡排序，这种每一趟都得把数据基本过一遍的算法是不行的，实际上可以想到，归并排序是个不错的选择

例如，一个有2000个记录的文件，每个磁盘块可以容纳125个记录，首先通过8次内部排序得到8个初始归并段R1到R8，每个段有250个记录，然后对该文件做两两归并，直至得到一个有序的文件

把内存分出三个缓冲区，两个输入一个输出，从R1和R2分别读一个磁盘块到输入缓冲区，归并到输出缓冲区，钥匙其中一个缓冲区空了就再读一个，然后把输出写到磁盘，再归并R3和R4，R5和R6，R7和R8，分别得到R1’-R4'

Prim Algorithm

How does it run?

• Choose an arbitrary vertex $v$ and let $S=\{v\}$
• Choose a vertex $u$ closest to $S$ and add it into $S$ and record the corresponding edge
• go on until all vertices are in $S$
• The recorded edges and $S$ constructs a Minimum Spanning Tree

Let $G=(V,E,W)$ be a weithted connected graph and has $n$ vertices.

一些常用的函数:

int socket(int domain, int type, int protocol);

domain可选值:

定理描述

任一次数 $\ge 1$ 的复多项式在复数域中至少有一个根。

Gauss 的证明方法

代数基本定理的第一个实质性证明是由 Gauss 在他的博士论文中给出的。

设 $f(x)\in \mathbb{C}[x]$ 且 $\partial (f(x))\ge 1$，那么 $f(x)$ 有一次因式，设为 $x-{\alpha }_1$，令 $x-{\alpha }_1$在 $f(x)$ 中是 $l_1-$ 重因式，则 $(x-{\alpha }_1{)}^{l_1}|f(x)$，令

Introduction

This is bold text, and this is emphasized text.

Test for Equations

This is an inline equation: $a+b=?$

This is a display equation:

Test for Code Block