白话算法(1) for循环不是随便写的

　在杨修的那些颇具传奇色彩的小故事里面，有一个是最能体现他是如何的聪明，却又没有用到正地方的，说的是杨修身为曹操主簿，却又不肯老老实实坐在办公室里，老想溜出去玩，可是又怕曹操有问题要问，于是每当外出时，都要事先揣度曹操的心思，写出答案，按次序写好，并吩咐侍从，如果丞相有令传出，就按这个次序一一作答，结果每次都严丝合缝，没出过一点差错。可是后来有一次吹来一阵风，把纸张的顺序弄乱了。侍从按乱了的次序作答，自然文不对题，结果露了馅。
　　不过我怎么都不觉得这是小聪明。要我说，这简直就是奇迹。即使是曹操问一题、杨修答一题的模式，能够全部回答出来就已经算得上是很聪明、很有才了。但是，杨修所做的事情却是，他不但可以预先判断出问题的内容，就连问题的数量和顺序也能丝毫不差地预先判断出来，这可就有些神了。如果杨老师给高考押题的话，那就不叫押题，那看上去根本就是泄题，估计也是难逃一死。

算法设计的一个常用思路

　　但是身为程序员，却必须时不时地扮演一下杨修。不信？准备接招：实现一个函数“int[] Sort(int[] s)”；输入：一个长度不确定、元素不确定、顺序不确定的数组；输出：按从小到大的顺序排列的数组。
　　例如：输入：{ 3, 1 }; 输出：{ 1, 3 }。
输入：{ 5, 2, 1, 4, 6, 7, 3 }; 输出：{ 1, 2, 3, 4, 5, 6, 7 }。
　　我们圈里人都知道，计算机里面其实并没有一个小妖精手忙脚乱地替我们工作。如果说计算机知道怎么工作，那是因为我们程序员预先判断出了所有可能的输入情况，并且告诉计算机在每种情况下应该怎么处理。但是，我们看到，输入的元素个数是不确定的，并且是无序的，这两个特点将导致输入的状态是无限多的，所以，我们不可能像杨修那样写程序：

asp-algorithm1.html#viewSource" commandName="viewSource" highlighterId="highlighter_709306">view sourceprint?

01 int[] Sort(int[] s)

02 {

03     if(IsArrayEquals(s, new int[] { 2, 1, 3 }))

04         return new int[] { 1, 2, 3 }

05     else if(IsArrayEquals(s, new int[] { 3, 1, 2 }))

06         return new int[] { 1, 2, 3 }

07     else if(IsArrayEquals(s, new int[] { 7, 6, 5, 9 }))

08         return new int[] { 5, 6, 7, 9 }

09     ...

10 }

　　那么，我们如何把具有无限多个状态的无序的集合（输入）转化为有序的集合（输出）呢？（注：这里的“有序”可以不仅仅指“有顺序”，而是可以更宽泛一点，指“有一定规律”）。一个常见的思路是：
　　1）首先处理输入的一个子集。由于这个子集的元素个数是有限的，它的状态必然是有限的，所以我们就有可能找到一个方法把这个子集处理成有序的。
　　2）向这个有序的子集加入更多的元素，并保持它的有序性，直到子集扩展到整个输入。既然子集会扩展成整个输入，那么子集的元素个数必然也会是不确定（无限多）的，所以很关键的一点是，如果我们想在扩展它的同时保持它的有序性，就必须找到一个方法可以把一个元素个数不确定但是有序的集合抽象成只有有限个状态的系统。
　　下面让我们来看一个实例。

插入排序

      插入排序算法就像我们一边抓扑克牌，一边排列扑克牌的顺序那样。
      假设输入是：{ 4, 2, 5, 10, 7 }
      在这里，我们定义“有序”的集合是一个“元素按从小到大的顺序排列”的集合。
      输入自然是无序的。

补充：综合编程 , 其他综合 ,