排序算法之插入排序 插入排序一般分为直接插入排序和二分插入插入排序。直接插入排序又可以分为前插和后插，不过虽然是这样分，只是寻找地点的方向不一样而已。“前插”就是从头开始找合适的位置，“后插”就是从后面开始找合适的位置。这里我们只讨论“后插”。直接插入排序的思想很简单，开始时，整个数组都是无序的，默认第一个数是排好序的，然后要把第二个数插入到前面，那么就要找到合适的位置插入，从当前数的前一个数$a与当前数$s进行比较，如果此时$a$j+1; $k--){ $a[$k] = $a[$k-1]; } //将当前的数据放在找到的位置 $a[$j+1] = $s;21 } } 还有就是二分插入排序，二分插入排序只不过查找的方式不同而已。每次要插入的值$a[$i]总是与前面已排好序的中间的值$a[$mid]进行比较，如果$a[$i]比较小则在前面的区间继续二分查找，否则在后面的区间。function binarySort(&$a){ $t = count($a); for($i=1; $i=$left; $k--){ $a[$k] = $a[$k-1]; } //将当前的数据放在找到的位置 $a[$left] = $s; } } 插入排序也是一种简单的排序方式。

排序算法之快速排序 终于讲到了排序的重点了。快排即使不是排序中最经典的算法，能算上是非常出色的算法了 1. 快排简介 # 快速排序是一种基于分治技术的重要排序算法，是冒泡算法的一种改进。是由东尼.霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要O(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 2. 快排原理 # 快速排序用分治的思想，将一个整串分为两个子串。左边子串中所有的数都不会大于右边子串中的数。步骤为： 从数组中挑选一个数作为“中轴”，（选择中轴有许多不同的策略，不过我们一般会选择数组的第一个元素）。 重新排列数组，使得所有比中轴小的元素放在中轴的左边，所有比中轴大的元素放在中轴的右边，中轴元素放在中间。当然，跟中轴相等的数放在哪边都无所谓。 按上述步骤递归执行新生成的子串。 递归的最底层是零个或者一个数，也就说是已经排好序的。 3. 时间和空间复杂度 # 我看了网上很多的数学证明，也不想多说。再说，即使用数学证明出来了，实际应用也是另一回事。我到现在也就知道快排的最好、平均和最坏的时间复杂度，而没有去纠结是怎么证明出来的（或许这样不好吧）。最好：O(nlogn), 平均:O(1.38nlogn，也就是nlogn)，最坏：O(n2)。平均情况下只比最好情况多执行38%的比较操作，不过最坏情况下就已经是平方的数量级了。被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分区的快速排序版本，在任何递归调用前，仅会使用固定的額外空間。然而，如果需要产生O(logn)嵌套递归调用，它需要在他们每一个存储一个固定数量的信息。因为最好的情况最多需要O(log n)次的嵌套递归调用，所以它需要O(log n)的空间。最坏情况下需要O(n)次嵌套递归调用，因此需要O(n)的空间。然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log2 n)空间的比特数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，因为如果一个数列大部份都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。非原地版本的快速排序，在它的任何递归调用前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递归的每一阶中，使用与上一次所使用最多空间的一半，且2n。它的最坏情况是很恐怖的，需要O(n2)空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部份都是不同的，每一个将会需要大约O(logn)为原来存储，导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。 4. 算法 # 具体算法如下：//交换两个数 function swap(&$x, &$y){ $temp = $x; $x = $y; $y = $temp; } function partition(&$a, $left, $right){ $p = $a[$left]; $i = $left; $j = $right+1; do{ //寻找大数 do{ $i++; }while($a[$i]=$i); //交换 swap($a[$i], $a[$j]); }while($i=$right){ return; } $mid = partition($a, $left, $right); quickSort($a, $left, $mid); quickSort($a, $mid+1, $right); } 5. 快排思想 # 快排的算法很简单，而且大部分高级语言的排序库函数都是用的快排。不过我们从快排的这个分治思想中还是能够学到很多的东西的。 第一个就是在数量级很大的数中寻找第j大（小）的数，这个j一般小于等于10，比如在100万个数中找出第3小的数。我们通常的想法是用一种最快的排序算法，比如堆排序或者归并排序，将整个数组排好序之后取出第三个数。这样时间复杂度是O(nlogn)。可是如果我们用快排的思想，只需要O(n)的时间复杂度就行了。因为我们就是要的第3小的数，而不关心其他的数是第几，因此我们只需要取出下标是2（下标从0开始）数就是第三小的数了。因此，我们改进一下quickSort()函数，在返回$mid后，判断一下$mid与3的大小。如果正好等于3那么正好找到了，如果比3大，那么我们需要在后面的部分找，否则我们在前面的部分找。 在大数量级中找出前10个最小的数，这个与第一种情况是一样的，只需要检测返回的$mid值就行了，不过这个返回的是一个数组罢了。 在有n个实数组成的数组中，有正数，有负数，怎样让所有的负数都位于正数之前。这个通过快排就非常好解决了。我们自己可以认为地引入一个0，然后对数组进行一次快速排序就可以了。 好的，快排就先这样吧。

