跳至主要内容

算法 | 用Javascript实现快速排序（quicksort）


最近在学各种排序算法，刚好写成几篇文记录下来，方便以后查看。

快速排序（quicksort）的主要思想就是：选择一个基准元素，把小于基准的元素全部移到左边，大于基准的元素移到右边。然后对左边和右边的元素分别再进行排序，如此循环到每个小分组只剩下一个元素为止。

对元素的划分有两种算法。一个是Lomuto算法。

把第一个元素作为基准元素。从第二个开始遍历余下的元素，a[i]>=p则继续往前走，当遇到一个小于p的元素时，就停下来，将s增加1，再交换a[s]，a[i]的元素。这样就保证比p小的元素永远在左边，比p大的元素永远再右边。
循环结束后，再交换a[s]和a[left]的值。使基准元素成为分界点。

另一个算法是Hoare算法。Hoare就是提出快速排序思想的人，图灵奖得主。
变量i跟踪小于基准的元素，从左到右遍历，遇到大于等于基准的元素就停下来。j跟踪大于基准的元素，从右到左遍历，遇到小于基准的元素就停下来，然后交换a[i]和a[j]。直到i，j相遇。再把基准元素和a[j]交换。比较麻烦的就是每次都要判断i是否溢出。

两个划分算法效率是一样的，个人认为Lomuto算法比较容易理解。
有了划分算法之后，要写快速排序就容易多了。
下面是用js写的原地排序（in-place）：
还有另一种比较有js特色的快速排序实现，代码如下：
第二种快速排序实现有一个很大的缺点，就是很耗内存，对一个有n个元素的数组进行排序，每一次递归都要新建两个数组来存放两边的元素，最好情况下递归循环log n次，每次需要n个元素的空间，因此需要额外n(log n)的空间，加上创建数组需要一些额外开销。因此这种方法对于大数组而言就不合适了。

关于快速排序的效率：
  1. 最好情况下，每次都刚好平均分为两个相同长度的分组，递归循环 log n 次， 键值比较次数为C(n)=2*C(n/2)+n,C(1)=0
  2. 最坏情况下，每次数组都会分成一边长度为0，一边长度为n-1的两个分组，递归循环  n-1次，键值比较次数为 n+(n-1)+(n-2)+……+1
  3. 平均情况下，键值比较次数约等于 1.39nlog n

    所以它们的效率分别是：


关于快速排序的优化：
  1. 更好的基准元素选择方法。比较有名的是三平均划分法（median-of-three method），以数组最左边，最右边，以及最中间元素的中位数作为基准元素。上文提过平均情况下快速选择的效率大约是1.39nlog n，根据维基百科，使用三平均划分法能使效率达到1.188nlog n 左右。
  2. 当数组足够小的时候（5-15），改用插入排序方法。或者在快速排序递归至每个分组都足够小的时候，停止递归，然后对整个近乎有序的数组实行插入排序。
  3. 先递归比较小的分组，然后对大的另一个分组使用尾递归，减少堆栈。


题外话：关于我对js特色的快速排序实现的改进历程：
第一次看到这个代码，我就觉得其实没必要对数组进行切片，所以我把切片去掉了，变成这样：
然后问题来了，我用var a=[2,5,3,9,8,0,7,1,4]去测试这段代码，浏览器就报错了！
然后我就在每个循环后面加了一个console.log(a)，发现第一次循环结果还是正常的，a被切成了 [2,5,3,0,7,1,4] [9,8]。
但是从第二次就开始了[2,5,3,0,7,1,4]的死循环。研究了以下，发现此时 a[Math.floor(a.length/2)]刚好是0，所以切片时right数组还是[2,5,3,0,7,1,4]，所以就形成了死循环。
也就是说，当我们选中的基准元素刚好是这个数组中的最大或者最小元素时，就会发生死循环。
想要避免死循环，就要跳过基准元素，为了避免频繁的比较下标，把基准元素设置为数组的第一个元素（但是如果数组本身已经排序好，选择第一个元素作为基准元素会让效率变得很低）：
再用var a=[2,5,3,9,8,0,7,1,4]去测试，运行成功。（当然，这次改进只能提高代码的可读性= =）
还有一个同学提出另一种改进思路：出了left和right外，再增加一个equal数组，存放和基准元素相等的元素，这样也不用切片，也不会发生死循环。不过我目前觉得，这个改进方法好像也没有什么实际意义……

标签：

评论

发表评论

此博客中的热门博文

算法 | 堆排序（heap sort)

    注：本文只讨论最大堆排序，最小堆排序同理 一 . 堆   堆（heap）可以定义为一棵 完全 二叉树，并且这棵树的每一个节点都大于或等于它的子女节点。  最大堆长这样子： 堆的特性 一棵n节点的 完全 二叉树，其高度为$$\lfloor \log_{2}n\rfloor$$ 堆的每一个节点都大于等于它的子女节点。 可以用数组来实现堆。留空H[0]，然后在H[1]到H[n]中存在堆元素。留空H[0]的目的是为了让之后的堆排序更加的方便。 所有父母节点的键会在数组的前$$\lfloor n/2 \rfloor$$ 个位置中，而叶子节点会占据后面的$$\lceil n/2 \rceil$$个位置。 在数组中，对于每一个位于父母位置i的键来说，它的子女会位于2i和2i+1 对于一个位于位置i的键来说它的父母将会位于$$\lfloor i/2 \rfloor$$ 如何生成堆 自底向上堆构造（bottom-up heap construction）： 对每个父母节点进行父母优势检查： 从最后的父母节点开始，到根为止，检查这些节点的键是否满足父母优势要求。 如果该节点不满足，就把该节点的键K与它子女的最大键进行交换。 然后再检查新位置上，K是不是满足父母的优势要求。 效率： 最坏情况下，每个位于树第i层的节点都要移动到树的最底层h，因为移动一层需要两次键值比较，因此移动到h层需要 2(h-i) 次键值比较，所以总键值比较次数为： 自顶向下堆构造（top-down heap construction）： 把新的键连续插入到已经预先构造好的堆： 把包含k附加到堆的最后一个叶节点的后面。 拿k与它的父母节点作比较，如果k刚好小于它的父母节点，则算法停止。 否则，交换k和其父母节点的位置 重复2，3步骤直到k不大于它的父母，或者到达了根为止。 效率： 因为包含n个节点的树的高度大约是 log n ,因此每次插入的时间效率属于 O(log n) 总时间效率叠加即可。 二. 堆排序 堆排序的思路很简单： 把数组构造成堆，此时根是最大值。 把根从堆中“移除”，即把...
