打印质数的各种算法

来源：原文链接

---

打印质数的算法应该是学习计算机编程的一个经典的问题，在这里想给大家展示一些方法，相信这些方法会对你的编程有一定的启发作用。请你注意几点，

• 实际应用和教学应用有很大的差别。
• 最后的那个使用编译时而不是运行时的方法大家可以重点看看。

教科书的示例

首先，先给一个教科书的示例。下面这个示例应该是教科书（至少是我上大学时的教科学）中算法复杂度最好的例子了。其想法很简单，先写一个判断是否是质数的函数isPrime()，然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心，其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n))，看上去不错，但其实很不经济。

#include <iostream> 
using namespace std;  
bool isPrime(int nr) {
     for (int d = 2; (d * d) <= (nr + 1); ++d){
         if (!(nr % d)){
             return false;
         }
      }
     return true;
 }  

int main (int argc, char * const argv[]) {
     for (int i = 0; i < 50; ++i){
         if (isPrime(i)){
             cout << i << endl;
         }
     }
 } 

较好的算法

我们知道，我们的算法如果写成线性算法，也就是O(n)，已经算是不错了，但是最好的是O(Log(n))的算法，这是一个级数级的算法，著名的二分取中（Binary Search）正是O(Log(n))的算法。通常来说，O(Log(n))的算法都是以排除法做为手段的。所以，找质数的算法完全可以采用排除法的方式。如下所示，这种算法的复杂度是O(n(log(logn)))。
示例：打印30以内的质数
一、初始化如下列表。

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

二、把第一个数（2）取出来，去掉所有可以被2整除的数。

2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

三、取第二个数（3），去掉所有可以被 3整除的数。

2  3     5     7          11    13          17    19          23    25          29

四、取第三个数（5），因为4已经被去除了，再去掉所有可以被5整除的数。

2  3     5     7          11    13          17    19          23                29

接下来的数是7，但是7的平方是49，其大于了30，所以我们可以停止计算了。剩下的数就是所有的质数了。

实际应用的算法

实际应用中，我们通常不会使用上述的两种算法，因为那是理论学院派的算法。实际中的算法是，我把质数事先就计算好，放在一个文件中，然后在程序启动时（注意是在启动时读这个文件，而不是运行时每调用一次就读一次文件），读取这个文件，然后打印出来就可以了。如果需要查找的化，二分查找或是hash表查找将会获得巨大的性能提升。当然，这样的方法对于空间来说比前面两个都要消耗得大，但是你可以有O(log(n))或是O(1)的时间复杂度。
所以，我想在这里提醒大家——实际和理论的的方法很不一样的，千万不要读书读成书呆子。在游戏编程的世界里，大量的数据都不是运行计算的，而都是写在文件中的。比如，一个火焰效果，一个人物跑动的动作，都是事先写在文件中的。

使用编译时而不是运行时

下面这个例子（本例参考于这里）你需要注意了，这是一个高级用法，使用模式来在编译时计算质数，而不是运行时。这种技术使用了C++编译器对模板的特化时的处理来生成自己相要的结果。这种方法在技术上是相当Cool的，但并不一定实用，这里只是想像大家展示这种用法。这是C++的最骨灰级的用法了。
请看下面的两个模板类，第一个模板以递归的方式检查是否是质数，第二个方法是递归的退出条件（当N=1时），对于模板的重载，请参看相关的C++书籍。

template<int N, int D = N - 1> 
struct isPrime {
     enum {
         result = (N % D) && isPrime<N, D-1>::result
     };
 };

template<int N> 
struct isPrime<N, 1> {
     enum {
         result = true
     };
 }; 

于是，通过这个模板，我们可以使用下面的代码来检查是否是质数：

if (isPrime<3>::result)
     cout << "Guess what: 3 is a prime!";
 

下一步，我们需要打出一个区间内的质数，所以，我们需要继续设计我们的print模板。

template<int N, bool ISPRIME> 
struct printIfPrime {
     static inline void print() {} 
};  
template <int N> 
struct printIfPrime<N, true> {
     static inline void print() {
         std::cout << N << endl;     
     }
}; 

从上面的代码中，我们可以看到，我们的第一个实际是什么也没做，而第二个有输出，注意第二个的模板参数中有一个true，其意味着那个质数的判断。于是我们就可以给出下面的代码来尝试着打印出一段区间内的质数：（请不要编译！！因为那会让编译器进入无限循环中，原因是printPrimes会不停地调用自己永不停止）

