1.1  Names

       A name should be informative, concise, memorable, and pronounceable if possible.

* Use descriptive names for globals, short names for locals.

Global variables need names long enough and descriptive enough to remind the reader of their meaning.

It's also helpful to include a brief comment with the declaration of each global.

The longer the program, the more important is the choice of good, descriptive, systematic names.

* Be consistent.

Give related things related names that show their relationship and high-light their difference.

* Use active names for functions.

* Be accurate.

1.2 Expressions and Statements

* Indent to show structure.

A consistent indentation style is the lowest-energy way to make a program's structure self-evident.

* Use the natural form of expressions.

Write expressions as you might speak them aloud.

* Parenthesize to resolve ambiguity.

* Break up complex expressions.

* Be clear.

the goal is to write clear code, not clever code.

* Be careful with side effects.

1.3 Consistency and Idioms

* Use a consistent indentation and brace style.

* Use idioms for consistency.

A central part of learning any language is developing a familiarity with its idioms.

* Use else-ifs for multi-way decisions.

1.4 Function Macros

* Avoid function macros.

* Parenthesize the macro body and arguments.

In C++, inline functions avoid the syntactic trouble while offering whatever performance advantage macros might provide.

They are appropriate for short functions that set or retrieve a single value.

1.5 Magic Numbers

Magic numbers are the constants, array sizes, character positions, conversion factors, and other literal numric values that appear in programs.

* Given names to magic numbers.

* Define numbers as constants, not macros.

The C preprocessor is a powerful but blunt tool, however, and macros are a dangerous way to program because they change the lexical structure of the program underfoot. Let the language proper do the work.

* Use character constants, not integers.

* Use the language to calculate the size of an object.

1.6 Comments

* Don't belabor the obvious.

* Comment functions and global data.

* Don't comment bad code, rewrite it.

* Don't contradict the code.

* Clarify,don't confuse.

1.7 Why bother?

The main concerns of programming style: descriptive names, clearity in expressions, straightforward control flow, readability of code and comments, and the importance of consistence use of conventions and idioms in achieving all of these.

Well-written code is easier to read and to understand, almost surely has fewer errors, and is likely to be smaller than code that has been carelessly tossed together and never polished.

The key observation is that good style should be a matter of habit.

Once they become automatic, your subconscious will take care of many of the details for you, and even the code you produce under pressure will be better.

程序设计实践 - 第1章

1. 风格

1.1 名字

一个名字应该是非形式的、简练的、容易记忆的，如果可能的话，最好是能够拼读的。

* 全局变量使用具有说明性的名字，局部变量用短名字。

全局变量的名字应该足够长，具有足够的说明性。给每个全局变量声明附一个简短注释也非常有帮助。

对于长的程序，选择那些好的、具有说明性的、系统化的名字就更加重要。

* 保持一致性。

* 函数采用动作性名字。

* 要准确。名字与其实现保持准确的对应。

1.2 表达式和语句

* 用缩行显示程序的结构。

采用一种一致的缩行风格，是使程序呈现出结构清晰的最省力的方法。

* 使用表达式的自然形式。

表达式应该写得你能大声念出来。

* 用加括号的方式排除二义性。

* 分解复杂的表达式。

* 要清晰。

目标应该是写出最清晰的代码，而不是最巧妙的代码。

* 小心副作用。

像++这一类运算符具有副作用，它们除了返回一个值外，还将隐含地改变变量的值。

1.3 一致性和习惯用法

* 使用一致的缩排和加括号风格。

如果你工作在一个不是自己写的程序上，请注意保留程序原有的风格。

* 为了一致性，使用习惯用法。

在学习一个语言的过程中，一个中心问题就是逐渐熟悉它的习惯用法。

-----------------------------------------------

常见习惯用法之一是循环的形式。

例如：

for(i = 0; i < n; i++)

array[i] = 1.0;

C++或Java里常见的另一种形式是把循环变量的声明也包括在内：

for(int i = 0; i < n; i++)

array[i] = 1.0;

-----------------------------------------------

下面是C语言扫描一个链表的标准循环：

for(p = list; p != NULL; p = p->next)

...

-----------------------------------------------

无穷循环：

for( ;; )

...

或

while(1)

...

-----------------------------------------------

常见的另一个惯用法是把一个赋值放进循环条件里：

while( (c = getchar()) != EOF)

putchar(c);

-----------------------------------------------

一个不好的例子：

char *p, buf[256];

gets(buf);

p = malloc(strlen(buf));

strcpy(p, buf);

问题1.

绝不要使用函数gets，因为你没办法限制它由输入那儿读入内容的数量。这常常会导致一个安全性问题。

问题2.

还有另一个问题：strlen求出的值没有计入串结尾的'\0'字符，而strcpy却将复制它。

习惯写法是：

p = malloc(strlen(buf)+1);

strcpy(p, buf);

或在C++里：

p = new char[strlen(buf)+1];

strcpy(p , buf);

如果这里没有+1，就要当心。

strdup可以使避免上述错误变得更简单。可惜strdup不是ANSI C标准中的内容。

问题3.

上面两个版本都没有检查malloc的返回值。

在实际程序中，对于malloc、realloc、strdup及任何牵涉到存储分配的函数，它们的返回值都必须做检查。

-----------------------------------------------

* 用else-if表达多路选择。

多路选择的习惯表示法形式如下：

if (condition₁)

statement₁

else if (condition₂)

statement₂

...

else if (condition_n)

statement_n

else

default-statement

1.4 函数宏

* 避免使用函数宏。

函数宏最常见的一个严重问题是：如果一个参数在定义中出现多次，它就可能被多次求值。

如果调用时的实际参数带有副作用，结果就可能产生一个难以捉摸的错误。

例子：

某<ctype.h>中：

#define isupper(c) ((c) >= 'A' && (c) <= 'Z')

如果这样调用

while (isupper(c = getchar())),

两次输入的字符c被分别与'A'和'Z'比较了。

C语言标准允许将isupper及类似函数定义为宏，但要求保证它们的参数只求值一次。

如果希望更安全些，那么就一定不要嵌套地使用像getchar这种带有副作用的函数。

改写如下：

while ((c = getchar()) != EOF && isupper(c))

有时多次求值带来的是执行效率问题，而不是真正的错误。

* 给宏的体和参数都加上括号。

如果一个操作比较复杂，或者它很具一般性，值得包装起来，那么还是应该使用函数。

C++提供的inline函数既避免了语法方面的麻烦，而且又可得到宏能够提供的执行效率，很适合来定义那些设置或者提取一个值的短信函数。

1.5 神秘的数 （翻译的有点...）

神秘的数包括各种常数、数组的大小、字符位置、变换因子以及程序中出现的其他以文字形式写出的数值。

* 给神秘的数起个名字。

* 把数定义为常数，不要定义为宏。

C语言预处理程序是一个强有力的工具，但是它又有些鲁莽。

使用宏进行编程是一种很危险的方式，因为宏会在背地里改变程序的词法结构。我们应该让语法去做正确的工作。

（译者注：预处理命令不是C语言本身的组成部分，而是一组辅助成分。这里说"让语言..."，也就是说不要用预处理命令做。）

* 使用字符形式的常量，不要用整数。

例子：

if (c >= 65 && c <= 90)

...

这种写法完全依赖于特殊的字符表示方式。

这样写更好些：

if (c >= 'A' && c <= 'Z')

...

但是，如果在某个编码字符集里的字母编码不是连续的，或夹有其他字母，那么这种描述就是错的。

最好是直接使用库函数。

if(isupper(c))

...

-----------------------------------------------

程序里许多上下文中经常出现的0。如果我们把每个0的类型写得更明确更清楚，对读程序的人理解其作用是很有帮助的。

例如，用 (void*)0 或 NULL 表示C里的空指针值，用'\0'而不是0表示字符串结尾的空字节。

然而在C++里人们都已经接受了用0（而不是NULL）表示空指针。Java里则定义了关键字null。

* 利用语言去计算对象的大小。

不要对任何数据类型使用显式写出来的大小。

例：

 char buf[1024];

 fgets(buf, sizeof(buf), stdin);

对于那些可以看清楚的数组（不是指针），下面的宏定义能计算出数组的元素个数：

#define NELEMS(array) (sizeof(array) / sizeof(array[0]))

1.6 注释

* 不要大谈明显的东西。

注释应该提供那些不能一下子从代码中看到的东西，或者把那些散布在许多代码里的信息收集到一起。

* 给函数和全局数据加注释。

* 不要注释差的代码，重写它。

* 不要与代码矛盾。

当你改变代码时，一定要注意保证其中的注释是准确的。

* 澄清情况，不要添乱。

注释应该在困难的地方尽量帮助读者，而不是给他们设置障碍。

注释很重要，但是也不必盲目注释。

注释是一种工具，它的作用就是帮助读者理解程序中的某些部分，而这些部分的意义不容易通过代码本身直接看到。

1.7 为何对此费心

注重程序设计的风格：具有说明性的名字、清晰的表达式、直截了当的控制流、可读的代码和注释，以及在追求这些内容时一致地使用某些规则和惯用法的重要性。

书写良好的代码更容易阅读和理解，几乎可以保证其中的错误更少。

好风格应该成为一种习惯。

一旦这种习惯变成自动的东西，你的潜意识就会帮助你照料许多细节问题，甚至你在工作压力下写出的代码也会更好。

　　iostream为内置类型类型对象提供了输入输出支持，同时也支持文件的输入输出，类的设计者可以通过对iostream库 的扩展，来支持自定义类型的输入输出操作。

　　为什么说要扩展才能提供支持呢？我们来一个示例。 %CODE{"cpp"}% #include <stdio.h> #include using namespace std;