排序算法之归并排序 归并排序是成功应用分治技术的一个完美例子。分治法的思想是： 将问题的实例划分为同一个问题的几个较小的实例，最好拥有同样的规模； 对这些较小的实例求解（一般用递归方法，但在问题规模足够小的时候。有时也会利用另一个算法）； 如果必要的话，合并这些较小问题的解，以得到原始问题的解。 对于一个需要排序的数组$a[0...n-1]，归并排序把它一分为二：$a[0..n/2-1]和$a[n/2...n-1]，并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。下面的这个图能够很好地解释归并排序的整个流程（自己画的，有点丑）。看上面的图，我们就知道了。递归的将一个数组分成两部分，直到小的足以解决问题就不再递归（一个数，一定是有序的）。然后再将两个有序的数组合并，最后整个数组就是有序的了。算法如下：/** * 归并排序 * 递归调用mergeSort来对数组$a排序 * @param $a 一个可排序的数组 * @return $a 非降序排列的数组 */ function mergeSort(&$a){ $t = count($a); if($t

排序算法之总结 原本还打算写希尔排序和堆排序呢，不过由于时间原因也只能写这些排序了。下面总结和对比一下常用的排序方法吧。 冒泡和选择排序 插入排序 快速排序 归并排序 1. 排序方式 # 插入排序：直接插入排序，二分插入排序，表插入排序，希尔插入排序；选择排序：直接选择排序，树形选择排序，堆排序；交换排序：冒泡排序，快速排序。还有归并排序、基数排序，等等。 2. 稳定性 # 稳定的：冒泡排序，双向冒泡排序（鸡尾酒排序），插入排序，计数排序，归并排序，二叉排序树排序，基数排序，等。不稳定的：选择排序。希尔排序，组合排序，堆排序，快速排序，等。 3. 时间复杂度 # 排序算法 最优情况 最坏情况 平均情况 冒泡排序 O(n2) O(n2) O(n2) 插入排序 O(n2) O(n2) O(n2) 选择排序 O(n2) O(n2) O(n2) 快速排序 O(nlogn) O(n2) O(nlogn) 堆排序 O(nlogn) O(nlogn) O(nlogn) 归并排序 O(nlogn) O(nlogn) O(nlogn) 基数排序 O(n) O(n) O(n) 希尔排序 0 0 O(n1.25) 4. 总结 # 为什么会出现这么多的排序算法，因为没有一个算法能在任何情况下都是最优的，两个算法之间的比对总是在一定的数据量级下进行的。还有就是人们希望能够找到一种更快的排序方式。有些人做过测试，在数据量越大的情况下，快排的优势就越明显。

异步传输ajax 什么是异步传输，首先让我们看看传统的数据加载方式“同步传输”，传统的页面加载一般是从上开始往下加载的，当需要加载 js 的时候，是阻塞加载，当引用了 js 的时候，浏览器发送一个 js request 就会一直等待该 request 的返回。因此这样写会提示错误的： up document.getElementById("ss").innerHTML = "sdfsdf"; dfgdfg 网页上依然会显示"dfgdfg"，而不是执行 js 语句后的形态。使用“谷歌浏览器”审查元素就会发现，提示 Uncaught TypeError: Cannot set property 'innerHTML' of null。可是如果将 script 块放在 div 的后面就会正常，因为在浏览器从上往下开始解析的时候，解析到第 6 行的时候，浏览器根本不知道 ss 这个元素的存在，因此会进行报错，可是如果把 js 放在后面，在浏览器解析到 document.getElementById("ss")时，已经知道了 ss 是什么东西了，因此浏览器会显示"sdfsdf"。现在我们再来谈一下传统的 web 请求，在传统的 web 应用中，允许用户填写表单，当提交表单时就向 web 服务器发送一个请求，服务器接收并处理传来的表单，然后返回一个新的网页。可是这样的作法很是浪费带宽，因为在前后的这个页面中大部分 HTML 往往是相同的。由于每次应用的交互都需要向服务器发送请求，应用的响应时间久依赖于服务器的响应时间。这导致了用户界面的响应比本地应用慢得多。可是异步传输就不一样，异步传输可以像服务器发送并取回自己必需的数据，不要的数据不必也不需要请求，它使用 SOAP 或其他一些基于 XML 的 web service 接口，并在客户端采用 JavaScript 处理来自服务器的响应。因此在服务器和路蓝旗的交换的数据大量减少，我们就能看到响应更快的应用。同时很多的处理工作可以在发出请求的客户端上完成，所以服务器的处理时间就会减少。通过上面的图片，我们就很清楚地看到了异步请求的过程。其实上面的“用户继续执行其他的操作”换成“浏览器继续执行其他的操作”应该更合适一些吧。我们身边有很多这样的异步请求的例子，比如注册用户信息时，用户名不能重复，邮箱不能重复注册，当我们把焦点移开当前输入框时便提示我们用户名和邮箱是否可用，而不是我们以前的那样当提交所有的信息时才提示我们用户名是否可用，这就用到了异步请求 ajax 技术。像上面的图片那样，当我们的焦点移开用户名输入框时，浏览器便通过 js 向服务器请求输入的用户名是否可用，服务器检索数据库检测用户名是否已经存在，然后返回信息，js 再根据返回的信息通过浏览器提示用户用户名是否可用；而用户的操作便是将焦点移动到下一个输入框。所有的操作在我们的页面没有任何的跳转和刷新的情况下就完成了。使用异步请求 ajax 最大的优点，就是能在不更新整个页面的前提下维护数据。这使得 web 应用程序更为迅捷地回应用户动作，并避免了在网络上发送那些没有改变过的信息。同时 ajax 不需要任何浏览器插件，但需要用户的浏览器能够运行 js，因为有的用户可能会有意或无意的关闭浏览器 js 运行，使得某些操作不能进行。使用 ajax 非常的方便，而且现在还有很多的 js 框架封装了 ajax 的使用，就更加的方便了。下面我就使用传统的 javascript 方式和 jQuery 框架两种形式来讲解一下 ajax 的使用。 1. 传统的 javascript 方式： # 创建 HttpRequest； 向服务器发送请求； 服务器响应； 处理服务器返回数据。 1.1 创建 HttpRequest # 由于 IE 的创建方式与其他的浏览器不一样，因此在创建的时候我们应该使用两种方式来创建。function createXMLHttpRequest() { //创建XMLHttpRequest对象 if (window.XMLHttpRequest) { //非IE浏览器 httpRequest = new XMLHttpRequest(); } else if (window.ActiveXObject) { httpRequest = new ActiveXObject("Microsoft.XMLHTTP"); } } 我已经把 httpRequest 变量声明在了所有函数的外面。 1.2 向服务器发送请求 # 可以调用 HTTP 请求类的 open()和 send()方法，具体的调用方式是这样的。url = "card_que_test.php?page=" + page + "&pno=" + pno + "&pname=" + pname + "&identitycard=" + identitycard + "&sex=" + sex + "&ismarried=" + ismarried; httpRequest.open("GET", url, true); httpRequest.onreadystatechange = handle; //指定响应函数 httpRequest.send(null); open()的第一个参数 HTTP 请求方式：GET,POST 或任何服务器所支持的方式。按照 HTTP 规范，该参数要大写；否则某些浏览器（如火狐）可能无法处理请求；第二个参数是请求页面的 URL，即当前页面的请求应该由哪个页面来进行处理，如果需要传递参数时，在 url 后跟上相应的参数；第三个参数为请求是否为异步模式，如果是 true，js 函数将继续执行，而不等待服务器响应。 1.3 服务器响应 # 上面的代码第 4 行有一个 onreadystatechange，该方法是用来指定由哪个函数来处理服务器返回的数据（注意，被指定的函数后面不带括号，只有函数名）；当然，我们也可以直接将处理代码写在 onreadystatechange 后面，handle()具体的实现方式如下：function handle() { if (httpRequest.readyState == 4) { if (httpRequest.status == 200) { var xml = httpRequest.responseText; alert(xml); } } } 看上面的代码，首先要检查请求的状态。只有当一个完整的服务器响应已经收到了，函数才可以处理该响应。httpRequest 提供了 readyState 属性来对服务器响应进行判断。readyState 的取值如下：0（未初始化），1（正在装载），2（装载完毕），3（交互中），4（完成）。只有当 readyState==4 时，一个完整的服务器响应已经收到了，函数才可以处理该响应。 1.4 处理服务器返回数据 # 从服务器返回的数据可以简单的是一个数字、字符或字符串，也可以是某些复杂的数据类型，如 xml,json 等。对于这些我们应当分开来进行处理。下面我们来看一个完整的例子。第一个文件，我们叫 index.html: upfile aa 中国 123 var httpRequest; //创建httpRequest对象 function createHttpRequest() { if (window.XMLHttpRequest) { httpRequest = new XMLHttpRequest(); } else { httpRequest = new ActiveObject("Microsoft.XMLHTTP"); } } //向服务器发送请求 function sendRequest(s) { createHttpRequest(); httpRequest.open("GET", "test.php?s=" + s, true); httpRequest.onreadystatechange = handle; httpRequest.send(null); } //处理数据 function handle() { if (httpRequest.readyState == 4) { var text = httpRequest.responseText; document.getElementById("ss").innerHTML = text; } } 第二个文件，我们叫 test.php: