排序算法之冒泡排序与选择排序 之前在ACM机房呆了很长的一段时间，对算法还是了解一些的，只不过现在暂时没有在接触它了，忘记了许多。可是，还有一句话：“瘦死的骆驼比马大”，即使有再长的时间没学习，但基础依然在那儿，看一段时间还是能够很熟练地使用的。前几天做了一个笔试题，最后一题就是排序题，给出7、8个整数让排序，不限排序的算法。于是我就用了冒泡排序，结果到面试的时候，面试官问我为什么不用更高级的排序算法呢，比如快排。好吧，我当时确实是无言以对，我还能说些什么呢，难道我要说：“我会使用快排，就是没写，要不我现在写给你看”。当时我是怎么想的呢，反正他又没限制排序的算法，而且写快排时可能在细节上会出错，关键是排序的数据量还很小，于是就打算用冒泡了。结果就这样悲剧了，有人说了这么一句话，感觉挺在理的，“你用什么样的排序算法，就代表了你什么样的水平；既然你用了冒泡排序，也就代表你的水平是在冒泡的水平”。吸取教训吧，以后要多出个心眼。 忽然想起个事，每次的面试后，都会发现自己学的东西很少很少，要学的东西还有很多，可是就是不知道怎么入手，算法得会吧，js前台技术得会吧，数据库操作得会吧，数据库配置和优化、面向对象的编程、linux下的服务器配置得会吧，而且数据库还不能只精通一种，至少得两种，比如：MySQL, NoSQL, Oracle，等等；得要熟悉模板吧、得要熟悉框架吧、得会二次开发吧，会部署网站的代码吧、得有拿的出手的作品吧，除了PHP还得会点其他的语言吧；好的，到现在，把该学的都已经学过一遍了，总得有项目经验吧；没项目经验？在一个好的学校也是可以找个工作的；如果不是重点学校呢，呃？！这个！ 那天面试可想而知没有很理想，于是打算回来看看数据结构，看看排序算法、树、图。今天就先总结一下冒泡排序吧。我写的简单的排序算法主要解决的有3种要排序的格式：1，以数字为下标的一维数组；2，二维数组，第二维的下标是数字，第一维的下标任意，以第一维数组为单位进行排序；3，二维数组，对值全部进行排序。//我也不知道该用什么语言来写，其实不管什么语言，思想是一样的，只不过对于不同的语言，有着不同的语法规则而已。那我就用PHP写吧。冒泡排序的思想大家应该都是了解的，毕竟接触的第一个排序算法就是冒泡排序了。$arr = array(12, 234, 33, 23, 1, 54, 0); function maopao(&$a){ $t = count($a); for($i=0; $i$low; $i--){ if($a[$i]'liming', 'sex'=>'male', 'score'=>89 ), array( 'name'=>'xiaohong', 'sex'=>'female', 'score'=>91 ), array( 'name'=>'xiaoli', 'sex'=>'male', 'score'=>78 ), array( 'name'=>'keke', 'sex'=>'female', 'score'=>60 ) ) 我们希望按学生的某个特性（比如分数）来进行排序，但是每个学生自己的特性不能乱。我们可以这样写代码。function maopao3(&$a, $key){ $t = count($a); for($i=0; $i'liming', 'sex'=>'male', 'score'=>90), array('name'=>'asd', 'sex'=>'male', 'score'=>89), array('name'=>'bdf', 'sex'=>'female', 'score'=>92), array('name'=>'rgeg', 'sex'=>'male', 'score'=>60) ); //交换两个数 function swap(&$x, &$y){ $temp = $x; $x = $y; $y = $temp; } //选择排序 function xuanze1(&$a){ $t = count($a); for($i=0; $i

排序算法之插入排序 插入排序一般分为直接插入排序和二分插入插入排序。直接插入排序又可以分为前插和后插，不过虽然是这样分，只是寻找地点的方向不一样而已。“前插”就是从头开始找合适的位置，“后插”就是从后面开始找合适的位置。这里我们只讨论“后插”。直接插入排序的思想很简单，开始时，整个数组都是无序的，默认第一个数是排好序的，然后要把第二个数插入到前面，那么就要找到合适的位置插入，从当前数的前一个数$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. 总结 # 为什么会出现这么多的排序算法，因为没有一个算法能在任何情况下都是最优的，两个算法之间的比对总是在一定的数据量级下进行的。还有就是人们希望能够找到一种更快的排序方式。有些人做过测试，在数据量越大的情况下，快排的优势就越明显。