最近在学各种排序算法，刚好写成几篇文记录下来，方便以后查看。 快速排序（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) 的空间，加上创建数组需要一些额外开销。因此这种方法对于大数组而言就不合适了。 关于快速排序的效率： 最好情况下，每次都刚好平均分为两个相同长度的分组，递归循环 log n 次， 键值比较次数为 C(n)=2*C(n/2)+n,C(1)=0 最坏情况下，每次数组都会分成一边长度为0，一边长度为n-1的两个分组，递归循环 n-1 次，键值比较次数为 n+(n-1)+(n-2)+……+1 平均情况下，键值比较次数约等于 1.39nlog n 所以它们的效率分别是： 关于快速排序的优化： 更好的基准元素选择方...