template<int N, int MAX> 
struct printPrimes {
     static inline void print()     {
         printIfPrime<N, isPrime<N>::result>::print();
         printPrimes<N + 1, MAX>::print();
     }
 };
 

为了避免这个问题，你需要再加一个模板类，如下所示。这样当N变成MAX的时候，递归就结束了。

template<int N> 
struct printPrimes<N, N> {
     static inline void print() {
         printIfPrime<N, isPrime<N>::result>::print();     
     } 
}; 

最后，让我们来看看最终的调用：

int main (int argc, char * const argv[]) {
     printPrimes<2, 40>::print();
     return 0;
 } 

这个方法很NB，但是有两个问题：

• 比较耗编译时间。
• 不能在运行时输入MAX的值。

不过，相信这种玩法会启动你很多的编程思路。
（全文完)

C++中数组参数详解

在C++中，数组永远不会按值传递。它是传递第一个元素（准确地说是第0个）的指针。

例如，如下声明：

  void putValues(int[10]);

被编译器视为：

  void putValues(int*);

数组的长度与参数声明无关。因此，下列三个声明是等价的：

  void putValues(int*);

  void putValues(int[]);

  void putValues(int[10]);

因为数组被传递为指针，所以这对程序员有两个含义：

1、在被调函数内对参数数组的改变将被应用到数组实参上而不是本地拷贝上。当用作实参的数组必须保持不变时，程序员需要保留数组的拷贝。函数可以通过把参数类型声明为const来表明不希望改变数组元素：

  void putValues(const int[10]);

2、数组长度不是参数类型的一部分。函数不知道传递给它的数组的实际长度，编译器也不知道，当编译器对实参类型进行参数类型检查时，并不检查数组的长度。

例如：

void putValues(int[10]); //视为int*

int main()

{

    int i, j[2];

    putValues(&i); //ok:&i是int*; 潜在的运行错误

    putValues(j);  //ok:j被转换成第0个元素的指针

    // 实参类型为int*:潜在的运行错误

    return 0;

}

 

参数的类型检查只能保证putValues()的再次调用都提供了int*型的实参。类型检查不能检验实参是一个10元素的数组。

习惯上，C风格字符串是字符的数组，它用一个空字符编码作为结尾。但是所有其他类型，包括希望处理内含字符的字符数组，必须以某种方式在向函数传递实参时使其知道它的长度。一种常见的机制是提供一个含有数组实参的长度的额外参数。例如：

 void putValues(int[], int size);

int main()

{

    int i,j[2];

    putValues(&i, 1);

    putValues(j, 2);

    return 0;

}

另外一种机制是将参数声明为数组的引用。当参数是一个数组类型的引用时，数组长度成为参数和类型的一部分，编译器检查数组实参的长度与在函数参数类型中指定的长度是否匹配。

// 参数为10个int的数组

// parameter is a reference to an array of 10 ints

void putValues(int (&arr)[10]);

int main()

{

    int i, j[2];

    int a[10];

    putValues(i); // 错误：实参不是10个int的数组

    putValues(j); // 错误：实参不是10个int的数组

    putValues(a); // 正确

    return 0;

}

因为数组的长度现在是参数类型的一部分，所以putValues()的这个版本只接受10个int的数组。这限制了可以作为实参被传递给putValues()的数组的种类。但是，它也使函数的实现更加简单。

ShowWindow的疑问

本 文：[转寄][转贴][删除][修改][回复][作者:novice][人气:81]

发信人: novice (Android), 信区: VC 

标  题: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月06日23:59:04 星期天), 站内信件 WWWPOST 

BOOL WINAPI ShowWindow( 

  __in  HWND hWnd, 

  __in  int nCmdShow 

); 

中 nCmdShow,MSDN中有这么段话： 

This parameter is ignored the first time an application calls ShowWindow, if  

the program that launched the application provides a STARTUPINFO structure.  

Otherwise, the first time ShowWindow is called, the value should be the  

value obtained by the WinMain function in its nCmdShow parameter. 

要怎么理解？？？ 

我的理解是，如果我用CreateProcess创建某程序，该程序就是创建个窗口，别无其他功 

能，调用CreateProcess时提供了STARTUPINFO si，并将相应的标志位设置si.dwFlags = 

 STARTF_USESHOWWINDOW，si.wShowWindow = SW_SHOWMINIMIZED. 