class Test { public: Test(int a=0,int b=0) { Test::a=a; Test::b=b; } int a; int b; }; int main() { Test t(100,50); printf("%???",t);//不明确的输出格式 scanf("%???",t);//不明确的输入格式 cout<<t<<endl;//同样不够明确 cin>>t;//同样不够明确 system("pause"); } %ENDCODE% 由于自定义类的特殊性，在上面的代码中，无论你使用c风格的输入输出，或者是c++的输入输出都不是不明确的一个表示，由于c语言没有运算符重载机 制，导致stdio库的不可扩充性，让我们无法让printf()和scanf()支持对自定义类对象的扩充识别，而c++是可以通过运算符重载机制扩充 iostream库的，使系统能能够识别自定义类型，从而让输入输出明确的知道他们该干什么，格式是什么。

　　在上例中我们之所以用printf与cout进行对比目的是为了告诉大家，C与C++处理输入输出的根本不同，我们从c远的输 入输出可以很明显看出是函数调用方式，而c++的则是对象模式，cout和cin是ostream类和istream类的对象。

1 iostream: istream 和 ostream

　　我们所熟悉的输入输出操作分别是由istream(输入流)和ostream(输出流)这两个类提供的，为了允许双向的输入／ 输出，由istream和ostream派生出了iostream类。

　　类的继承关系见下图：

iostream库定义了以下三个标准流对象：

1. cin，表示标准输入(standard input)的istream类对象。cin使我们可以从设备读如数据。
2. cout，表示标准输出(standard output)的ostream类对象。cout使我们可以向设备输出或者写数据。
3. cerr，表示标准错误(standard error)的osttream类对象。cerr是导出程序错误消息的地方，它只能允许向屏幕设备写数据。

　　输出主要由重载的左移操作符（<<）来完成，输入主要由重载的右移操作符(>>)完成:

1. >>a表示将数据放入a对象中。
2. <<a表示将a对象中存储的数据拿出。

　　这些标准的流对象都有默认的所对应的设备，见下表：

C++对象名	设备名称	C中标准设备名	默认含义
cin	键盘	stdin	标准输入
cout	显示器屏幕	stdout	标准输出
cerr	显示器屏幕	stderr	标准错误输出

　　上表中的意思表明cin对象的默认输入设备是键盘，cout对象的默认输出设备是显示器屏幕。

　　那么原理上Ｃ++有是如何利用cin／cout对象与左移和右移运算符重载来实现输入输出的呢？

　　下面我们以输出为例，说明其实现原理：

1. cout是ostream类的对象，因为它所指向的是标准设备（显示器屏幕），所以它在iostream头文件中作为全 局对象进行定义。
2. ostream cout(stdout);//其默认指向的C中的标准设备名，作为其构造函数的参数使用。
3. 在iostream.h头文件中，ostream类对应每个基本数据类型都有其友元函数对左移操作符进行了友 元函数的重载。
   • ostream& operator<<(ostream &temp,int source);
   • ostream& operator<<(ostream &temp,char *ps);
   • ... 等等

　　一句输出语句：cout<<"www.cndev-lab.com"；，事实上调用的就是 ostream& operator<<(ostream &temp,char *ps);这个运算符重载函数，由于返回的是流对象的引用，引用可以作为左值使用，所以当程序中有类似cout<<"www.cndev- lab.com"<<"中国软件开发实验室";这样的语句出现的时候，就能够构成连续输出。

　　由于iostream库不光支持对象的输入输出，同时也支持文件流的输入输出，所以在详细讲解左移与右移运算符重载只前，我们 有必要先对文件的输入输出以及输入输出的控制符有所了解。

2 fstream: ifstream 和 ofstream

　　和文件有关系的输入输出类主要在fstream.h这个头文件中被定义，在这个头文件中主要被定义了三个类，由这三个类控制对文件的 各种输入输出操作，他们分别是ifstream、ofstream、fstream，其中fstream类是由iostream类派生而来，他们之间的继 承关系见下图所示。

由于文件设备并不像显示器屏幕与键盘那样是标准默认设备，所以它在fstream.h头文件中是没有像cout那样预先定义的全局 对象，所以我们必须自己定义一个该类的对象，我们要以文件作为设备向文件输出信息(也就是向文件写数据)，那么就应该使用ofstream类。

　　ofstream类的默认构造函数原形为： %CODE{"cpp"}% ofstream::ofstream(const char *filename,int mode = ios::out,int openprot = filebuf::openprot); %ENDCODE%

• filename：　　要打开的文件名
• mode：　　　　要打开文件的方式
• prot：　　　　打开文件的属性

　　其中mode和openprot这两个参数的可选项表见下表：

mode 属性表
ios::app	以追加的方式打开文件
ios::ate	文件打开后定位到文件尾，ios:app就包含有此属性
ios::binary	以二进制方式打开文件，缺省的方式是文本方式。两种方式的区别见前文
ios::in	文件以输入方式打开
ios::out	文件以输出方式打开
ios::trunc	如果文件存在，把文件长度设为0

　　可以用“或”把以上属性连接起来，如ios::out|ios::binary。

openprot 属性表
属性	含义
0	普通文件，打开访问
1	只读文件
2	隐含文件
4	系统文件

　　可以用“或”或者“+”把以上属性连接起来 ，如3或1|2就是以只读和隐含属性打开文件。

实例代码如下： %CODE{"cpp"}% #include using namespace std;

int main() { ofstream myfile("c:\\1.txt",ios::out|ios::trunc,0); myfile<<"中国软件开发实验室"<<endl<<"网址："<<"www.cndev- lab.com"; myfile.close() system("pause"); } %ENDCODE% 文件使用完后可以使用close成员函数关闭文件。

　　ios::app为追加模式，在使用追加模式的时候同时进行文件状态的判断是一个比较好的习惯。

　　示例如下：

%CODE{"cpp"}% #include #include using namespace std; int main() { ofstream myfile("c:\\1.txt",ios::app,0); if(myfile)//或者写成myfile.fail() { cout<<"文件打开失败，目标文件状态可能为只读！"; system("pause"); exit(1); } myfile<<"中国软件开发实验室"<<endl<<"网址："<<"www.cndev- lab.com"<<endl; myfile.close(); } %ENDCODE%

　　在定义ifstream和ofstream类对象的时候，我们也可以不指定文件。以后可以通过成员函数open()显式的把一 个文件连接到一个类对象上。

　　例如：

%CODE{"cpp"}% #include #include using namespace std; int main() { ofstream myfile; myfile.open("c:\\1.txt",ios::out|ios::app,0); if(myfile)//或者写成myfile.fail() { cout<<"文件创建失败,磁盘不可写或者文件为只读!"; system("pause"); exit(1); } myfile<<"中国软件开发实验室"<<endl<<"网址："<<"www.cndev- lab.com"<<endl; myfile.close(); } %ENDCODE% 下面我们来看一下是如何利用ifstream类对象，将文件中的数据读取出来，然后再输出到标准设备中的例子。

　　代码如下： %CODE{"cpp"}% #include #include #include using namespace std; int main() { ifstream myfile; myfile.open("c:\\1.txt",ios::in,0); if(myfile) { cout<<"文件读错误"; system("pause"); exit(1); } char ch; string content; while(myfile.get(ch)) { content+=ch; cout.put(ch);//cout<<ch;这么写也是可以的 } myfile.close(); cout<<content; system("pause"); } %ENDCODE% 上例中，我们利用成员函数get()，逐一的读取文件中的有效字符，再利用put()成员函数，将文件中的数据通过循环逐一输出到标准设备(屏幕) 上， get()成员函数会在文件读到默尾的时候返回假值，所以我们可以利用它的这个特性作为while循环的终止条件，我们同时也在上例中引入了C++风格的 字符串类型string，在循环读取的时候逐一保存到content中，要使用string类型，必须包含string.h的头文件。

我们在简单介绍过ofstream类和ifstream类后，我们再来看一下fstream类，fstream类是由 iostream派生而来，fstream类对象可以同对文件进行读写操作。

　　示例代码如下： %CODE{"cpp"}% #include #include using namespace std; int main() { fstream myfile; myfile.open("c:\\1.txt",ios::out|ios::app,0); if(myfile) { cout<<"文件写错误,文件属性可能为只读!"<<endl; system("pause"); exit(1); } myfile<<"中国软件开发实验室"<<endl<<"网址："<<"www.cndev- lab.com"<<endl; myfile.close();

myfile.open("c:\\1.txt",ios::in,0); if(myfile) { cout<<"文件读错误,文件可能丢失!"<<endl; system("pause"); exit(1); } char ch; while(myfile.get(ch)) { cout.put(ch); } myfile.close(); system("pause"); } %ENDCODE% 由于fstream类可以对文件同时进行读写操作，所以对它的对象进行初始话的时候一定要显式的指定mode和openprot参数。

　　接下来我们来学习一下串流类的基础知识，什么叫串流类？

3 strstream: ostrstream 和 istrstream

　　我们先看看看C++是如何对C风格的字符串流进行控制的，C中的字符串其实也就是字符数组，字符数组内的数据在内存中的位置的 排列是连续的，我们通常用 char str[size]或者char *str的方式声明创建C风格字符数组，为了能让字符数组作为设备并提供输入输出操作，C++引入了ostrstream、istrstream、 strstream这三个类，要使用他们创建对象就必须包含strstream.h头文件。

• istrstream类用于执行C风格的串流的输入操作，也就是以字符串数组作为输入设备。
• ostrstream类用于执行C风格的串流的输出操作，也就是一字符串数组作为输出设备。
• strstream类同时可以支持C风格的串流的输入输出操作。

　　istrstream类是从istream（输入流类）和strstreambase（字符串流基类）派生而 来，ostrstream是从 ostream（输出流类）和strstreambase（字符串流基类）派生而来，strstream则是从iostream(输入输出流类)和和 strstreambase（字符串流基类）派生而来。

　　他们的继承关系如下图所示:

　　串流同样不是标准设备，不会有预先定义好的全局对象，所以不能直接操作，需要通过构造函数创建对象。

类istrstream的构造函数原形如下： %CODE{"cpp"}% istrstream::istrstream(const char *str,int size); %ENDCODE% 参数1表示字符串数组,而参数2表示数组大小，当size为0时，表示istrstream类对象直接连接到由str所指向的内存空间并以\0结尾的 字符串。

　　下面的示例代码就是利用istrstream类创建类对象，制定流输入设备为字符串数组，通过它向一个字符型对象输入数据。代 码如下： %CODE{"cpp"}% #include #include using namespace std; int main() { char *name = "www.cndev-lab.com"; int arraysize = strlen(name)+1; istrstream is(name,arraysize); char temp; is>>temp; cout<<temp; system("pause"); } %ENDCODE% 类ostrstream用于执行串流的输出，它的构造函数如下所示： %CODE{"cpp"}% ostrstream::ostrstream(char *_Ptr,int streamsize,int Mode = ios::out); %ENDCODE% 　　第一个参数是字符数组，第二个是说明数组的大小，第三个参数是指打开方式。

　　我们来一个示例代码： %CODE{"cpp"}% #include #include using namespace std; int main() { int arraysize=1; char *pbuffer=new char[arraysize]; ostrstream ostr(pbuffer,arraysize,ios::out); ostr<<arraysize<<ends;//使用ostrstream输出到流对象的时候,要用ends结束字符串 cout<<pbuffer; delete[] pbuffer; system("pause"); } %ENDCODE% 上面的代码中，我们创建一个c风格的串流输出对象ostr，我们将arraysize内的数据成功的以字符串的形式输出到了ostr对象所指向的 pbuffer指针的堆空间中，pbuffer也正是我们要输出的字符串数组，在结尾要使用ends结束字符串，如果不这么做就有溢出的危险。

4 stringstream

int main() { stringstream ostr("ccc"); ostr.put('d'); ostr.put('e'); ostr<<"fg"; string gstr = ostr.str(); cout<<gstr<<endl;

char a; ostr>>a; cout<<a

system("pause"); } %ENDCODE% 除此而外，stringstream类的对象我们还常用它进行string与各种内置类型数据之间的转换。示例代码如下： %CODE{"cpp"}% #include #include #include using namespace std;

int main() { stringstream sstr; //--------int转string----------- int a=100; string str; sstr<<a; sstr>>str; cout<<str<<endl; //--------string转char[]-------- sstr.clear();//如果你想通过使用同一stringstream对象实现多种类型的转换，请注意在每一次转换之后都必须调用clear() 成员函数。 string name = "colinguan"; char cname[200]; sstr<<name; sstr>>cname; cout<<cname; system("pause"); } %ENDCODE% 接下来我们来学习一下输入/输出的状态标志的相关知识.

5 io_state 输入/输出的状态标志

• goodbit 无错误
• Eofbit 已到达文件尾
• failbit 非致命的输入/输出错误，可挽回
• badbit　致命的输入/输出错误,无法挽回

有两种方法可以获得输入/输出的状态信息。一种方法是通过调用rdstate()函数，它将返回当前状态的错误标记。例如，假如没 有任何错误，则rdstate()会返回goodbit.下例示例，表示出了rdstate()的用法： %CODE{"cpp"}% #include using namespace std;

int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; if(cin.rdstate() == ios::goodbit) { cout<<"输入数据的类型正确，无错误！"<<endl; } if(cin.rdstate() == ios_base::failbit) { cout<<"输入数据类型错误，非致命错误，可清除输入缓冲区挽回！"<<endl; } system("pause"); } %ENDCODE% 　　另一种方法则是使用下面任何一个函数来检测相应的输入/输出状态： %CODE{"cpp"}% bool bad(); bool eof(); bool fail(); bool good(); %ENDCODE%

　　下例示例，表示出了上面各成员函数的用法： %CODE{"cpp"}% #include using namespace std;

int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; if(cin.good()) { cout<<"输入数据的类型正确，无错误！"<<endl; } if(cin.fail()) { cout<<"输入数据类型错误，非致命错误，可清除输入缓冲区挽回！"<<endl; } system("pause"); } %ENDCODE% 如果错误发生，那么流状态既被标记为错误，你必须清除这些错误状态，以使你的程序能正确适当地继续运行。要清除错误状态，需使用clear()函数。 此函数带一个参数，它是你将要设为当前状态的标志值。，只要将ios::goodbit作为实参。

　　示例代码如下： %CODE{"cpp"}% #include using namespace std;

int main() { int a; cin>>a; cout<<cin.rdstate()<<endl; cin.clear(ios::goodbit); cout<<cin.rdstate()<<endl; system("pause"); } %ENDCODE% 通常当我们发现输入有错又需要改正的时候，使用clear()更改标记为正确后，同时也需要使用get()成员函数清除输入缓冲区，以达到重复输入的目 的。

　　示例代码如下： %CODE{"cpp"}% #include using namespace std;