发表评论
阅读全文

Javascript | 从swap函数思考js中的参数传递

事情是这样的，有一天，林逍遥同学在学js的时候，想要用js写一个swap函数，她是这么写的： 但是结果输出来之后，她发现事情并没有这么简单：a还是等于1，b还是等于2. 她赶紧翻了一下《Javascript高级程序设计》，发现里面有一段话： ECMAScript中所有函数的参数都是按值传递的。  传递基本类型的值时，被传递是值会被复制给一个局部变量（即命名参数）。 传递引用类型的值时，会把这个值在内存中的地址复制给一个局部变量，因此这个局部变量的变化会反应在函数的外部。  原来如此，已知a，b是两个基本类型的变量，当把a，b传入swap函数的时候，会生成两个新的局部变量，分别存储a，b的值，也相当于它们的副本，虽然值跟a，b是一样的，但在内存中的地址却是不同的，所以在swap函数里面做的改变并不会影响a，b的值，也就谈不上交换了。 综上所述，不可能写一个swap函数来交换两个基本类型的值。 不过对于引用类型的值（数组，对象），却是可以通过函数改变它们的值的。 当把person复制给xy时，同样也会把存储在person中的值复制一份给xy，不过，person存储的值并不是一个对象，而是这个对象的地址（也就是指针），因此复制的其实是地址值。复制操作结束后，person和xy将指向内存中的同一个地址。 所以在xy上做的改变。也会反映到person上面。 同样地，在传递参数的时候，相当于临时创建了一个局部变量，把person的地址也复制给了这个局部变量，因此在函数内部做的改变会反应到person上。 但是，在函数中对参数赋新值，不会影响到函数外部。 给参数赋值一个新的对象，相当于把参数指向另一块地址，所以不会对person产生影响。 总结：js中参数的传递都是按值传递，不过基本类型变量传递的是变量值，引用类型变量传递的是地址。 题外话：如何用一句话代码交换a，b的值？ b={x:a,y:(a=b)}.x; js文化真是博大精深哪！
发表评论
阅读全文

算法 | 归并排序（merge sort）(Javascript实现)

算法第二弹，归并排序（merge sort）。语言：Javascript。 核心思想： 归并排序的思路还是比较简单的，话不多说，看图： divide阶段：每次把数组一分为二，循环直到每个分组只有一个元素为止。 merge阶段：每次比较两个待合并数组的第一个元素，将较小的元素添加到一个新创建的数组中。接着，被复制数组中的指针后移。再比较两个数组各自的第一个元素……循环直到两个数组中的一个被处理完为止。然后，把未处理完的数组剩下的元素复制到新数组的尾部。看不懂请移步下面的动图。 （下图来自维基百科） 代码 既然已经懂了归并排序的原理。那就可以开始敲代码了。 如果简单粗暴地把归并排序的思想转化为代码，那结果是这样的： 不过理想很丰满，现实很骨感。这种实现方法虽然做到了时间上的高效，但是空间上付出的代价时惨重的。想象一下，假设数组有 n 个元素，那么算法就要递归 log n 次，因为数组的元素个数是不会减少的，也就是每次要额外的 n 个空间来暂时存储划分好的元素。如果你计算的是一个比较大的数组，而你的计算机刚好又是那种内存比较小的……嗯，画面太美我不敢看。 一个好的解决方法是建立一个临时数组，每次递归时，交替使用临时数组和原数组来进行切片，合并，以达到节省空间的目的。（此时空间复杂度为 n）。 可以从两个方向来进行递归。 一个是自顶向下的归并排序（Top-Down)，代码如下。 代码可能有点难理解，看不懂的同学请拿出一张纸，创造一个数组，按着代码步骤一步一步将数组排序。实践出真理。 另一个是自底向上的归并排序（Bottom-Up），代码如下。 效率 空间复杂度 前面已经讲过，所以这里不再赘述。 时间复杂度 计算归并排序的键值比较次数，每做一步，都要进行一次比较，比较之后，两个数组中尚未处理的元素个数减 1 。 最坏情况下，无论哪个数组都不会为空，除非另外一个数组只剩下最后一个元素（也就是连个数组中的元素是按序交错存在的）。当每个数组有 k/2 个元素时，比较的次数为 k-1 （只有最后一个元素不用比较）。所以递归式为 最好情况下，其中一个数组的所有元素都小于另一个数组的最小元素，当每个数组有 k/2 个元素时，键值比较次数为 k/2 ，因此递归式为 ...
发表评论
阅读全文