这样的话，即使被创建的程序第一次调用ShowWindow时传入参数 SW_SHOWMAXIMIZED ,程 

序也应该刚开始是最小化的。因为按照文档说明，参数该被忽略。 

但实际试验了一下，还是会出现最大化得窗口。不知道我哪里理解错误？ 

-- 

本 文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:7]

发信人: CrLF (CrLF(落羽猫)), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月07日13:26:12 星期一), 站内信件 WWWPOST 

注意认真读文档：if the program that launched the application provides a  

STARTUPINFO structure. 

典型的提供STARTUPINFO的方法如：建立一个快捷方式，通过双击快捷方式启动。 

-- 

本 文：[转寄][转贴][删除][修改][回复][作者:novice][人气:2]

发信人: novice (Android), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月07日21:04:18 星期一), 站内信件 WWWPOST 

调用CreateProcess时，给 STARTUPINFO 赋值，不算提供STARTUPINFO 么？ 

-- 

本 文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:5]

发信人: CrLF (CrLF(落羽猫)), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月08日13:40:44 星期二), 站内信件 WWWPOST 

之前理解错了。查了一下，使用STARTUPINFO 里提供的wShowWindow的条件是： 

第一种情况：ShowWindow的参数设为SW_SHOWDEFAULT 

第二种情况：满足以下条件，系统认定为主窗口： 

1. 设置了 STARTF_USESHOWWINDOW.  

2. 窗口是顶级窗口、无所有者、有WS_CAPTION、不是系统模态窗口 

这种情况下若ShowWindow 的参数为 SW_SHOWNORMAL 或 SW_SHOW，则使用你给定的参数. 

  

于是SW_MAXIMIZE不在此列………… 

好吧，MSDN的文档不全…… 

-- 

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.157] 

※ 修改:・CrLF 于 2011年02月09日17:24 修改本文・[FROM: 60.18.151.188]

novice

69307364

本 文：[转寄][转贴][删除][修改][回复][作者:novice][人气:6]

发信人: novice (Android), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月08日16:27:05 星期二), 站内信件 WWWPOST 

不好意思，没明白你的意思。我能理解，在你列举的两种情况下，如果给ShowWindow提 

供SW_SHOWDEFAULT或者SW_SHOWNORMAL使得窗口按照STARTUPINFO的wShowWindow显示。 

我不能明白的是，MSDN文档里说的，第一次调用ShowWindow忽略nCmdShow参数的情况。 

对于“忽略”一词，我的理解是不管传入什么值，它都按照固定的方式显示。 

调用CreateProcess时给STARTUPINFO赋值，不算提供STARTUPINFO么？ 

【 在 CrLF (CrLF(落羽猫)) 的大作中提到: 】 

: 之前理解错了。查了一下，使用STARTUPINFO 里提供的wShowWindow的条件是：

: 

: 第一种情况：ShowWindow的参数设为SW_SHOWDEFAULT

: 

: 第二种情况：满足以下条件，系统认定为主窗口：

: 1. 设置了 STARTF_USESHOWWINDOW. 

: 2. 窗口是顶级窗口、无所有者、有WS_CAPTION、不是系统模态窗口

: 3. ShowWindow 的参数为 SW_SHOWNORMAL 或 SW_SHOW. 

: 

: 于是SW_MAXIMIZE不在此列…………

: 

: 好吧，MSDN的文档不全……

-- 

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 125.78.224.32] 

※ 修改:・novice 于 2011年02月08日16:28 修改本文・[FROM: 125.78.224.32]

CrLF

53453131364

本 文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:5]

发信人: CrLF (CrLF(落羽猫)), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月08日18:11:36 星期二), 站内信件 WWWPOST 

不是，我查给你的规则是实际的规则（系统实际是这样做的）。msdn文档写的含糊 :) 

信我查的好了。写msdn文档的人肯定没有写windows的人知道的清楚:P 

【 在 novice (Android) 的大作中提到: 】 

: BOOL WINAPI ShowWindow(

:   __in  HWND hWnd,

:   __in  int nCmdShow

: );

: 中 nCmdShow,MSDN中有这么段话：

: This parameter is ignored the first time an application calls ShowWindow, if 

: the program that launched the application provides a STARTUPINFO structure. 

: Otherwise, the first time ShowWindow is called, the value should be the 

: value obtained by the WinMain function in its nCmdShow parameter.

: 

: 要怎么理解？？？

: 

: 我的理解是，如果我用CreateProcess创建某程序，该程序就是创建个窗口，别无其他功