int main() { int a; while(1) { cin>>a; if(cin)//条件可改写为cin.fail() { cout<<"输入有错!请重新输入"<<endl; cin.clear(); cin.get(); } else { cout<<a; break; } } system("pause"); } %ENDCODE% 　　最后再给出一个对文件流错误标记处理的例子，巩固学习，代码如下： %CODE{"cpp"}% #include #include using namespace std;

int main() { ifstream myfile("c:\\1.txt",ios_base::in,0); if(myfile.fail()) { cout<<"文件读取失败或指定文件不存在!"<<endl; } else { char ch; while(myfile.get(ch)) { cout<<ch; } if(myfile.eof()) { cout<<"文件内容已经全部读完"<<endl; } while(myfile.get(ch)) { cout<<ch; } } system("pause"); } %ENDCODE%  

• ofstream: 写操作（输出）的文件类 (由ostream引申而来)
• ifstream: 读操作（输入）的文件类(由istream引申而来)
• fstream: 可同时读写操作的文件类 (由iostream引申而来)

打开文件(Open a file)

对这些类的一个对象所做的第一个操作通常就是将它和一个真正的文件联系起来，也就是说打开一个文件。被打开的文件在程序中由一个流对象 (stream object)来表示 (这些类的一个实例) ，而对这个流对象所做的任何输入输出操作实际就是对该文件所做的操作。

要通过一个流对象打开一个文件，我们使用它的成员函数open()：

void open (const char * filename, openmode mode);这里filename 是一个字符串，代表要打开的文件名，mode 是以下标志符的一个组合：

这些标识符可以被组合使用，中间以”或”操作符(|)间隔。例如，如果我们想要以二进制方式打开文件”example.bin” 来写入一些数据，我们可以通过以下方式调用成员函数open（）来实现：

ofstream file;
file.open ("example.bin", ios::out | ios::app | ios::binary); ofstream, ifstream 和 fstream所有这些类的成员函数open 都包含了一个默认打开文件的方式，这三个类的默认方式各不相同：

只有当函数被调用时没有声明方式参数的情况下，默认值才会被采用。如果函数被调用时声明了任何参数，默认值将被完全改写，而不会与调用参数组合。

由于对类ofstream, ifstream 和 fstream 的对象所进行的第一个操作通常都是打开文件，这些类都有一个构造函数可以直接调用open 函数，并拥有同样的参数。这样，我们就可以通过以下方式进行与上面同样的定义对象和打开文件的操作：

ofstream file ("example.bin", ios::out | ios::app | ios::binary);两种打开文件的方式都是正确的。

你可以通过调用成员函数is_open()来检查一个文件是否已经被顺利的打开了：

bool is_open();它返回一个布尔(bool) 值，为真（true）代表文件已经被顺利打开，假( false )则相反。

关闭文件(Closing a file)

当文件读写操作完成之后，我们必须将文件关闭以使文件重新变为可访问的。关闭文件需要调用成员函数close()，它负责将缓存中的数据排放出来并 关闭文件。它的格式很简单：

void close ();这个函数一旦被调用，原先的流 对象(stream object)就可以被用来打开其它的文件了，这个文件也就可以重新被其它的进程(process)所有访问了。

为防止流对象被销毁时还联系着打开的文件，析构函数(destructor)将会自动调用关闭函数close。

文本文件(Text mode files)

类ofstream, ifstream 和fstream 是分别从ostream, istream 和iostream 中引申而来的。这就是为什么 fstream 的对象可以使用其父类的成员来访问数据。

一般来说，我们将使用这些类与同控制台(console)交互同样的成员函数(cin 和 cout)来进行输入输出。如下面的例题所示，我们使用重载的插入操作符<<：

从文件中读入数据也可以用与 cin的使用同样的方法：

上面的例子读入一个文本文件的内容，然后将它打印到屏幕上。注意我们使用了一个新的成员函数叫做eof ，它是ifstream 从类 ios 中继承过来的，当到达文件末尾时返回true 。

状态标志符的验证(Verification of state flags)

除了eof()以外，还有一些验证流的状态的成员函数（所有都返回bool型返回值）：

• bad() 如果在读写过程中出错，返回 true 。例如：当我们要对一个不是打开为写状态的文件进行写入时，或者我们要写入的设备没有剩余空间的时候。
• fail() 除了与bad() 同样的情况下会返回 true 以外，加上格式错误时也返回true ，例如当想要读入一个整数，而获得了一个字母的时候。
• eof() 如果读文件到达文件末尾，返回true。
• good() 这是最通用的：如果调用以上任何一个函数返回true 的话，此函数返回 false 。

要想重置以上成员函数所检查的状态标志，你可以使用成员函数clear()，没有参数。

获得和设置流指针(get and put stream pointers)

所有输入/输出流对象(i/o streams objects)都有至少一个流指针：

• ifstream， 类似istream, 有一个被称为get pointer的指针，指向下一个将被读取的元素。
• ofstream, 类似 ostream, 有一个指针 put pointer ，指向写入下一个元素的位置。
• fstream, 类似 iostream, 同时继承了get 和 put

我们可以通过使用以下成员函数来读出或配置这些指向流中读写位置的流指针：

• tellg() 和 tellp() 这两个成员函数不用传入参数，返回pos_type 类型的值(根据ANSI-C++ 标准) ，就是一个整数，代表当前get 流指针的位置 (用tellg) 或 put 流指针的位置(用tellp).
• seekg() 和seekp() 这对函数分别用来改变流指针get 和put的位置。两个函数都被重载为两种不同的原型：

  seekg ( pos_type position );
  seekp ( pos_type position );

  使用这个原型，流指针被改变为指向从文件开始计算的一个绝对位置。要求传入的参数类型与函数 tellg 和tellp 的返回值类型相同。

  seekg ( off_type offset, seekdir direction );
  seekp ( off_type offset, seekdir direction );

  使用这个原型可以指定由参数direction决定的一个具体的指针开始计算的一个位移(offset)。它可以是：

  ios::beg	从流开始位 置计算的位移
  ios::cur	从流指针当 前位置开始计算的位移
  ios::end	从流末尾处 开始计算的位移

流 指针 get 和 put 的值对文本文件(text file)和二进制文件(binary file)的计算方法都是不同的，因为文本模式的文件中某些特殊字符可能被修改。由于这个原因，建议对以文本文件模式打开的文件总是使用seekg 和 seekp的第一种原型，而且不要对tellg 或 tellp 的返回值进行修改。对二进制文件，你可以任意使用这些函数，应该不会有任何意外的行为产生。

以下例子使用这些函数来获得一个二进制文件的大小：

二进制文件(Binary files)

在二进制文件中，使用<< 和>>，以及函数（如getline）来操作符输入和输出数据，没有什么实际意义，虽然它们是符合语法的。

文 件流包括两个为顺序读写数据特殊设计的成员函数：write 和 read。第一个函数 (write) 是ostream 的一个成员函数，都是被ofstream所继承。而read 是istream 的一个成员函数，被ifstream 所继承。类 fstream 的对象同时拥有这两个函数。它们的原型是：

write ( char * buffer, streamsize size );
read ( char * buffer, streamsize size );

这里 buffer 是一块内存的地址，用来存储或读出数据。参数size 是一个整数值，表示要从缓存（buffer）中读出或写入的字符数。

缓存和同步(Buffers and Synchronization)

当 我们对文件流进行操作的时候，它们与一个streambuf 类型的缓存(buffer)联系在一起。这个缓存（buffer）实际是一块内存空间，作为流(stream)和物理文件的媒介。例如，对于一个输出流， 每次成员函数put (写一个单个字符)被调用，这个字符不是直接被写入该输出流所对应的物理文件中的，而是首先被插入到该流的缓存（buffer）中。

当缓存被排放出来(flush)时，它里面的所有数据或者被写入物理媒质中（如果是一个输出流的话），或者简单的被抹掉(如果是一个输入流的话)。 这个过程称为同步(synchronization)，它会在以下任一情况下发生：

• 当文件被关闭时: 在文件被关闭之前，所有还没有被完全写出或读取的缓存都将被同步。
• 当缓存buffer 满时: 缓存Buffers 有一定的空间限制。当缓存满时，它会被自动同步。
• 控制符明确指明: 当遇到流中某些特定的控制符时，同步会发生。这些控制符包括：flush 和endl。
• 明确调用函数sync(): 调用成员函数sync() (无参数)可以引发立即同步。这个函数返回一个int 值，等于-1 表示流没有联系的缓存或操作失败。

当我们不断拿 到新的数并想保持已有的数始终有序时，我们用插入排序；当给出的数列已经比较有序，只需要小幅度的调整一下时，我们用冒泡排序。

    我 们来算一下最坏情况下三种算法各需要多少次比较和赋值操作。
    选择排序在第i次选择时赋值和比较都需要n-i次（在n-i+1个数中选一个 出来作为当前最小值，其余n-i个数与当前最小值比较并不断更新当前最小值），然后需要一次赋值操作。总共需要n(n-1)/2次比较与n(n-1) /2+n次赋值。
    插入排序在第i次寻找插入位置时需要最多i-1次比较（从后往前找到第一个比待插入的数小的数，最坏情况发生在这个数是 所有已经取出的数中最小的一个的时候），在已有数列中给新的数腾出位置需要i-1次赋值操作来实现，还需要两次赋值借助临时变量把新取出的数搬进搬出。也 就是说，最坏情况下比较需要n(n-1)/2次，赋值需要n(n-1)/2+2n次。我这么写有点误导人，大家不要以为程序的实现用了两个数组哦，其实一 个数组就够了，看看上面的演示就知道了。我只说算法，一般不写如何实现。学算法的都是强人，知道算法了都能写出一个漂亮的代码来。
    冒泡排 序第i趟排序需要比较n-i次，n-1趟排序总共n(n-1)/2次。给出的序列逆序排列是最坏的情况，这时每一次比较都要进行交换操作。一次交换操作需 要3次赋值实现，因此冒泡排序最坏情况下需要赋值3n(n-1)/2次。
    按照渐进复杂度理论，忽略所有的常数，三种排序的最坏情况下复杂 度都是一样的：O(n^2)。但实际应用中三种排序的效率并不相同。实践证明（政治考试时每道大题都要用这四个字），插入排序是最快的（虽然最坏情况下与 选择排序相当甚至更糟），因为每一次插入时寻找插入的位置多数情况只需要与已有数的一部分进行比较（你可能知道这还能二分）。你或许会说冒泡排序也可以在 半路上完成，还没有跑到第n-1趟就已经有序。但冒泡排序的交换操作更费时，而插入排序中找到了插入的位置后移动操作只需要用赋值就能完成（你可能知道这 还能用move）。本文后面将介绍的一种算法就利用插入排序的这些优势。

    我们证明了，三种排序方法在最坏情况下时间复杂度都是 O(n^2)。但大家想过吗，这只是最坏情况下的。在很多时候，复杂度没有这么大，因为插入和冒泡在数列已经比较有序的情况下需要的操作远远低于n^2次 （最好情况下甚至是线性的）。抛开选择排序不说（因为它的复杂度是“死”的，对于选择排序没有什么“好”的情况），我们下面探讨插入排序和冒泡排序在特定 数据和平均情况下的复杂度。
    你会发现，如果把插入排序中的移动赋值操作看作是把当前取出的元素与前面取出的且比它大的数逐一交换，那插入 排序和冒泡排序对数据的变动其实都是相邻元素的交换操作。下面我们说明，若只能对数列中相邻的数进行交换操作，如何计算使得n个数变得有序最少需要的交换 次数。
    我们定义逆序对的概念。假设我们要把数列从小到大排序，一个逆序对是指的在原数列中，左边的某个数比右边的大。也就是说，如果找到 了某个i和j使得i<j且Ai>Aj，我们就说我们找到了一个逆序对。比如说，数列3,1,4,2中有三个逆序对，而一个已经有序的数列逆序 对个数为0。我们发现，交换两个相邻的数最多消除一个逆序对，且冒泡排序（或插入排序）中的一次交换恰好能消除一个逆序对。那么显然，原数列中有多少个逆 序对冒泡排序（或插入排序）就需要多少次交换操作，这个操作次数不可能再少。
    若给出的n个数中有m个逆序对，插入排序的时间复杂度可以说 是O(m+n)的，而冒泡排序不能这么说，因为冒泡排序有很多“无用”的比较（比较后没有交换），这些无用的比较超过了O(m+n)个。从这个意义上说， 插入排序仍然更为优秀，因为冒泡排序的复杂度要受到它跑的趟数的制约。一个典型的例子是这样的数列：8, 2, 3, 4, 5, 6, 7, 1。在这样的输入数据下插入排序的优势非常明显，冒泡排序只能哭着喊上天不公。
    然而，我们并不想计算排序算法对于某个特定数据的效率。我 们真正关心的是，对于所有可能出现的数据，算法的平均复杂度是多少。不用激动了，平均复杂度并不会低于平方。下面证明，两种算法的平均复杂度仍然是 O(n^2)的。
    我们仅仅证明算法需要的交换次数平均为O(n^2)就足够了。前面已经说过，它们需要的交换次数与逆序对的个数相同。我 们将证明，n个数的数列中逆序对个数平均O(n^2)个。
    计算的方法是十分巧妙的。如果把给出的数列反过来（从后往前倒过来写），你会发 现原来的逆序对现在变成顺序的了，而原来所有的非逆序对现在都成逆序了。正反两个数列的逆序对个数加起来正好就是数列所有数对的个数，它等于n(n- 1)/2。于是，平均每个数列有n(n-1)/4个逆序对。忽略常数，逆序对平均个数O(n^2)。
    上面的讨论启示我们，要想搞出一个复 杂度低于平方级别的排序算法，我们需要想办法能把离得老远的两个数进行操作。

    人们想啊想啊想啊，怎么都想不出怎样才能搞出复杂度 低于平方的算法。后来，英雄出现了，Donald Shell发明了一种新的算法，我们将证明它的复杂度最坏情况下也没有O(n^2) （似乎有人不喜欢研究正确性和复杂度的证明，我会用实例告诉大家，这些证明是非常有意思的）。他把这种算法叫做Shell增量排序算法（大家常说的希尔排 序）。
    Shell排序算法依赖一种称之为“排序增量”的数列，不同的增量将导致不同的效率。假如我们对20个数进行排序，使用的增量为 1,3,7。那么，我们首先对这20个数进行“7-排序”(7-sortedness)。所谓7-排序，就是按照位置除以7的余数分组进行排序。具体地 说，我们将把在1、8、15三个位置上的数进行排序，将第2、9、16个数进行排序，依此类推。这样，对于任意一个数字k，单看A(k), A(k+7), A(k+14), …这些数是有序的。7-排序后，我们接着又进行一趟3-排序（别忘了我们使用的排序增量为1,3,7）。最后进行1-排序（即普通的排序）后整个 Shell算法完成。看看我们的例子：

  3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2  <-- 原数列
  3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2  <-- 7-排序后
  0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9  <-- 3-排序后
  0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9  <-- 1-排序后（完成）

    在每一趟、每一组的排序中我们总是使用插入排序。仔细观察上面的例子你会发现是什么导致了 Shell排序的高效。对，每一趟排序将使得数列部分有序，从而使得以后的插入排序很快找到插入位置。我们下面将紧紧围绕这一点来证明Shell排序算法 的时间复杂度上界。
    只要排序增量的第一个数是1，Shell排序算法就是正确的。但是不同的增量将导致不同的时间复杂度。我们上面例子中 的增量(1, 3, 7, 15, 31, …, 2^k-1)是使用最广泛的增量序列之一，可以证明使用这个增量的时间复杂度为O(n√n)。这个证明很简单，大家可以参看一些其它的资料，我们今天不证 明它。今天我们证明，使用增量1, 2, 3, 4, 6, 8, 9, 12, 16, …, 2^p*3^q，时间复杂度为O(n*(log n)^2)。
    很显然，任何一个大于1的正整数都可以表示为2x+3y，其中x和y是非负整数。于是，如果一个数列已经是2-排序的且是 3-排序的，那么对于此时数列中的每一个数A(i)，它的左边比它大的只有可能是A(i-1)。A2绝对不可能比A12大，因为10可以表示为两个2和两 个3的和，则A2<A4<A6<A9<A12。那么，在这个增量中的1-排序时每个数找插入位置只需要比较一次。一共有n个数， 所以1-排序是O(n)的。事实上，这个增量中的2-排序也是O(n)，因为在2-排序之前，这个数列已经是4-排序且6-排序过的，只看数列的奇数项或 者偶数项（即单看每一组）的话就又成了刚才的样子。这个增量序列巧妙就巧妙在，如果我们要进行h-排序，那么它一定是2h-排序过且3h-排序过，于是处 理每个数A(i)的插入时就只需要和A(i-h)进行比较。这个结论对于最开始几次（h值较大时）的h-排序同样成立，当2h、3h大于n时，按照定义， 我们也可以认为数列是2h-排序和3h-排序的，这并不影响上述结论的正确性（你也可以认为h太大以致于排序时每一组里的数字不超过3个，属于常数级）。 现在，这个增量中的每一趟排序都是O(n)的，我们只需要数一下一共跑了多少趟。也就是说，我们现在只需要知道小于n的数中有多少个数具有2^p*3^q 的形式。要想2^p*3^q不超过n，p的取值最多O(log n)个，q的取值最多也是O(log n)个，两两组合的话共有O(logn*logn)种情况。于是，这样的增量排序需要跑O((log n)^2)趟，每一趟的复杂度O(n)，总的复杂度为O(n*(log n)^2)。早就说过了，证明时间复杂度其实很有意思。
    我们自然 会想，有没有能使复杂度降到O(nlogn)甚至更低的增量序列。很遗憾，现在没有任何迹象表明存在O(nlogn)的增量排序。但事实上，很多时候 Shell排序的实际效率超过了O(nlogn)的排序算法。

    后面我们将介绍三种O(nlogn)的排序算法和三种线性时间的排 序算法。最后我们将以外部排序和排序网络结束这一章节。

    很多人问到我关于转贴的问题。我欢迎除商业目的外任何形式的转贴（论坛、 Blog、Wiki、个人网站、PodCast，甚至做成ppt、pdf），但一定要注明出处，最好保留原始链接。我的网站需要点反向链接才能在网络中生 存下去，大家也都可以关注并且推广这个Blog。我一直支持cc版权协议，因此发现了文章中的问题或者想要补充什么东西尽管提出来，好让更多的人学习到好 东西。我昨天看Blog上原来写的一些东西，居然连着发现了几个错误式子和错别字，好奇大家居然没有提出来。发现了问题真的要告诉我，即使格式有点问题也 要说一下，决不能让它那么错着。另外有什么建议或想法也请说一下，我希望听到不同的声音不同的见解，好让我决定这类文章以后的发展方向。

Matrix67 原创
转贴请注明出处

从零开始学算法：十种排序算法介绍（中）
 本文被华丽的分割线分为了四段。对 于O(nlogn)的排序算法，我们详细介绍归并排序并证明归并排序的时间复杂度，然后简单介绍堆排序，之后给出快速排序的基本思想和复杂度证明。最后我 们将证明，O(nlogn)在理论上已经达到了最优。学过OI的人一般都学过这些很基础的东西，大多数OIer们不必看了。为了保持系列文章的完整性，我 还是花时间写了一下。

    首先考虑一个简单的问题：如何在线性的时间内将两个有序队列合并为一个有序队列（并输出）？

A 队列：1 3 5 7 9
B队列：1 2 7 8 9

    看上面的例子，AB两个序列都是已经有序的了。在给出数据已经有序的情况下，我 们会发现很多神奇的事，比如，我们将要输出的第一个数一定来自于这两个序列各自最前面的那个数。两个数都是1，那么我们随便取出一个（比如A队列的那个 1）并输出：

A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1

    注意，我们取出了一个数，在原数列中删除这个数。删除操作是通过移动队首指针实 现的，否则复杂度就高了。
    现在，A队列打头的数变成3了，B队列的队首仍然是1。此时，我们再比较3和1哪个大并输出小的那个数：

A队列：1 3 5 7 9
B队列：1 2 7 8 9
输出：1 1

    接 下来的几步如下：

A队列：1 3 5 7 9         A队列：1 3 5 7 9         A队列：1 3 5 7 9          A队列：1 3 5 7 9
B队列：1 2 7 8 9   ==>   B队列：1 2 7 8 9   ==>   B队列：1 2 7 8 9    ==>   B队列：1 2 7 8 9     ……
输出：1 1 2              输出：1 1 2 3            输出：1 1 2 3 5           输出：1 1 2 3 5 7

    我希望你明白了这是怎么做的。这个做法显然是正确的，复杂 度显然是线性。

    归并排序(Merge Sort)将会用到上面所说的合并操作。给出一个数列，归并排序利用合并操作在O(nlogn)的时间内将数列从小到大排序。归并排序用的是分治 (Divide and Conquer)的思想。首先我们把给出的数列平分为左右两段，然后对两段数列分别进行排序，最后用刚才的合并算法把这两段（已经排过序的）数列合并为一 个数列。有人会问“对左右两段数列分别排序时用的什么排序”么？答案是：用归并排序。也就是说，我们递归地把每一段数列又分成两段进行上述操作。你不需要 关心实际上是怎么操作的，我们的程序代码将递归调用该过程直到数列不能再分（只有一个数）为止。
    初看这个算法时有人会误以为时间复杂度相 当高。我们下面给出的一个图将用非递归的眼光来看归并排序的实际操作过程，供大家参考。我们可以借助这个图证明，归并排序算法的时间复杂度为 O(nlogn)。

[3] [1] [4] [1] [5] [9] [2] [7]
  \ /     \ /     \ /     \ /
[1 3]   [1 4]   [5 9]   [2 7]
     \   /           \   /
   [1 1 3 4]       [2 5 7 9]
           \       /
       [1 1 2 3 4 5 7 9]

    上图中的每一个“ \ / ”表示的是上文所述的线性时间合并操作。上图用了4行来图解归并排序。如果有n个数，表示成上图显然需要O(logn)行。每一行的合并操作复杂度总和都 是O(n)，那么logn行的总复杂度为O(nlogn)。这相当于用递归树的方法对归并排序的复杂度进行了分析。假设，归并排序的复杂度为 T(n)，T(n)由两个T(n/2)和一个关于n的线性时间组成，那么T(n)=2*T(n/2)+O(n)。不断展开这个式子我们可以同样可以得到 T(n)=O(nlogn)的结论，你可以自己试试。如果你能在线性的时间里把分别计算出的两组不同数据的结果合并在一起，根据 T(n)=2*T(n/2)+O(n)=O(nlogn)，那么我们就可以构造O(nlogn)的分治算法。这个结论后面经常用。我们将在计算几何部分举 一大堆类似的例子。
    如果你第一次见到这么诡异的算法，你可能会对 这个 感兴趣。 分治是递归的一种应用。这是我们第一次接触递归运算。下面说的快速排序也是用的递归的思想。递归程序的复杂度分析通常和上面一样，主定理(Master Theory)可以简化这个分析过程。主定理和本文内容离得太远，我们以后也不会用它，因此我们不介绍它，大家可以自己去查。有个名词在这里的话找学习资 料将变得非常容易，我最怕的就是一个东西不知道叫什么名字，半天找不到资料。

    归并排序有一个有趣的副产品。利用归并排序能够在 O(nlogn)的时间里计算出给定序列里逆序对的个数。你可以用任何一种平衡二叉树来完成这个操作，但用归并排序统计逆序对更方便。我们讨论逆序对一般 是说的一个排列中的逆序对，因此这里我们假设所有数不相同。假如我们想要数1, 6, 3, 2, 5, 4中有多少个逆序对，我们首先把这个数列分为左右两段。那么一个逆序对只可能有三种情况：两个数都在左边，两个数都在右边，一个在左一个在右。在左右两段 分别处理完后，线性合并的过程中我们可以顺便算出所有第三种情况的逆序对有多少个。换句话说，我们能在线性的时间里统计出A队列的某个数比B队列的某个数 大有多少种情况。

A队列：1 3 6         A队列：1 3 6         A队列：1 3 6         A队列：1 3 6         A队列：1 3 6
B队列：2 4 5   ==>   B队列：2 4 5   ==>   B队列：2 4 5   ==>   B队列：2 4 5   ==>   B队列：2 4 5   ……
输 出：               输出：1              输出：1 2            输出：1 2 3          输出：1 2 3 4

    每一次从B队列取出一个数时，我们就知道了在A队列中有多少个数比B 队列的这个数大，它等于A队列现在还剩的数的个数。比如，当我们从B队列中取出2时，我们同时知道了A队列的3和6两个数比2大。在合并操作中我们不断更 新A队列中还剩几个数，在每次从B队列中取出一个数时把当前A队列剩的数目加进最终答案里。这样我们算出了所有“大的数在前一半，小的数在后一半”的情 况，其余情况下的逆序对在这之前已经被递归地算过了。

============================华丽的分割 线============================

    堆排序(Heap Sort)利用了堆(Heap)这种数据结构（ 什么是堆？ ）。 堆的插入操作是平均常数的，而删除一个根节点需要花费O(log n)的时间。因此，完成堆排序需要线性时间建立堆（把所有元素依次插入一个堆），然后用总共O(nlogn)的时间不断取出最小的那个数。只要堆会搞，堆 排序就会搞。堆在那篇日志里有详细的说明，因此这里不重复说了。

============================华丽的分割 线============================

    快速排序(Quick Sort)也应用了递归的思想。我们想要把给定序列分成两段，并对这两段分别进行排序。一种不错的想法是，选取一个数作为“关键字”，并把其它数分割为两 部分，把所有小于关键字的数都放在关键字的左边，大于关键字的都放在右边，然后递归地对左边和右边进行排序。把该区间内的所有数依次与关键字比较，我们就 可以在线性的时间里完成分割的操作。完成分割操作有很多有技巧性的实现方法，比如最常用的一种是定义两个指针，一个从前往后找找到比关键字大的，一个从后 往前找到比关键字小的，然后两个指针对应的元素交换位置并继续移动指针重复刚才的过程。这只是大致的方法，具体的实现还有很多细节问题。快速排序是我们最 常用的代码之一，网上的快速排序代码五花八门，各种语言，各种风格的都有。大家可以随便找一个来看看，我说过了我们讲算法但不讲如何实现。NOIp很简 单，很多人NOIp前就背了一个快速排序代码就上战场了。当时我把快速排序背完了，抓紧时间还顺便背了一下历史，免得晚上听写又不及格。
    不 像归并排序，快速排序的时间复杂度很难计算。我们可以看到，归并排序的复杂度最坏情况下也是O(nlogn)的，而快速排序的最坏情况是O(n^2)的。 如果每一次选的关键字都是当前区间里最大（或最小）的数，那么这样将使得每一次的规模只减小一个数，这和插入排序、选择排序等平方级排序没有区别。这种情 况不是不可能发生。如果你每次选择关键字都是选择的该区间的第一个数，而给你的数据恰好又是已经有序的，那你的快速排序就完蛋了。显然，最好情况是每一次 选的数正好就是中位数，这将把该区间平分为两段，复杂度和前面讨论的归并排序一模一样。根据这一点，快速排序有一些常用的优化。比如，我们经常从数列中随 机取一个数当作是关键字（而不是每次总是取固定位置上的数），从而尽可能避免某些特殊的数据所导致的低效。更好的做法是随机取三个数并选择这三个数的中位 数作为关键字。而对三个数的随机取值反而将花费更多的时间，因此我们的这三个数可以分别取数列的头一个数、末一个数和正中间那个数。另外，当递归到了一定 深度发现当前区间里的数只有几个或十几个时，继续递归下去反而费时，不如返回插入排序后的结果。这种方法同时避免了当数字太少时递归操作出错的可能。

    下 面我们证明，快速排序算法的平均复杂度为O(nlogn)。不同的书上有不同的解释方法，这里我选用算法导论上的讲法。它更有技巧性一些，更有趣一些，需 要转几个弯才能想明白。
    看一看快速排序的代码。正如我们提到过的那种分割方法，程序在经过若干次与关键字的比较后才进行一次交换，因此比 较的次数比交换次数更多。我们通过证明一次快速排序中元素之间的比较次数平均为O(nlogn)来说明快速排序算法的平均复杂度。证明的关键在于，我们需 要算出某两个元素在整个算法过程中进行过比较的概率。
    我们举一个例子。假如给出了1到10这10个数，第一次选择关键字7将它们分成了 {1,2,3,4,5,6}和{8,9,10}两部分，递归左边时我们选择了3作为关键字，使得左部分又被分割为{1,2}和{4,5,6}。我们看到， 数字7与其它所有数都比较过一次，这样才能实现分割操作。同样地，1到6这6个数都需要与3进行一次比较（除了它本身之外）。然而，3和9决不可能相互比 较过，2和6也不可能进行过比较，因为第一次出现在3和9，2和6之间的关键字把它们分割开了。也就是说，两个数A(i)和A(j)比较过，当且仅当第一 个满足A(i)<=x<=A(j)的关键字x恰好就是A(i)或A(j) （假设A(i)比A(j)小）。我们称排序后第i小的数为Z(i)，假设i<j，那么第一次出现在Z(i)和Z(j)之间的关键字恰好就是Z(i) 或Z(j)的概率为2/(j-i+1)，这是因为当Z(i)和Z(j)之间还不曾有过关键字时，Z(i)和Z(j)处于同一个待分割的区间，不管这个区间 有多大，不管递归到哪里了，关键字的选择总是随机的。我们得到，Z(i)和Z(j)在一次快速排序中曾经比较过的概率为2/(j-i+1)。
    现 在有四个数，2,3,5,7。排序时，相邻的两个数肯定都被比较过，2和5、3和7都有2/3的概率被比较过，2和7之间被比较过有2/4的可能。也就是 说，如果对这四个数做12次快速排序，那么2和3、3和5、5和7之间一共比较了12*3=36次，2和5、3和7之间总共比较了8*2=16次，2和7 之间平均比较了6次。那么，12次排序中总的比较次数期望值为36+16+6=58。我们可以计算出单次的快速排序平均比较了多少次：58/12=29 /6。其实，它就等于6项概率之和，1+1+1+2/3+2/3+2/4=29/6。这其实是与期望值相关的一个公式。
    同样地，如果有n 个数，那么快速排序平均需要的比较次数可以写成下面的式子。令k=j-i，我们能够最终得到比较次数的期望值为O(nlogn)。
  
    这 里用到了一个知识：1+1/2+1/3+…+1/n与log n增长速度相同，即Σ(1/n)=Θ(log n)。它的证明放在本文的最后。

    在 三种O(nlogn)的排序算法中，快速排序的理论复杂度最不理想，除了它以外今天说的另外两种算法都是以最坏情况O(nlogn)的复杂度进行排序。但 实践上看快速排序效率最高（不然为啥叫快速排序呢），原因在于快速排序的代码比其它同复杂度的算法更简洁，常数时间更小。

    快速排 序也有一个有趣的副产品：快速选择给出的一些数中第k小的数。一种简单的方法是使用上述任一种O(nlogn)的算法对这些数进行排序并返回排序后数组的 第k个元素。快速选择(Quick Select)算法可以在平均O(n)的时间完成这一操作。它的最坏情况同快速排序一样，也是O(n^2)。在每一次分割后，我们都可以知道比关键字小的 数有多少个，从而确定了关键字在所有数中是第几小的。我们假设关键字是第m小。如果k=m，那么我们就找到了答案——第k小元素即该关键字。否则，我们递 归地计算左边或者右边：当k<m时，我们递归地寻找左边的元素中第k小的；当k>m时，我们递归地寻找右边的元素中第k-m小的数。由于我们 不考虑所有的数的顺序，只需要递归其中的一边，因此复杂度大大降低。复杂度平均线性，我们不再具体证了。
    还有一种算法可以在最坏O(n) 的时间里找出第k小元素。那是我见过的所有算法中最没有实用价值的算法。那个O(n)只有理论价值。

============================ 华丽的分割线============================

    我们前面证明过，仅仅依靠交换相邻元素的操作，复杂度只 能达到O(n^2)。于是，人们尝试交换距离更远的元素。当人们发现O(nlogn)的排序算法似乎已经是极限的时候，又是什么制约了复杂度的下界呢？我 们将要讨论的是更底层的东西。我们仍然假设所有的数都不相等。
    我们总是不断在数与数之间进行比较。你可以试试，只用4次比较绝对不可能给 4个数排出顺序。每多进行一次比较我们就又多知道了一个大小关系，从4次比较中一共可以获知4个大小关系。4个大小关系共有2^4=16种组合方式，而4 个数的顺序一共有4!=24种。也就是说，4次比较可能出现的结果数目不足以区分24种可能的顺序。更一般地，给你n个数叫你排序，可能的答案共有n! 个，k次比较只能区分2^k种可能，于是只有2^k>=n!时才有可能排出顺序。等号两边取对数，于是，给n个数排序至少需要log2(n!)次。 注意，我们并没有说明一定能通过log2(n!)次比较排出顺序。虽然2^5=32超过了4!，但这不足以说明5次比较一定足够。如何用5次比较确定4个 数的大小关系还需要进一步研究。第一次例外发生在n=12的时候，虽然2^29>12!，但现已证明给12个数排序最少需要30次比较。我们可以证 明log(n!)的增长速度与nlogn相同，即log(n!)=Θ(nlogn)。这是排序所需要的最少的比较次数，它给出了排序复杂度的一个下界。 log(n!)=Θ(nlogn)的证明也附在本文最后。
     这篇日志 的第 三题中证明log2(N)是最优时用到了几乎相同的方法。那种“用天平称出重量不同的那个球至少要称几次”一类题目也可以用这种方法来解决。事实上，这里 有一整套的理论，它叫做信息论。信息论是由香农(Shannon)提出的。他用对数来表示信息量，用熵来表示可能的情况的随机性，通过运算可以知道你目前 得到的信息能够怎样影响最终结果的确定。如果我们的信息量是以2为底的，那信息论就变成信息学了。从根本上说，计算机的一切信息就是以2为底的信息量 (bits=binary digits)，因此我们常说香农是数字通信之父。信息论和热力学关系密切，比如熵的概念是直接 从热力学的熵定义引申过来的。和这个有关的东西已经严重偏题了，这里不说了，有兴趣可以去看《信息论与编码理论》。我对这个也很有兴趣，半懂不懂的，很想 了解更多的东西，有兴趣的同志不妨加入讨论。物理学真的很神奇，利用物理学可以解决很多纯数学问题，我有时间的话可以举一些例子。我他妈的为啥要选文科 呢。
    后面将介绍的三种排序是线性时间复杂度，因为，它们排序时根本不是通过互相比较来确定大小关系的。


附 1：Σ(1/n)=Θ(log n)的证明
    首先我们证明，Σ(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+…中，我们把1/3变成1/2，使得两个1/2加起来凑成一个1；再把1/5,1/6和1/7全部变成 1/4，这样四个1/4加起来又是一个1。我们把所有1/2^k的后面2^k-1项全部扩大为1/2^k，使得这2^k个分式加起来是一个1。现 在，1+1/2+…+1/n里面产生了几个1呢？我们只需要看小于n的数有多少个2的幂即可。显然，经过数的扩大后原式各项总和为log n。O(logn)是Σ(1/n)的复杂度上界。
    然后我们证明，Σ(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+…中，我们把1/3变成1/4，使得两个1/4加起来凑成一个1/2；再把1/5,1/6和1/7全部 变成1/8，这样四个1/8加起来又是一个1/2。我们把所有1/2^k的前面2^k-1项全部缩小为1/2^k，使得这2^k个分式加起来是一个1 /2。现在，1+1/2+…+1/n里面产生了几个1/2呢？我们只需要看小于n的数有多少个2的幂即可。显然，经过数的缩小后原式各项总和为1 /2*logn。Ω(logn)是Σ(1/n)的复杂度下界。


附2：log(n!)=Θ(nlogn)的证明
    首 先我们证明，log(n!)=O(nlogn)。显然n!<n^n，两边取对数我们得到log(n!)<log(n^n)，而 log(n^n)就等于nlogn。因此，O(nlogn)是log(n!)的复杂度上界。
    然后我们证 明，log(n!)=Ω(nlogn)。n!=n(n-1)(n-2)(n-3)….1，把前面一半的因子全部缩小到n/2，后面一半因子全部舍去，显然 有n!>(n/2)^(n/2)。两边取对数，log(n!)>(n/2)log(n/2)，后者即Ω(nlogn)。因 此，Ω(nlogn)是log(n!)的复杂度下界。

今天写到这里了，大家帮忙校对哦
Matrix67原创
转贴请注明出 处
从零开始学算法：十种排序算法介绍（下）
那么，有什么方法可以不用比较就能排 出顺序呢？借助Hash表的思想，多数人都能想出这样一种排序算法来。
    我们假设给出的数字都在一定范围中，那么我们就可以开一个范围相同 的数组，记录这个数字是否出现过。由于数字有可能有重复，因此Hash表的概念需要扩展，我们需要把数组类型改成整型，用来表示每个数出现的次数。
    看 这样一个例子，假如我们要对数列3 1 4 1 5 9 2 6 5 3 5 9进行排序。由于给定数字每一个都小于10，因此我们开一个0到9的整型数组T[i]，记录每一个数出现了几次。读到一个数字x，就把对应的T[x]加 一。

  A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
               +---+---+---+---+---+---+---+---+---+---+
      数 字 i： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
               +---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
               +---+---+---+---+---+---+---+---+---+---+

    最后，我们用一个指针从前 往后扫描一遍，按照次序输出0到9，每个数出现了几次就输出几个。假如给定的数是n个大小不超过m的自然数，显然这个算法的复杂度是O(m+n)的。

    我 曾经以为，这就是线性时间排序了。后来我发现我错了。再后来，我发现我曾犯的错误是一个普遍的错误。很多人都以为上面的这个算法就是传说中的计数排序。问 题出在哪里了？为什么它不是线性时间的排序算法？原因是，这个算法根本不是排序算法，它根本没有对原数据进行排序。


问 题一：为什么说上述算法没有对数据进行排序？
STOP! You should think for a while.

    我们班有很多MM。和身高相差太远的MM在一起肯定很别扭， 接个吻都要弯腰才行（ 小猫 矮死了）。为此，我希望给我们班的MM的身高排序。我们班MM的身高， 再离谱也没有超过2米的，这很适合用我们刚才的算法。我们在黑板上画一个100到200的数组，MM依次自曝身高，我负责画“正”字统计人数。统计出来 了，从小到大依次为141, 143, 143, 147, 152, 153, …。这算哪门子排序？就一排数字对我有什么用，我要知道的是哪个MM有多高。我们仅仅把元素的属性值从小到大列了出来，但我们没有对元素本身进行排序。也 就是说，我们需要知道输出结果的每个数值对应原数据的哪一个元素。下文提到的“排序算法的稳定性”也和属性值与实际元素的区别有关。


问 题二：怎样将线性时间排序后的输出结果还原为原数据中的元素？
STOP! You should think for a while.

    同样借助Hash表的思想，我们立即想到了类似于 开散列的方法。我们用链表把属性值相同的元素串起来，挂在对应的T[i]上。每次读到一个数，在增加T[i]的同时我们把这个元素放进T[i]延伸出去的 链表里。这样，输出结果时我们可以方便地获得原数据中的所有属性值为i的元素。

  A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
               +---+---+---+---+---+---+---+---+---+---+
      数字 i： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
               +---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
               +---+o--+-o-+-o-+-o-+-o-+--o+---+---+-o-+
                    |    |   |   |   |    |          |
                 +--+  +-+   |   |   +-+  +---+      |
                 |     |   A[1]  |     |      |     A[6]
               A[2]  A[7]    |  A[3]  A[5]   A[8]    |
                 |           |         |            A[12]
               A[4]        A[10]      A[9]
                                       |
                                      A[11]

    形 象地说，我们在地上摆10个桶，每个桶编一个号，然后把数据分门别类放在自己所属的桶里。这种排序算法叫做桶式排序(Bucket Sort)。本文最后你将看到桶式排序的另一个用途。
    链表写起来比较麻烦，一般我们不使用它。我们有更简单的方法。


问 题三：同样是输出元素本身，你能想出不用链表的其它算法么？
STOP! You should think for a while.

  A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9
               +---+---+---+---+---+---+---+---+---+---+
      数字 i： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
               +---+---+---+---+---+---+---+---+---+---+
出现次数T[i]： | 0 | 2 | 1 | 2 | 1 | 3 | 1 | 0 | 0 | 2 |
               +---+---+---+---+---+---+---+---+---+---+
修改后的T[i]： | 0 | 2 | 3 | 5 | 6 | 9 | 10| 10| 10| 12|
               +---+---+---+---+---+---+---+---+---+---+

    所有数都读入后，我们修改 T[i]数组的值，使得T[i]表示数字i可能的排名的最大值。比如，1最差排名第二，3最远可以排到第五。T数组的最后一个数应该等于输入数据的数字个 数。修改T数组的操作可以用一次线性的扫描累加完成。
    我们还需要准备一个输出数组。然后，我们从后往前扫描A数组，依照T数组的指示依次 把原数据的元素直接放到输出数组中，同时T[i]的值减一。之所以从后往前扫描A数组，是因为这样输出结果才是稳定的。我们说一个排序算法是稳定的 (Stable)，当算法满足这样的性质：属性值相同的元素，排序后前后位置不变，本来在前面的现在仍然在前面。不要觉得排序算法是否具有稳定性似乎关系 不大，排序的稳定性在下文的某个问题中将变得非常重要。你可以倒回去看看前面说的七种排序算法哪些是稳定的。
    例子中，A数组最后一个数9 所对应的T[9]=12，我们直接把9放在待输出序列中的第12个位置，然后T[9]变成11（这样下一次再出现9时就应该放在第11位）。

A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 9 <--
T[i]= 0, 2, 3, 5, 6, 9, 10, 10, 10, 11
Ans = _ _ _ _ _ _ _ _ _ _ _ 9

    接下来的几步如下：

A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 <--
T[i]= 0, 2, 3, 5, 6, 8, 10, 10, 10, 11
Ans = _ _ _ _ _ _ _ _ 5 _ _ 9

A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 <--
T[i]= 0, 2, 3, 4, 6, 8, 10, 10, 10, 11
Ans = _ _ _ _ 3 _ _ _ 5 _ _ 9

A[]= 3, 1, 4, 1, 5, 9, 2, 6, 5 <--
T[i]= 0, 2, 3, 4, 6, 7, 10, 10, 10, 11
Ans = _ _ _ _ 3 _ _ 5 5 _ _ 9

    这种算法叫 做计数排序(Counting Sort)。正确性和复杂度都是显然的。


问题四：给定数的数据范围大了该怎么 办？
STOP! You should think for a while.

    前面的算法只有在数据的范围不大时才可行，如果给定的数在长整范围内的话，这个算法是不可行的，因为 你开不下这么大的数组。Radix排序(Radix Sort)解决了这个难题。
    昨天我没事翻了一下初中（9班）时的同学录，回忆了一下 过去。我把比较感兴趣的MM的生日列在下面（绝对真实）。如果列表中的哪个MM有幸看到了这篇日志（几乎不可能），左边的Support栏有我的电子联系 方式，我想知道你们怎么样了。排名不分先后。

• 19880818
  
• 19880816
  
• 19890426
  
• 19880405
  
• 19890125
  
• 19881004
  
• 19881209
  
• 19890126
  
• 19890228

    这就是我的数据了。现在，我要给这些数排序。假如我的电脑只能开出0..99的数组，那计数排序算法最多对两位数进行排序。我就把 每个八位数两位两位地分成四段（图1），分别进行四次计数排序。地球人都知道月份相同时应该看哪一日，因此我们看月份的大小时应该事先保证日已经有序。换 句话说，我们先对“最不重要”的部分进行排序。我们先对所有数的最后两位进行一次计数排序（图2）。注意观察1月26号的MM和4月26号的MM，本次排 序中它们的属性值相同，由于计数排序是稳定的，因此4月份那个排完后依然在1月份那个的前头。接下来我们对百位和千位进行排序（图3）。你可以看到两个 26日的MM在这一次排序中分出了大小，而月份相同的MM依然保持日数有序（因为计数排序是稳定的）。最后我们对年份排序（图4），完成整个算法。大家都 是跨世纪的好儿童，因此没有图5了。

      

    这 种算法显然是正确的。它的复杂度一般写成O(d*(n+m))，其中n表示n个数，m是我开的数组大小（本例中m=100），d是一个常数因子（本例中 d=4）。我们认为它也是线性的。


问题五：这样的排序方法还有什么致命的缺陷？
STOP! You should think for a while.

    即 使数据有30位，我们也可以用d=5或6的Radix算法进行排序。但，要是给定的数据有无穷多位怎么办？有人说，这可能么。这是可能的，比如给定的数据 是小数（更准确地说，实数）。基于比较的排序可以区分355/113和π哪 个大，但你不知道Radix排序需要精确到哪一位。这下惨了，实数的出现把貌似高科技的线性时间排序打回了农业时代。这时，桶排序再度出山，挽救了线性时 间排序悲惨的命运。


问题六：如何对实数进行线性时间排序？
STOP! You should think for a while.

    我 们把问题简化一下，给出的所有数都是0到1之间的小数。如果不是，也可以把所有数同时除以一个大整数从而转化为这种形式。我们依然设立若干个桶，比如，以 小数点后面一位数为依据对所有数进行划分。我们仍然用链表把同一类的数串在一起，不同的是，每一个链表都是有序的。也就是说，每一次读到一个新的数都要进 行一次插入排序。看我们的例子：

      A[]= 0.12345, 0.111, 0.618, 0.9, 0.99999
               +---+---+---+---+---+---+---+---+---+---+
      十分位： | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
               +---+-o-+---+---+---+---+-o-+---+---+-o-+
                     |                   |           |
                   A[2]=0.111          A[3]=0.618   A[4]=0.9
                     |                               |
                   A[1]=0.12345                     A[5]=0.99999

    假如再下一个读入的数是 0.122222，这个数需要插入到十分位为1的那个链表里适当的位置。我们需要遍历该链表直到找到第一个比0.122222大的数，在例子中则应该插入 到链表中A[2]和A[1]之间。最后，我们按顺序遍历所有链表，依次输出每个链表中的每个数。
    这个算法显然是正确的，但复杂度显然不是 线性。事实上，这种算法最坏情况下是O(n^2)的，因为当所有数的十分位都相同时算法就是一个插入排序。和原来一样，我们下面要计算算法的平均时间复杂 度，我们希望这种算法的平均复杂度是线性的。
    这次算平均复杂度我们用最笨的办法。我们将算出所有可能出现的情况的总时间复杂度，除以总的 情况数，得到平均的复杂度是多少。
    每个数都可能属于10个桶中的一个，n个数总的情况有10^n种。这个值是我们庞大的算式的分母部分。 如果一个桶里有K个元素，那么只与这个桶有关的操作有O(K^2)次，它就是一次插入排序的操作次数。下面计算，在10^n种情况中，K0=1有多少种情 况。K0=1表示，n个数中只有一个数在0号桶，其余n-1个数的十分位就只能在1到9中选择。那么K0=1的情况有C(n,1)*9^(n-1)，而每 个K0=1的情况在0号桶中将产生1^2的复杂度。类似地，Ki=p的情况数为C(n,p)*9^(n-p)，复杂度总计为C(n,p)*9^(n- p)*p^2。枚举所有K的下标和p值，累加起来，这个算式大家应该能写出来了，但是这个……怎么算啊。别怕，我们是搞计算机的，拿出点和MO不一样的东 西来。于是，Mathematica 5.0隆重登场，我做数学作业全靠它。它将帮我们化简这个复杂的式子。


    我 们遗憾地发现，虽然常数因子很小（只有0.1），但算法的平均复杂度仍然是平方的。等一下，1/10的那个10是我们桶的个数吗？那么我们为什么不把桶的 个数弄大点？我们干脆用m来表示桶的个数，重新计算一次：


    化 简出来，操作次数为O(n+n^2/m)。发现了么，如果m=Θ(n)的话，平均复杂度就变成了O(n)。也就是说，当桶的个数等于输入数据的个数时，算 法是平均线性的。
    我们将在Hash表开散列的介绍中重新提到这个结论。

    且慢，还有一个问题。10个桶以十分位的 数字归类，那么n个桶用什么方法来分类呢？注意，分类的方法需要满足，一，一个数分到每个桶里的概率相同（这样才有我们上面的结论）；二，所有桶里容纳元 素的范围必须是连续的。根据这两个条件，我们有办法把所有数恰好分为n类。我们的输入数据不是都在0到1之间么？只需要看这些数乘以n的整数部分是多少就 行了，读到一个数后乘以n取整得几就插入到几号桶里。这本质上相当于把区间[0,1)平均分成n份。


问题七：有 没有复杂度低于线性的排序算法
STOP! You should think for a while.

    我们从O(n^2)走向O(nlogn)，又从O(nlogn)走向线性， 每一次我们都讨论了复杂度下限的问题，根据讨论的结果提出了更优的算法。这次总算不行了，不可能有比线性还快的算法了，因为——你读入、输出数据至少就需 要线性的时间。排序算法之旅在线性时间复杂度这一站终止了，所有十种排序算法到这里介绍完毕了。



    文章有越写越长 的趋势了，我检查起来也越来越累了。我又看了三遍，应该没问题了。群众的眼睛是雪亮的，恳请大家帮我找错。

=====   真正强的东西来了！   =====

二进制中的1有奇数个还是偶数个
    我们可以用下面的代码来计算 一个32位整数的二进制中1的个数的奇偶性，当输入数据的二进制表示里有偶数个数字1时程序输出0，有奇数个则输出1。例如，1314520的二进制 101000000111011011000中有9个1，则x=1314520时程序输出1。
var
   i,x,c:longint;
begin
   readln(x);
   c:=0;
   for i:=1 to 32 do
   begin
      c:=c + x and 1;
      x:=x shr 1;
   end;
   writeln( c and 1 );
end.
    但这样的效率并不高，位运算的神奇之处还 没有体现出来。
    同样是判断二进制中1的个数的奇偶性，下面这段代码就强了。你能看出这个代码的原理吗？
var
   x:longint;
begin
   readln(x);
   x:=x xor (x shr 1);
   x:=x xor (x shr 2);
   x:=x xor (x shr 4);
   x:=x xor (x shr 8);
   x:=x xor (x shr 16);
   writeln(x and 1);
end.
    为了说明 上面这段代码的原理，我们还是拿1314520出来说事。1314520的二进制为101000000111011011000，第一次异或操作的结果如 下：

    00000000000101000000111011011000
XOR  0000000000010100000011101101100
---------------------------------------
    00000000000111100000100110110100

    得 到的结果是一个新的二进制数，其中右起第i位上的数表示原数中第i和i+1位上有奇数个1还是偶数个1。比如，最右边那个0表示原数末两位有偶数个1，右 起第3位上的1就表示原数的这个位置和前一个位置中有奇数个1。对这个数进行第二次异或的结果如下：

    00000000000111100000100110110100
XOR   000000000001111000001001101101
---------------------------------------
    00000000000110011000101111011001

    结 果里的每个1表示原数的该位置及其前面三个位置中共有奇数个1，每个0就表示原数对应的四个位置上共偶数个1。一直做到第五次异或结束后，得到的二进制数 的最末位就表示整个32位数里有多少个1，这就是我们最终想要的答案。


计算二进制中的1的个数
    同样假设x是一个 32位整数。经过下面五次赋值后，x的值就是原数的二进制表示中数字1的个数。比如，初始时x为1314520（网友抓狂：能不能换一个数啊），那么最后 x就变成了9，它表示1314520的二进制中有9个1。
x := (x and $55555555) + ((x shr 1) and $55555555);
x := (x and $33333333) + ((x shr 2) and $33333333);
x := (x and $0F0F0F0F) + ((x shr 4) and $0F0F0F0F);
x := (x and $00FF00FF) + ((x shr 8) and $00FF00FF);
x := (x and $0000FFFF) + ((x shr 16) and $0000FFFF);
    为了便于解说，我们下面仅说明这个程序是如何对一个8位整数进 行处理的。我们拿数字211（我们班某MM的生日）来开刀。211的二进制为11010011。

+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |   <---原数
+---+---+---+---+---+---+---+---+
|  1 0  |  0 1  |  0 0  |  1 0  |   <---第一次运算后
+-------+-------+-------+-------+
|    0 0 1 1    |    0 0 1 0    |   <---第二次运算后
+---------------+---------------+
|        0 0 0 0 0 1 0 1        |   <---第三次运算后，得数为5
+-------------------------------+

    整 个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相 加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010 加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100….，用 它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。


二分查找32位整数的前导0个数
    这 里用的C语言，我直接Copy的Hacker's Delight上的代码。这段代码写成C要好看些，写成Pascal的话会出现很多begin和end，搞得代码很难看。程序思想是二分查找，应该很简 单，我就不细说了。
int nlz(unsigned x)
{
   int n;

   if (x == 0) return(32);
   n = 1;
   if ((x >> 16) == 0) {n = n +16; x = x <<16;}
   if ((x >> 24) == 0) {n = n + 8; x = x << 8;}
   if ((x >> 28) == 0) {n = n + 4; x = x << 4;}
   if ((x >> 30) == 0) {n = n + 2; x = x << 2;}
   n = n - (x >> 31);
   return n;
}


只用位运算来取 绝对值
    这是一个非常有趣的问题。大家先自己想想吧，Ctrl+A显示答案。
    答案：假设x为32位整数，则x xor (not (x shr 31) + 1) + x shr 31的结果是x的绝对值
    x shr 31是二进制的最高位，它用来表示x的符号。如果它为0（x为正），则not (x shr 31) + 1等于$00000000，异或任何数结果都不变；如果最高位为1（x为负），则not (x shr 31) + 1等于$FFFFFFFF，x异或它相当于所有数位取反，异或完后再加一。


高低位交换
    这个题实际上是我出的，做为学校内部NOIp模拟赛的第一题。题目是这样：

    给出一个小于2^32的正整数。这个数可以用一个32位的二进制数表示（不足32位用0补足）。我们称这个二进 制数的前16位为“高位”，后16位为“低位”。将它的高低位交换，我们可以得到一个新的数。试问这个新的数是多少（用十进制表示）。
　　例如， 数1314520用二进制表示为0000 0000 0001 0100 0000 1110 1101 1000（添加了11个前导0补足为32位），其中前16位为高位，即0000 0000 0001 0100；后16位为低位，即0000 1110 1101 1000。将它的高低位进行交换，我们得到了一个新的二进制数0000 1110 1101 1000 0000 0000 0001 0100。它即是十进制的249036820。

 

    当时几乎没有人想到用一句位操作来代替冗长的程序。使用位运算的话两句话就完了。
var
   n:dword;
begin
   readln( n );
   writeln( (n shr 16) or (n  shl 16) );
end.
    而事实上，Pascal有一个系统函数swap直接就可以用。


二 进制逆序
    下面的程序读入一个32位整数并输出它的二进制倒序后所表示的数。
    输入： 1314520    （二进制为00000000000101000000111011011000）
    输出： 460335104  （二进制为00011011011100000010100000000000）
var
   x:dword;
begin
   readln(x);
   x := (x and $55555555) shl  1 or (x and $AAAAAAAA) shr  1;
   x := (x and $33333333) shl  2 or (x and $CCCCCCCC) shr  2;
   x := (x and $0F0F0F0F) shl  4 or (x and $F0F0F0F0) shr  4;
   x := (x and $00FF00FF) shl  8 or (x and $FF00FF00) shr  8;
   x := (x and $0000FFFF) shl 16 or (x and $FFFF0000) shr 16;
   writeln(x);
end.
    它的原理和刚才求二进制中1 的个数那个例题是大致相同的。程序首先交换每相邻两位上的数，以后把互相交换过的数看成一个整体，继续进行以2位为单位、以4位为单位的左右对换操作。我 们再次用8位整数211来演示程序执行过程：
+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |   <---原数
+---+---+---+---+---+---+---+---+
|  1 1  |  1 0  |  0 0  |  1 1  |   <---第一次运算后
+-------+-------+-------+-------+
|    1 0 1 1    |    1 1 0 0    |   <---第二次运算后
+---------------+---------------+
|        1 1 0 0 1 0 1 1        |   <---第三次运算后
+-------------------------------+


Copyright 也很强
writeln('Matrix' , 42 XOR 105 , '原创，转贴请注明出处');

今天我们来看两个稍微复杂一点的例子。

n皇后问题位运算版
    n皇后问题是啥我就不说了吧，学编程的肯定都见过。下面 的十多行代码是n皇后问题的一个高效位运算程序，看到过的人都夸它牛。初始时，upperlim:=(1 shl n)-1。主程序调用test(0,0,0)后sum的值就是n皇后总的解数。拿这个去交USACO，0.3s，暴爽。
procedure test(row,ld,rd:longint);
var
      pos,p:longint;
begin

{ 1}  if row<>upperlim then
{ 2}  begin
{ 3}     pos:=upperlim and not (row or ld or rd);
{ 4}     while pos<>0 do
{ 5}     begin
{ 6}        p:=pos and -pos;
{ 7}        pos:=pos-p;
{ 8}        test(row+p,(ld+p)shl 1,(rd+p)shr 1);
{ 9}     end;
{10}  end
{11}  else inc(sum);

end;
    乍 一看似乎完全摸不着头脑，实际上整个程序是非常容易理解的。这里还是建议大家自己单步运行一探究竟，实在没研究出来再看下面的解说。

  
    和 普通算法一样，这是一个递归过程，程序一行一行地寻找可以放皇后的地方。过程带三个参数，row、ld和rd，分别表示在纵列和两个对角线方向的限制条件 下这一行的哪些地方不能放。我们以6×6的棋盘为例，看看程序是怎么工作的。假设现在已经递归到第四层，前三层放的子已经标在左图上了。红色、蓝色和绿色 的线分别表示三个方向上有冲突的位置，位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来，得到该行所有的禁位，取反后就得到所 有可以放的位置（用pos来表示）。前面说过-a相当于not a + 1，这里的代码第6行就相当于pos and (not pos + 1)，其结果是取出最右边的那个1。这样，p就表示该行的某个可以放子的位置，把它从pos中移除并递归调用test过程。注意递归调用时三个参数的变 化，每个参数都加上了一个禁位，但两个对角线方向的禁位对下一行的影响需要平移一位。最后，如果递归到某个时候发现row=111111了，说明六个皇后 全放进去了，此时程序从第1行跳到第11行，找到的解的个数加一。

    ~~~~====~~~~=====   华丽的分割线   =====~~~~====~~~~

Gray码
    假如我有4个潜在的GF，我需要决定最终到底和谁在一起。一个简单的办法 就是，依次和每个MM交往一段时间，最后选择给我带来的“满意度”最大的MM。但看了dd牛的理论后， 事情开始变得复杂了：我可以选择和多个MM在一起。这样，需要考核的状态变成了2^4=16种（当然包括0000这一状态，因为我有可能是玻璃）。现在的 问题就是，我应该用什么顺序来遍历这16种状态呢？
    传统的做法是，用二进制数的顺序来遍历所有可能的组合。也就是说，我需要以 0000->0001->0010->0011->0100->…->1111这样的顺序对每种状态进行测试。这个 顺序很不科学，很多时候状态的转移都很耗时。比如从0111到1000时我需要暂时甩掉当前所有的3个MM，然后去把第4个MM。同时改变所有MM与我的 关系是一件何等巨大的工程啊。因此，我希望知道，是否有一种方法可以使得，从没有MM这一状态出发，每次只改变我和一个MM的关系（追或者甩），15次操 作后恰好遍历完所有可能的组合（最终状态不一定是1111）。大家自己先试一试看行不行。
    解决这个问题的方法很巧妙。我们来说明，假如我 们已经知道了n=2时的合法遍历顺序，我们如何得到n=3的遍历顺序。显然，n=2的遍历顺序如下：

00
01
11
10

    你 可能已经想到了如何把上面的遍历顺序扩展到n=3的情况。n=3时一共有8种状态，其中前面4个把n=2的遍历顺序照搬下来，然后把它们对称翻折下去并在 最前面加上1作为后面4个状态：

000
001
011
010  ↑
--------
110  ↓
111
101
100

    用 这种方法得到的遍历顺序显然符合要求。首先，上面8个状态恰好是n=3时的所有8种组合，因为它们是在n=2的全部四种组合的基础上考虑选不选第3个元素 所得到的。然后我们看到，后面一半的状态应该和前面一半一样满足“相邻状态间仅一位不同”的限制，而“镜面”处则是最前面那一位数不同。再次翻折三阶遍历 顺序，我们就得到了刚才的问题的答案：

0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000

    这 种遍历顺序作为一种编码方式存在，叫做Gray码（写个中文让蜘蛛来抓：格雷码）。它的应用范围很广。比如，n阶的Gray码相当于在n维立方体上的 Hamilton回路，因为沿着立方体上的边走一步，n维坐标中只会有一个值改变。再比如，Gray码和Hanoi塔问题等价。Gray码改变的是第几个 数，Hanoi塔就该移动哪个盘子。比如，3阶的Gray码每次改变的元素所在位置依次为1-2-1-3-1-2-1，这正好是3阶Hanoi塔每次移动 盘子编号。如果我们可以快速求出Gray码的第n个数是多少，我们就可以输出任意步数后Hanoi塔的移动步骤。现在我告诉你，Gray码的第n个数（从 0算起）是n xor (n shr 1)，你能想出来这是为什么吗？先自己想想吧。

    下面我们把二进制数和Gray码都写在下 面，可以看到左边的数异或自身右移的结果就等于右边的数。

二进制数   Gray码
   000       000
   001       001
   010       011
   011       010
   100       110
   101       111
   110       101
   111       100

    从 二进制数的角度看，“镜像”位置上的数即是对原数进行not运算后的结果。比如，第3个数010和倒数第3个数101的每一位都正好相反。假设这两个数分 别为x和y，那么x xor (x shr 1)和y xor (y shr 1)的结果只有一点不同：后者的首位是1，前者的首位是0。而这正好是Gray码的生成方法。这就说明了，Gray码的第n个数确实是n xor (n shr 1)。

    今年四月份mashuo给 我看了这道题，是二维意义上的Gray码。题目大意是说，把0到2^(n+m)-1的数写成2^n * 2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。答案其实很简单，所有数都是由m位的Gray码和n位Gray码拼接而成，需要用左移操作和 or运算完成。完整的代码如下：
var
   x,y,m,n,u:longint;
begin
   readln(m,n);
   for x:=0 to 1 shl m-1 do begin
      u:=(x xor (x shr 1)) shl n; //输出数的左边是一个m位的Gray码
      for y:=0 to 1 shl n-1 do
         write(u or (y xor (y shr 1)),' '); //并上一个n位Gray码
      writeln;
   end;
end.

Matrix67原创
转贴请注明出处

Problem : 费解的开关

题目来源
    06 年NOIp模拟赛（一） by Matrix67 第四题

问题描述
    你玩过“拉灯”游戏吗？25盏灯排成一个5×5的方 形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相 邻的灯也要相应地改变其状态。
    我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011

    在 改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

    再 改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

    给 定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式
    第一行有一个正整数n，代表数 据中共有n个待解决的游戏初始状态。
    以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数 据间用一个空行分隔。
    对于30%的数据，n<=5；
    对于100%的数据，n<=500。

输 出格式
    输出数据一共有n行，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
    对 于某一个游戏初始状态，若6步以内无法使所有灯变亮，请输出“-1”。

样例输入
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

样 例输出
3
2
-1

 

程序代码
const
   BigPrime=3214567;
   MaxStep=6;
type
   pointer=^rec;
   rec=record
         v:longint;
         step:integer;
         next:pointer;
       end;

var
   total:longint;
   hash:array[0..BigPrime-1]of pointer;
   q:array[1..400000]of rec;

function update(a:longint;p:integer):longint;
begin
   a:=a xor (1 shl p);
   if p mod 5<>0 then a:=a xor (1 shl (p-1));
   if (p+1) mod 5<>0 then a:=a xor (1 shl (p+1));
   if p<20 then a:=a xor (1 shl (p+5));
   if p>4 then a:=a xor (1 shl (p-5));
   exit(a);
end;

function find(a:longint;step:integer):boolean;
var
   now:pointer;
begin
   now:=hash[a mod BigPrime];
   while now<>nil do
   begin
      if now^.v=a then exit(true);
      now:=now^.next;
   end;

   new(now);
   now^.v:=a;
   now^.step:=step;
   now^.next:=hash[a mod BigPrime];
   hash[a mod BigPrime]:=now;
   total:=total+1;
   exit(false);
end;

procedure solve;
var
   p:integer;
   close:longint=0;
   open:longint=1;
begin
   find(1 shl 25-1,0);
   q[1].v:=1 shl 25-1;
   q[1].step:=0;
   repeat
      inc(close);
      for p:=0 to 24 do
         if not find(update(q[close].v,p),q[close].step+1) and (q[close].step+1<MaxStep) then
         begin
            open:=open+1;
            q[open].v:=update(q[close].v,p);
            q[open].step:=q[close].step+1;
         end;
   until close>=open;
end;

procedure print(a:longint);
var
   now:pointer;
begin
   now:=hash[a mod BigPrime];
   while now<>nil do
   begin
      if now^.v=a then
      begin
         writeln(now^.step);
         exit;
      end;
      now:=now^.next;
   end;
   writeln(-1);
end;

procedure main;
var
   ch:char;
   i,j,n:integer;
   t:longint;
begin
   readln(n);
   for i:=1 to n do
   begin
      t:=0;
      for j:=1 to 25 do
      begin
         read(ch);
         t:=t*2+ord(ch)-48;
         if j mod 5=0 then readln;
      end;
      print(t);
      if i<n then readln;
   end;
end;

begin
   solve;
   main;
end.

=======================  性 感的分割线  =======================

Problem : garden / 和MM逛花园

题目来源
     07年Matrix67生日邀请赛 第 四题

问题描述
    花园设计强调，简单就是美。Matrix67常去的花园有着非常简单的布局：花园的所有景点的位置都是“对 齐”了的，这些景点可以看作是平面坐标上的格点。相邻的景点之间有小路相连，这些小路全部平行于坐标轴。景点和小路组成了一个“不完整的网格”。
    一 个典型的花园布局如左图所示。花园布局在6行4列的网格上，花园的16个景点的位置用红色标注在了图中。黑色线条表示景点间的小路，其余灰色部分实际并不 存在。
        

    Matrix67 的生日那天，他要带着他的MM在花园里游玩。Matrix67不会带MM两次经过同一个景点，因此每个景点最多被游览一次。他和他的MM边走边聊，他们是 如此的投入以致于他们从不会“主动地拐弯”。也就是说，除非前方已没有景点或是前方的景点已经访问过，否则他们会一直往前走下去。当前方景点不存在或已游 览过时，Matrix67会带MM另选一个方向继续前进。由于景点个数有限，访问过的景点将越来越多，迟早会出现不能再走的情况（即四个方向上的相邻景点 都访问过了），此时他们将结束花园的游览。Matrix67希望知道以这种方式游览花园是否有可能遍历所有的景点。Matrix67可以选择从任意一个景 点开始游览，以任意一个景点结束。
    在上图所示的花园布局中，一种可能的游览方式如右图所示。这种浏览方式从(1,2)出发，以(2,4) 结束，经过每个景点恰好一次。

输入格式
    第一行输入两个用空格隔开的正整数m和n，表示花园被布局在m行n列的网格上。
    以 下m行每行n个字符，字符“0”表示该位置没有景点，字符“1”表示对应位置有景点。这些数字之间没有空格。

输出格式
    你 的程序需要寻找满足“不主动拐弯”性质且遍历所有景点的游览路线。
    如果没有这样的游览路线，请输出一行“Impossible”（不带引 号，注意大小写）。
    如果存在游览路线，请依次输出你的方案中访问的景点的坐标，每行输出一个。坐标的表示格式为“(x,y)”，代表第x 行第y列。
    如果有多种方案，你只需要输出其中一种即可。评测系统可以判断你的方案的正确性。

样例输入
6 4
1100
1001
1111
1100
1110
1110

样 例输出
(1,2)
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(6,1)
(6,2)
(6,3)
(5,3)
(5,2)
(4,2)
(3,2)
(3,3)
(3,4)
(2,4)

数 据规模
    对于30%的数据，n,m<=5；
    对于100%的数据，n,m<=10。

 

程序代码：
program garden;

const
   dir:array[1..4,1..2]of integer=
     ((1,0),(0,1),(-1,0),(0,-1));

type
   arr=array[1..10]of integer;
   rec=record x,y:integer;end;

var
   map:array[0..11,0..11]of boolean;
   ans:array[1..100]of rec;
   n,m,max:integer;
   step:integer=1;
   state:arr;

procedure readp;
var
   i,j:integer;
   ch:char;
begin
   readln(m,n);
   for i:=1 to n do
   begin
      for j:=1 to m do
      begin
         read(ch);
         map[i,j]:=(ch='1');
         inc(max,ord( map[i,j] ))
      end;
   readln;
   end;
end;

procedure writep;
var
   i:integer;
begin
   for i:=1 to step do
      writeln( '(' , ans[i].x , ',' , ans[i].y , ')' );
end;

procedure solve(x,y:integer);
var
   tx,ty,d:integer;
   step_cache:integer;
   state_cache:arr;
begin
   step_cache:=step;
   state_cache:=state;
   if step=max then
   begin
      writep;
      exit;
   end;

   for d:=1 to 4 do
   begin
      tx:=x+dir[d,1];
      ty:=y+dir[d,2];
      while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
      begin
         inc(step);
         ans[step].x:=tx;
         ans[step].y:=ty;
         state[tx]:=state[tx] or ( 1 shl (ty-1) );
         tx:=tx+dir[d,1];
         ty:=ty+dir[d,2];
      end;

      tx:=tx-dir[d,1];
      ty:=ty-dir[d,2];
      if (tx<>x) or (ty<>y) then solve(tx,ty);
      state:=state_cache;
      step:=step_cache;
   end;
end;

{====main====}
var
   i,j:integer;
begin
   assign(input,'garden.in');
   reset(input);
   assign(output,'garden.out');
   rewrite(output);

   readp;
   for i:=1 to n do
   for j:=1 to m do
     if map[i,j] then
     begin
        ans[1].x:=i;
        ans[1].y:=j;
        state[i]:=1 shl (j-1);
        solve(i,j);
        state[i]:=0;
     end;

   close(input);
   close(output);
end.

=======================  性 感的分割线  =======================

Problem : cowfood / 玉米地

题目来源
    USACO月赛

问 题描述
    农夫约翰购买了一处肥沃的矩形牧场，分成M*N(1<=M<=12; 1<=N<=12)个格子。他想在那里的一些格子中种植美味的玉米。遗憾的是，有些格子区域的土地是贫瘠的，不能耕种。
    精明 的约翰知道奶牛们进食时不喜欢和别的牛相邻，所以一旦在一个格子中种植玉米，那么他就不会在相邻的格子中种植，即没有两个被选中的格子拥有公共边。他还没 有最终确定哪些格子要选择种植玉米。
    作为一个思想开明的人，农夫约翰希望考虑所有可行的选择格子种植方案。由于太开明，他还考虑一个格子 都不选择的种植方案！请帮助农夫约翰确定种植方案总数。

输入格式:
    第一行：两个用空格分隔的整数M和N
    第 二行到第M+1行：第i+1行描述牧场第i行每个格子的情况，N个用空格分隔的整数，表示这个格子是否可以种植（1表示肥沃的、适合种植，0表示贫瘠的、 不可种植）

输出格式
    一个整数，农夫约翰可选择的方案总数除以 100,000,000 的余数

样例输入
2 3
1 1 1
0 1 0

样例输出
9

样例说明

    给可以种植玉米的格子编 号：
      1 2 3
        4

    只 种一个格子的方案有四种(1,2,3或4)，种植两个格子的方案有三种(13,14或34)，种植三个格子的方案有一种(134)，还有一种什么格子都不 种。
    4+3+1+1=9。

数据规模
    对于30%的数据，N,M<=4；
    对于 100%的数据，N,M<=12。

 

程序代码：
program cowfood;

const
   d=100000000;
   MaxN=12;

var
   f:array[0..MaxN,1..2000]of longint;
   w:array[1..2000,1..2000]of boolean;
   st:array[0..2000]of integer;
   map:array[0..MaxN]of integer;
   m,n:integer;

function Impossible(a:integer):boolean;
var
   i:integer;
   flag:boolean=false;
begin
   for i:=1 to MaxN do
   begin
      if flag and (a and 1=1) then exit(true);
      flag:=(a and 1=1);
      a:=a shr 1;
   end;
   exit(false);
end;

function Conflict(a,b:integer):boolean;
var
   i:integer;
begin
   for i:=1 to MaxN do
   begin
      if (a and 1=1) and (b and 1=1) then exit(true);
      a:=a shr 1;
      b:=b shr 1;
   end;
   exit(false);
end;

function CanPlace(a,b:integer):boolean;
begin
   exit(a or b=b);
end;

procedure FindSt;
var
   i:integer;
begin
   for i:=0 to 1 shl MaxN-1 do
      if not Impossible(i) then
      begin
         inc(st[0]);
         st[st[0]]:=i;
      end;
end;

procedure Init;
var
   i,j:integer;
begin
   for i:=1 to st[0] do
   for j:=i to st[0] do
      if not Conflict(st[i],st[j]) then
      begin
         w[i,j]:=true;
         w[j,i]:=true;
      end;
end;

procedure Readp;
var
   i,j,t,v:integer;
begin
   readln(m,n);
   for i:=1 to m do
   begin
      v:=0;
      for j:=1 to n do
      begin
         read(t);
         v:=v*2+t;
      end;
      map[i]:=v;
      readln;
   end;
end;

procedure Solve;
var
   i,j,k:integer;
begin
   f[0,1]:=1;
   map[0]:=1 shl n-1;
   for i:=1 to m do
   for j:=1 to st[0] do
      if not CanPlace(st[j],map[i]) then f[i,j]:=-1 else
        for k:=1 to st[0] do if (f[i-1,k]<>-1) and w[j,k] then
           f[i,j]:=(f[i,j]+f[i-1,k]) mod d;
end;

procedure Writep;
var
   j:integer;
   ans:longint=0;
begin
   for j:=1 to st[0] do
      if f[m,j]<>-1 then ans:=(ans+f[m,j]) mod d;
   writeln(ans);
end;

begin
   assign(input,'cowfood.in');
   reset(input);
   assign(output,'cowfood.out');
   rewrite(output);

   FindSt;
   Init;
   Readp;
   Solve;
   Writep;

   close(input);
   close(output);
end.