一、算法一词的来源

Algos是希腊字，意思是“疼”，A1gor是拉丁字，意思是“冷却”。这两个字都不是Algorithm(算法)一词的词根，a1gorithm一词却与9世纪的阿拉伯学者al-Khwarizmi有关，他写的书《al-jabr w’al muqabalah》(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题的有条理的步骤。如果他能活到今天的话，他一定会被以他的名字而得名的方法的进展所感动。

二、20世纪10最好的算法

20世纪最好的算法，计算机时代的挑选标准是对科学和工程的研究和实践影响最大。下面就是按年代次序排列的20世纪最好的10个算法。

1. Monte Carlo方法
1946年，在洛斯阿拉莫斯科学实验室工作的John von Neumann，Stan Ulam和Nick Metropolis编制了Metropolis算法，也称为Monte Carlo方法。Metropolis算法旨在通过模仿随机过程，来得到具有难以控制的大量的自由度的数值问题和具有阶乘规模的组合问题的近似解法。数字计算机是确定性问题的计算的强有力工具，但是对于随机性（不确定性）问题如何当时并不知晓，Metropolis算法可以说是最早的用来生成随机数，解决不确定性问题的算法之一。

2. 线性规划的单纯形方法
1947年，兰德公司的Grorge Dantzig创造了线性规划的单纯形方法。就其广泛的应用而言，Dantzig算法一直是最成功的算法之一。线性规划对于那些要想在经济上站住脚，同时又有赖于是否具有在预算和其他约束条件下达到最优化的能力的工业界，有着决定性的影响(当然，工业中的“实际”问题往往是非线性的；使用线性规划有时候是由于估计的预算，从而简化了模型而促成的)。单纯形法是一种能达到最优解的精细的方法。尽管理论上讲其效果是指数衰减的，但在实践中该算法是高度有效的——它本身说明了有关计算的本质的一些有趣的事情。

3. Krylov子空间叠代法
1950年，来自美国国家标准局的数值分析研究所的Magnus Hestenes, Eduard Stiefel和Cornelius Lanczos开创了Krylov子空间叠代法的研制。这些算法处理看似简单的求解形为Ax=b的方程的问题。当然隐藏的困难在于A是一个巨型的n*n 矩阵，致使代数解x=b/A是不容易计算的(确实，矩阵的“相除”不是一个实际上有用的概念)。叠代法——诸如求解形为Kx(k+1)=Kx(k)+b-Ax(k)的方程，其中K 是一个理想地“接近”A 的较为简单的矩阵——导致了Krylov子空间的研究。以俄罗斯数学家Nikolai Krylov命名的Krylov子空间由作用在初始“余量”向量r(0)=b-Ax(0)上的矩阵幂张成的。当 A是对称矩阵时，Lanczos找到了一种生成这种子空间的正交基的极好的方法。对于对称正定的方程组，Hestenes 和Stiefel提出了称为共轭梯度法的甚至更妙的方法。过去的50年中，许多研究人员改进并扩展了这些算法。当前的一套方法包括非对称方程组的求解技巧，像字首缩拼词为GMRES和Bi-CGSTAB那样的算法。(GMRES和Bi-CGSTAB分别首次出现于1986和1992 SIAM journal on Scientific and Statistical computing(美国工业与应用数学学会的科学和统计计算杂志)。

4. 矩阵计算的分解方法
1951年，橡树岭国家实验室的A1ston Householder系统阐述了矩阵计算的分解方法。研究证明能把矩阵因子分解为三角、对角、正交和其他特殊形式的矩阵是极其有用的。这种分解方法使软件研究人员能生产出灵活有效的矩阵软件包。这也促进了数值线性代数中反复出现的大问题之一的舍入误差分析问题。 (1961年伦敦国家物理实验室的James Wilkinson基于把矩阵分解为下和上三角矩阵因子的积的LU分解，在美国计算机协会(ACM)的杂志上发表了一篇题为“矩阵逆的直接方法的误差分析”的重要文章。)

5. Fortran最优编译程序
1957年，John Backus在IBM领导一个小组研制Fortran最优编译程序。Fortran的创造可能是计算机编程历史上独一无二的最重要的事件：科学家(和其他人)终于可以无需依靠像地狱那样可怕的机器代码，就可告诉计算机他们想要做什么。虽然现代编译程序的标准并不过分――Fortran I只包含23，500条汇编语言指令――早期的编译程序仍然能完成令人吃惊的复杂计算。就像Backus本人在1998年在IEEE annals of the History of computing 发表的有关Fortran I，II, III的近代历史的文章中回忆道：编译程序“所产生的如此有效的代码，使得其输出令研究它的编程人员都感到吓了一跳。”

6. 矩阵本征值计算的QR算法
1959—61年，伦敦Ferranti Ltd.的J.G. F. Francis找到了一种称为QR算法的计算本征值的稳定的方法。本征值大概是和矩阵相连在—起的最重要的数了，而且计算它们可能是最需要技巧的。把—个方阵变换为一个“几乎是”上三角的矩阵――意即在紧挨着矩阵主对角线下面的一斜列上可能有非零元素――是相对容易的，但要想不产生大量的误差就把这些非零元素消去，就不是平凡的事了。QR 算法正好是能达到这一目的的方法，基于QR 分解， A可以写成正交矩阵Q 和一个三角矩阵R 的乘积，这种方法叠代地把 A=Q(k)R(k) 变成 A(k+1)==Q(k)R(k) 就加速收敛到上三角矩阵而言多少有点不能指望。20世纪60年代中期QR 算法把一度难以对付的本征值问题变成了例行程序的计算。

7. 快速分类法
1962：伦敦Elliott Brothers, Ltd.的Tony Hoare提出了快速(按大小)分类法.把n个事物按数或字母的次序排列起来，在心智上是不会有什么触动的单调平凡的事。智力的挑战在于发明一种快速完成排序的方法。Hoare的算法利用了古老的分割开和控制的递归策略来解决问题：挑一个元素作为“主元”、把其余的元素分成“大的”和“小的”两堆(当和主元比较时)、再在每一堆中重复这一过程。尽管可能要做受到严厉责备的做完全部N(N-1)/2 次的比较(特别是，如果你把主元作为早已按大小分类好的表列的第一个元素的话！)，快速分类法运行的平均次数具有O(Nlog(N)) 的有效性，其优美的简洁性使之成为计算复杂性的著名的例子。

8. 快速Fourier变换
1965年，IBM的T. J. Watson研究中心的James Cooley以及普林斯顿大学和AT＆T贝尔实验室的John Tukey向公众透露了快速Fourier变换(方法)(FFT)。应用数学中意义最深远的算法，无疑是使信号处理实现突破性进展的FFT。其基本思想要追溯到Gauss(他需要计算小行星的轨道)，但是Cooley—Tukey的论文弄清楚了Fourier变换计算起来有多容易。就像快速分类法一样，FFT有赖于用分割开和控制的策略，把表面上令人讨厌的O(N*N) 降到令人欢乐的O(Nlog(N)) 。但是不像快速分类法，其执行(初一看)是非直观的而且不那么直接。其本身就给计算机科学一种推动力去研究计算问题和算法的固有复杂性。

9. 整数关系侦查算法
1977年，BrighamYoung大学的Helaman Ferguson 和Rodney Forcade提出了整数关系侦查算法。这是一个古老的问题：给定—组实数，例如说x(1),x(2),…,x(n) ，是否存在整数a(1),a(2),..,a(n) （不全为零），使得a(1)x(1)+a(2)x(2)+…+a(n)x(n)=0对于n=2 ，历史悠久的欧几里得算法能做这项工作、计算x(1)/x(2) 的连分数展开中的各项。如果x(1)/x(2) 是有理数，展开会终止，在适当展开后就给出了“最小的”整数a(1)和a(2) 。欧几里得算法不终止——或者如果你只是简单地由于厌倦计算——那么展开的过程至少提供了最小整数关系的大小的下界。Ferguson和Forcade的推广更有威力，尽管这种推广更难于执行(和理解)。例如，他们的侦查算法被用来求得逻辑斯谛(logistic)映射的第三和第四个分歧点，b(3)=3.544090 和 b(4)=3.564407所满足的多项式的精确系数。(后者是120 阶的多项式；它的最大的系数是257^30 。)已证明该算法在简化量子场论中的Feynman图的计算中是有用的。

10. 快速多极算法
1987年，耶鲁大学的Leslie Greengard 和Vladimir Rokhlin发明了快速多极算法。该算法克服了N体模拟中最令人头疼的困难之一：经由引力或静电力相互作用的N个粒子运动的精确计算(想象一下银河系中的星体，或者蛋白质中的原于)看来需要O(N*N) 的计算量——比较每一对质点需要一次计算。该算法利用多极展开(净电荷或质量、偶极矩、四矩，等等)来近似遥远的一组质点对当地一组质点的影响。空间的层次分解用来确定当距离增大时，比以往任何时候都更大的质点组。快速多极算法的一个明显优点是具有严格的误差估计，这是许多算法所缺少的性质。

Ken Thompson，1943年出生于美国新奥尔良。1960年，Ken进入加州大学伯克利分校主修电气工程。1965年从伯克利毕业后，又花了一年的时间 在该校取得了电子工程硕士的学位。不知道是时代造就英雄，还是英雄顺应时代而生，在Ken读书期间，正好赶上了计算机时代蓬勃发展的起步阶段，自小喜欢电 气的Ken接触到计算机后，立即完全沉迷了进去，从1962年的开始，他就在学校的计算机中心找到份工作，专门负责程序的编写。这也为其后他一手开创的 Unix时代奠定了良好基础。

1966年离开校园的Ken加入了贝尔 实验室。那时的计算机系统还是批处理的天下，程序员只能在又慢又笨重大型机上工作，一般来讲是先将程序卡片装入设备，然后再等1个小时再过来取回运算的结 果，其效率之低可想而知。应市场的需要，当时贝尔实验室与麻省理工学院以及通用电气公司联合开发了一个多用户分时操作系统，取名为Multics(多路信 息计算系统)，Ken当时就是这个系统的开发人员之一，在开发Multics的期间，Ken创造出了名为Bon的编程语言。可惜因为这个系统不但开发周期 长，成本高，而且庞大而缓慢，市场前景完全不被看好，最后贝尔实验室从这个项目中撤了出来。这对于Ken而言，简直是个巨大的不幸，因为他自己用写的一个 “star travel”游戏就是完全基于Multics的，退出Multics项目意味着Ken将没有机器可以再玩这个游戏了。

面对此情此景，Ken作为一个创造者的 本性立即体现了出来，于是他决定自己写一个操作系统来满足他玩游戏的需要，说干就干，Ken找到了一台废弃已久的老式PDP-7，并在这台机器上重写了他 的游戏。在这个过程中，Ken有了一个主意，要开发一个全新的操作系统。利用PDP-7上的汇编语言，Ken只花了一个月就编写完了操作系统的内核，在这 个一个月中，他一周一个内核，一个文件系统，一个编辑器和一个编译程序的完成。做完这个系统后，Ken将其命名为 UNiplexed Information and Computing System，缩写为 UNICS，后来做了一下改动，称为UNIX，在开发第一版Unix的过程中，Ken还开发出一种新的语言，即C语言的前身——B 语言，这种语言简洁明了，接近于硬件语言，第一版的Unix就是基于B语言来开发的。

Unix的出现开始虽然并不为大家所看 好，但是却引起了贝尔实验室另一位同事的注意，这就是Dennis M. Ritchie，于是Dennis主动加入了进来共同完善这个系统。至此一场轰轰烈烈的Unix的传奇时代才真正的拉开了序幕。1972年，他们联手将 Unix移植到当时最先进的大型机PDP-2上，由于Unix是如此的简洁、稳定与高效，以至于当时大家都放弃了PDP-2上自带的DEC操作系统，而完 全改用Unix，这时的Unix已经开始走向成熟了。在1973年之前Unix还不太为外界所知，到同年10月，Unix在IBM举办的操作系统原理专题 研讨会上被提及，当Ken和Dennis在会上宣读论文并展示Unix后，整个会场轰动了，大家都立即涌上来索取这种新型的操作系统的程序。随着Unix 的需求量的日益增加，Ken与Dennis决定将Unix进一步改写，以便可以移植到各种不同的硬件系统，由于Unix的原码中不少是用汇编完成，不具备 良好的移植性，正好Dennis在1973年在B语言的基础上开发出了C语言，C语言灵活，高效性，与硬件无关，并且不失其简洁性，正是Unix移植所需 要的法宝，于是旧版的Unix与C语言完美结合在一起产生了新的可移植的Unix系统。随着Unix的广泛使用，C语言也成为了当时最受欢迎的编程语言一 直到延续至令。

说到Unix与C语言，还有一段小故 事，当时安装了Unix的PDP-11被放在贝尔实验室供大家使用，有一天大家伙发现Ken总是可以得到最高的权限轻松进入他们的帐户，在贝尔实验室这种 高人云集的地方，这简单是太不能容忍了，于是有若干高人跳了出来，仔细分析Unix代码，找到后门，修改后再重新编译整个Unix，当所有人都以为这个世 界应该从此清静了的时候，却发现Ken还是很容易就取得了他们的帐户权限，为此大家郁闷不已。至到很多年后，Ken才道出其中的原委，原来代码里确实存在 后门，不过并不在Unix代码中，而是藏在编译Unix的编译器里，每次编译器编译时就会自动加入后门代码，而当时整个贝尔实验室都用的是Ken所写的C 编译器。

由于Unix与C语言的深远影 响，1983年美国计算机协会将当年的图灵奖破例颁给了作为软件工程师的Ken与Dennis，并在当年还决定新设立一个奖项――软件系统奖，以奖励那些 优秀的软件开发者，当然首个软件系统奖也是非他们两人莫属了。虽然Unix与C语言让Ken与Dennis功成名就，但是他们两人都没有走那些IT史上自 己创业的通用套路，而是一直留在贝尔实验室从事其喜爱的软件开发工作。到了2000年12月时，Ken正式退休，离开了工作了几十年的贝尔实验室开始享受 他晚年的时光，但是Ken怎么能闲得下来呢，于是他干脆将他的另一个爱好：飞机，变成正式的职业，成为了一名专职的飞行员。至此，他所开创的Unix时代 已经完全与他无关了。

冒泡排序

排序方法

将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上”飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

（1）初始

R[1..n]为无序区。

（2）第一趟扫描

从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置。即依次比较(R[n]，R[n-1])，(R[n-1]，R[n-2])，…，(R[2]，R[1])；对于每对气泡(R[j+1]，R[j])，若R[j+1].key<R[j].key，则交换R[j+1]和R[j]的内容。

第一趟扫描完毕时，”最轻”的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[1]上。

（3）第二趟扫描

扫描R[2..n]。扫描完毕时，”次轻”的气泡飘浮到R[2]的位置上……

最后，经过n-1 趟扫描可得到有序区R[1..n]

注意：

第i趟扫描时，R[1..i-1]和R[i..n]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[1..i]变为新的有序区。

复杂度分析:

（1）算法的最好时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：

Cmin=n-1

Mmin=0。

冒泡排序最好的时间复杂度为O(n)。

（2）算法的最坏时间复杂度

若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax=n(n-1)/2=O(n2)

Mmax=3n(n-1)/2=O(n2)

冒泡排序的最坏时间复杂度为O(n2)。

（3）算法的平均时间复杂度为O(n2)

虽然冒泡排序不一定要进行n-1趟，但由于它的记录移动次数较多，故平均时间性能比直接插入排序要差得多。

（4）算法稳定性

冒泡排序是就地排序，且它是稳定的。

更多:

冒泡排序的不对称性

能一趟扫描完成排序的情况：

只有最轻的气泡位于R[n]的位置，其余的气泡均已排好序，那么也只需一趟扫描就可以完成排序。

【例】对初始关键字序列12，18，42，44，45，67，94，10就仅需一趟扫描。

需要n-1趟扫描完成排序情况：

当只有最重的气泡位于R[1]的位置，其余的气泡均已排好序时，则仍需做n-1趟扫描才能完成排序。

【例】对初始关键字序列：94，10，12，18，42，44，45，67就需七趟扫描。

造成不对称性的原因

每趟扫描仅能使最重气泡”下沉”一个位置，因此使位于顶端的最重气泡下沉到底部时，需做n-1趟扫描。

改进不对称性的方法

在排序过程中交替改变扫描方向，可改进不对称性。具体算法。

冒泡排序C++代码：

void bubbleSort(int arr[], int n) {
      bool swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < n - j; i++) {
                  if (arr[i] > arr[i + 1]) {
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }
      }
}

冒泡排序Java代码：

public void bubbleSort(int[] arr) {
      boolean swapped = true;
      int j = 0;
      int tmp;
      while (swapped) {
            swapped = false;
            j++;
            for (int i = 0; i < arr.length - j; i++) {
                  if (arr[i] > arr[i + 1]) {
                        tmp = arr[i];
                        arr[i] = arr[i + 1];
                        arr[i + 1] = tmp;
                        swapped = true;
                  }
            }
      }
}

快速排序

算法思想:
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

（1） 分治法的基本思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

（2）快速排序的基本思想
设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解：
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
注意：
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合：
因为当”求解”步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，”组合”步骤无须做什么，可看作是空操作。

快排C++代码：

void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

快排Java代码：

int partition(int arr[], int left, int right)
{
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      return i;
}

void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

选择排序

算法原理:

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有

序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无

序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

复杂度分析:

（1）关键字比较次数
无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：
n(n-1)/2=0(n2)

（2）记录的移动次数
当初始文件为正序时，移动次数为0
文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。
直接选择排序的平均时间复杂度为O(n2)。

（3）直接选择排序是一个就地排序

（4）稳定性分析
直接选择排序是不稳定的
【例】反例[2，2，1]

选择排序C++代码：

void selectionSort(int arr[], int n) {
      int i, j, minIndex, tmp;
      for (i = 0; i < n - 1; i++) {
            minIndex = i;
            for (j = i + 1; j < n; j++)
                  if (arr[j] < arr[minIndex])
                        minIndex = j;
            if (minIndex != i) {
                  tmp = arr[i];
                  arr[i] = arr[minIndex];
                  arr[minIndex] = tmp;
            }
      }
}

选择排序Java代码：

public void selectionSort(int[] arr) {
      int i, j, minIndex, tmp;
      int n = arr.length;
      for (i = 0; i < n - 1; i++) {
            minIndex = i;
            for (j = i + 1; j < n; j++)
                  if (arr[j] < arr[minIndex])
                        minIndex = j;
            if (minIndex != i) {
                  tmp = arr[i];
                  arr[i] = arr[minIndex];
                  arr[minIndex] = tmp;
            }
      }
}

使用301重定向 btbuzz.com 到www.btbuzz.com 可以防止网站流量的分流，优化网页收录，有利于网页PR传递，等等。在此不多说了。

在godaddy的linux主机上进行301重定向是很简单的，只需要修改主机.htaccess文件即可。具体的方法google一下有一大把在此也不多说了。但是很多人对在godaddy的windows虚拟主机中进行301 重定向却很陌生。

本文介绍一种在Windows虚拟主机下，尤其是godaddy的虚拟主机下从btbuzz.com通过301重定向到 www.btbuzz.com的方法。该方法在godaddy的windows虚拟主机中实现起来相当方便。当然有一个前提条件就是：windows主机使用的是IIS7.0或以上版本。 具体方法如下：

如果你的网站没有web.config文件。在网站的根目录下新建web.config文件并将一下代码加入到文件中。

<configuration>
   <system .webServer>
      <rewrite>
         <rules>
            <rule name="WWW Redirect" stopProcessing="true">
              <match url=".*" />
                 <conditions>
                    <add input="{HTTP_HOST}" pattern="^btbuzz.com$" />
                 </conditions>
              <action type="Redirect" url="http://www.btbuzz.com/{R:0}" redirectType="Permanent" />
            </rule>
         </rules>
      </rewrite>
   </system>
</configuration>

如果你的网站已经有了web.config文件。修改你的web.config文件。在web.config文件… 中的最后一行后面添加以下代码：

<rule name="WWW Redirect" stopProcessing="true">
  <match url=".*" />
    <conditions>
       <add input="{HTTP_HOST}" pattern="^btbuzz.com$" />
    </conditions>
       <action type="Redirect" url="http://www.btbuzz.com/{R:0}" redirectType="Permanent" />
</rule>

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

比如将二叉搜索树

         10
     /         \
   6          14
/    \        /   \
4     8   12      1

转换成双向链表 4=6=8=10=12=14=16。

解题分析：很多与树相关的题目都是用递归的思路来解决，本题也不例外。下面我们用两种不同的递归思路来分析。

思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。

思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

代码：

READ MORE…

问题描述：将char[]的字符串转换为int类型的整数并将int类型的整数转换为char[] 的字符串。其中字符串中只有0-9数字和‘-’。

解题关键：应用到了霍纳法则，这个思想很简单但是很重要，在手算和计算机的运算中能节省大量的运算量。因为人脑和计算机在进行加减运算时都快过乘除运算。

相关概念：霍纳法则(Horner Rule) 又名秦九昭法。

把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+……+a[1]x+a[0]改写成如下形式： f(x)=a[n]x^n+a[n-1]x^(n-1))+……+a[1]x+a[0] =(a[n]x^(n-1)+a[n-1]x^(n-2)+……+a[1])x+a[0] =((a[n]x^(n-2)+a[n-1]x^(n-3)+……+a[2])x+a[1])x+a[0] =…… =(……((a[n]x+a[n-1])x+a[n-2])x+……+a[1])x+a[0]. 求多项式的值时，首先计算最内层括号内一次多项式的值，即 v[1]=a[n]x+a[n-1] 然后由内向外逐层计算一次多项式的值，即 v[2]=v[1]x+a[n-2] v[3]=v[2]x+a[n-3] …… v[n]=v[n-1]x+a[0] 这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。 （注：中括号里的数表示下标） 上述方法称为秦九韶算法。直到今天，这种算法仍是多项式求值比较先进的算法 该算法看似简单，其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值。在人工计算时，利用秦九韶算法和其中的系数表可以大幅简化运算；对于计算机程序算法而言，加法比乘法的计算效率要高很多，因此该算法仍有极大的意义，用于减少CPU运算时间。—From 百度百科