: 能，调用CreateProcess时提供了STARTUPINFO si，并将相应的标志位设置si.dwFlags =

:  STARTF_USESHOWWINDOW，si.wShowWindow = SW_SHOWMINIMIZED.

: 这样的话，即使被创建的程序第一次调用ShowWindow时传入参数 SW_SHOWMAXIMIZED ,程

: 序也应该刚开始是最小化的。因为按照文档说明，参数该被忽略。

: 

: 但实际试验了一下，还是会出现最大化得窗口。不知道我哪里理解错误？

-- 

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.146]

novice

69307364

本 文：[转寄][转贴][删除][修改][回复][作者:novice][人气:3]

发信人: novice (Android), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月08日20:18:32 星期二), 站内信件 WWWPOST 

那意思是 ShowWindow第一次调用与后续调用没区别？ 

【 在 CrLF (CrLF(落羽猫)) 的大作中提到: 】 

: 不是，我查给你的规则是实际的规则（系统实际是这样做的）。msdn文档写的含糊 :)

: 

: 信我查的好了。写msdn文档的人肯定没有写windows的人知道的清楚:P

: 

: 

: 【 在 novice (Android) 的大作中提到: 】

: : BOOL WINAPI ShowWindow(

: :   __in  HWND hWnd,

: :   __in  int nCmdShow

: : );

: : 中 nCmdShow,MSDN中有这么段话：

: : This parameter is ignored the first time an application calls ShowWindow, if 

: : the program that launched the application provides a STARTUPINFO structure. 

: : Otherwise, the first time ShowWindow is called, the value should be the 

: : value obtained by the WinMain function in its nCmdShow parameter.

: : 

: : 要怎么理解？？？

: : 

: : 我的理解是，如果我用CreateProcess创建某程序，该程序就是创建个窗口，别无其他功

: : 能，调用CreateProcess时提供了STARTUPINFO si，并将相应的标志位设置si.dwFlags =

: (以下引言省略...)

-- 

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 125.78.224.32]

CrLF

53453131364

本 文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:3]

发信人: CrLF (CrLF(落羽猫)), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月09日17:28:30 星期三), 站内信件 WWWPOST 

不不，你还是没明白我的意思。 

首先是，不一定是*第一次*调用ShowWindow~  而是第一次对符合主窗口条件（见上面） 

的窗口调用ShowWindow 的时候。 

这个时候如果你用SW_SHOW或SW_SHOWNORMAL，系统会替换。 

你的程序系统认为它是主窗口了，但是你给的是最大化，系统就不管了~ 

【 在 novice (Android) 的大作中提到: 】 

: 那意思是 ShowWindow第一次调用与后续调用没区别？

: 

: 【 在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: : 不是，我查给你的规则是实际的规则（系统实际是这样做的）。msdn文档写的含糊 :)

: : 

: : 信我查的好了。写msdn文档的人肯定没有写windows的人知道的清楚:P

: : 

: : 

: : (以下引言省略...)

-- 

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.188]

novice

69307364

本 文：[转寄][转贴][删除][修改][回复][作者:novice][人气:5]

发信人: novice (Android), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月09日20:12:03 星期三), 站内信件 WWWPOST 

抱歉在这个问题上纠缠这么久。 

再说说我现在的理解。你的意思是：在满足主窗口条件时，第一次调用ShowWindow时使 

用SW_SHOW或SW_SHOWNORMAL，会使窗口按照STARTUPINFO的信息显示？ 

MSDN里文档里说的“忽略”就是上述意思？“This parameter is ignored the first  

time an application calls ShowWindow, if the program that launched the  

application provides a STARTUPINFO structure.”感觉另有深意啊。 

那为什么要称为“ignored”呢？ 因为是上述说法的话，那等同于在SW_SHOW或SW_ 

SHOWNORMAL时，使用STARTUPINFO的信息。而其他参数也按照各自本来的效果显示，并没 

有被忽略。 

感觉你的意思是在说明在什么条件下使用STARTUPINFO的信息，而我最大的疑惑是MSDN文 

档里的“忽略”二字。不对之处请指正。 

【 在 CrLF (CrLF(落羽猫)) 的大作中提到: 】 

: 不不，你还是没明白我的意思。

: 

: 首先是，不一定是*第一次*调用ShowWindow~  而是第一次对符合主窗口条件（见上面）

: 的窗口调用ShowWindow 的时候。

: 

: 这个时候如果你用SW_SHOW或SW_SHOWNORMAL，系统会替换。

: 

: 你的程序系统认为它是主窗口了，但是你给的是最大化，系统就不管了~

: 

: 【 在 novice (Android) 的大作中提到: 】

: : 那意思是 ShowWindow第一次调用与后续调用没区别？

: : 

-- 

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 222.77.201.102] 

※ 修改:・novice 于 2011年02月09日20:25 修改本文・[FROM: 222.77.201.102]

CrLF

53453131364

本 文：[转寄][转贴][删除][修改][回复][作者:CrLF][人气:2]

发信人: CrLF (CrLF(落羽猫)), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月09日23:00:37 星期三), 站内信件 WWWPOST 

it is "ignored" becuase it is "overridden" :) 

MSDN只是没说识别的细节而已。实际上你从设计意图上理解比较好。它之所以这么设计 

，就是为了让写程序的人不用考虑到底该用什么参数。你只要主窗口的ShowWindow用 

WinMain参数里给定的那个，根本不用考虑这些。如果需要在前面显示对话框，就该是模 

态的。如果同时显示对话框，主窗口一般是所有者……总之，为了方便，你什么都不做 

，交给Windows就好。 

【 在 novice (Android) 的大作中提到: 】 

: 抱歉在这个问题上纠缠这么久。

: 

: 再说说我现在的理解。你的意思是：在满足主窗口条件时，第一次调用ShowWindow时使

: 用SW_SHOW或SW_SHOWNORMAL，会使窗口按照STARTUPINFO的信息显示？

: 

: MSDN里文档里说的“忽略”就是上述意思？“This parameter is ignored the first 

: time an application calls ShowWindow, if the program that launched the 

: application provides a STARTUPINFO structure.”感觉另有深意啊。

: 

: 那为什么要称为“ignored”呢？ 因为是上述说法的话，那等同于在SW_SHOW或SW_

: SHOWNORMAL时，使用STARTUPINFO的信息。而其他参数也按照各自本来的效果显示，并没

: 有被忽略。

: 

: 感觉你的意思是在说明在什么条件下使用STARTUPINFO的信息，而我最大的疑惑是MSDN文

: 档里的“忽略”二字。不对之处请指正。

: 

: 【 在 CrLF (CrLF(落羽猫)) 的大作中提到: 】

: : 不不，你还是没明白我的意思。

: : 

: : 首先是，不一定是*第一次*调用ShowWindow~  而是第一次对符合主窗口条件（见上面）

: (以下引言省略...)

-- 

※ 来源:・瀚海星云 bbs.ustc.edu.cn・[FROM: 60.18.151.188] 

※ 修改:・CrLF 于 2011年02月09日23:08 修改本文・[FROM: 60.18.151.188]

novice

69307364

本 文：[转寄][转贴][删除][修改][回复][作者:novice][人气:0]

发信人: novice (Android), 信区: VC 

标  题: Re: ShowWindow 的疑问 

发信站: 瀚海星云 (2011年02月10日09:59:17 星期四), 站内信件 WWWPOST 

it is "ignored" becuase it is "overridden" 。了解了。 

哦哦，那结论是第一次调用时乖乖用WinMain的nCmdShow啦。 

多谢！ 

【 在 CrLF (CrLF(落羽猫)) 的大作中提到: 】 

: it is "ignored" becuase it is "overridden" :)

: 

: MSDN只是没说识别的细节而已。实际上你从设计意图上理解比较好。它之所以这么设计

: ，就是为了让写程序的人不用考虑到底该用什么参数。你只要主窗口的ShowWindow用

: WinMain参数里给定的那个，根本不用考虑这些。如果需要在前面显示对话框，就该是模

: 态的。如果同时显示对话框，主窗口一般是所有者……总之，为了方便，你什么都不做

: ，交给Windows就好。

: 

: 【 在 novice (Android) 的大作中提到: 】

: : 抱歉在这个问题上纠缠这么久。

: : 

: : 再说说我现在的理解。你的意思是：在满足主窗口条件时，第一次调用ShowWindow时使

: : 用SW_SHOW或SW_SHOWNORMAL，会使窗口按照STARTUPINFO的信息显示？

: : 

: : MSDN里文档里说的“忽略”就是上述意思？“This parameter is ignored the first 

: : time an application calls ShowWindow, if the program that launched the 

: : application provides a STARTUPINFO structure.”感觉另有深意啊。