代码：

READ MORE…

函数声明：BinarySearch(int *array, int lower, int upper, int target);

二分法查找的迭代方法
代码： READ MORE…

问题描述：反转一句话中的单词顺序而不改变每个单词，标点符号算入单词当中。如：”What a good day!”反转之后为”day! good a What”

解题关键：这道题目并不难，难的是如何优化空间复杂度。通常来说需要一个跟原文大小相同的buffer以及一个临时的存放单词的buffer，但是如果我们使用在问题<<去除字符串中指定的字符>>中类似的int 类型的标记，则我们可以省掉两个buffer。

代码： READ MORE…

问题描述：去除一个以ASCII码为字符的字符串中指定的字符集，如输入：asdfg sg,结果为adf。 要求的函数声明: RemoveChars(char str[], char remove[]);

解题关键：此问题第一想法是两个循环嵌套遍历，这样的时间复杂度为O(mn),而数组需要不定的移动删除之后的剩余字符串，所以需要一个buffer长度为数组大小。但是当字符串为一段长文字而且去除字符的数量m很大时，复杂度便会上升。为了降低开销可以使用问题 <<查找字符串中第一个不重复的字母>>中所使用到的索引的方法，实际上此题是上一题的延伸和扩展，并且对空间使用上也有更高的要求。在空间上，完全可以避免使用buffer并且做到每个字符只被copy一次，使用两个int 变量作为标记，标记当前查找的字符位置和删除了相应字符之后当前新字符串的位置。这样在同一个字符串上进行两个标记src 和 dst的同时移动并且copy移动之前的字符。

代码：

READ MORE…

问题描述：查找字符串中第一个不重复的字母（假设字母仅包括a-z的小写字母）。如：attal中第一个不重复的字母为l。

解题关键：首先所有字母必须要遍历一遍，所以复杂度至少O(n)，而如果和其他的字符都做比较则复杂度最多为O(n2)。我们需要寻找一种数据结构可以在最短时间内对字符串中的字母进行有效的搜索。

代码：

READ MORE…