: : 

: : 那为什么要称为“ignored”呢？ 因为是上述说法的话，那等同于在SW_SHOW或SW_

: : SHOWNORMAL时，使用STARTUPINFO的信息。而其他参数也按照各自本来的效果显示，并没

: (以下引言省略...)

给定一个数组，找出不在数组中的最小的那个数字

来源:原文链接

---

这是在TL讨论中Liu xinyu给出的一个例子，觉得思路挺有启发的，所以整理记录一下。
给定一个数组，其内容是一些随机的、不重复的正整数，如：
{4, 23, 1, 8, 9, 21, 6, 12}
要求找出不在数组中出现的最小的那个数，比如这个数组中未在数组中出现的最小值是：2
这个问题实际应用的原型可以是一个ID分配系统，其使用一个数组来保存已分配的ID，每次回收就从数组中删除一个元素(O(n))，而分配则需要找到最小的那个可用的ID，就是这个算法要做的事情。
这个问题从naive的解法到快速的解法的思路转换是十分巧妙的，当然，如果之前没有接触过类似的题，注意到这个特性应该不是一件很容易的事。
设数组为A，大小为n，下标从1开始，下面是一系列逐步改进的算法：
一、穷举查找
一般的问题都可以通过这种很暴力的方式来做，从1到n逐个判断是否在数组中：
MIN-AVAILABLE-NUM(A, n)
for i = 1 to n
do if i not in A
   then return i
      return n+1
显然，这里的算法复杂度是O(n^2)
二、先排序再二分查找
第一种方法，每次查找都是线性查找，要改进最先想到的自然是二分查找，二分查找的前提是有序， 所以：

1. 先排序，用O(nlgn)的快速排序、归并排序或者堆排序；因为数组中的元素是一些自然数，我们甚至可以使用O(n) 的基数排序，当然，需要更多的内存。
2. 对1..n进行判断，复杂度也为O(nlgn)

所以，整体的算法复杂度为O(nlgn)
三、该数组的一个特性
其实仔细观察该数组A[1]..A[n]，我们可以得出一个结论：如果该数组中存在未被使用的数，那么Max(A) > n。
证明很简单，假设Max(A) <= n，由于该数组大小为n，那么该数组中的元素只能是从1到n的某个排列，从而得出该数组中不存在未被使用的数，矛盾。
这个特性和抽屉原理有些类似之处。
从而我们可以有另外一个方法：

1. 先排序
2. 再利用该特性搜索

MIN-AVAILABLE-NUM(A, n)

for i = 1 to n

do A[i] > i

   then return i

      return n+1

注意到，如果我们使用基数排序，可以将复杂度降低到O(n)。
四、一个线性时间，线性空间的算法
第三个算法虽然能达到理论意义上的O(n)，但是基数排序隐含的常数因子较大，而且不是原地排序，这里给出一个不需要排序的算法：
MIN-AVAILABLE-NUM(A, n)
for i = 1 to n
B[i] = 0
for i = 1 to n
do if A[i] < n
   then B[A[i]] = 1
      for  i = 1 to n
if(B[i] == 0) return i;
return n+1;
这里使用一个辅助数组B来表示1到n这些数是否存在在数组A中，只要不存在就将其标为0，最后在B中找到第一个值为0的便是我们要找的那个元素；如果B中元素全为1，这说明A使用了所有1到n这些数，那么返回的便是下一个n+1.
此处无须排序，且复杂度为O(n)，但需要一个额外的O(n)的数组。
五、一个线性时间、常数空间的算法
利用快速排序的原理，我们可以在不使用额外数组的情况下达到O(n)的效率，原理为：
取1到n的中间值m = (1 + n)/2，用m将数组分成A1, A2两个部分，A1中的元素全部小于等于m，A2中的元素全部大于m（注意此处用的是下标，而不是A[m]），如果A1的大小为m，则空闲元素在A2中，这在前面证明过，然后就在A2中应用同样的方法。
MIN-AVAILABLE-NUM(A, low, up)
if(low == up) return low
m = (low + up) / 2
split = partition(A, low, up, m)
if a[split] == m
  then return MIN-AVAILABLE-NUM(A, low, split)
      else return MIN-AVAILABLE-NUM(A, split+1, up)
这里递归式为：T(n) = T(n/2) + O(n)，根据主定理的第三种情况，复杂度为O(n)，其实也就是一个等比数列：n + n/2 + n/4...