快速排序之javascript实现
算法原理
快速排序是目前各种排序算法中较为高效的一种算法,它的基本思想是分治法:
分治法(Divide and Conquer Algorithm):把原问题分为若干个与原问题结构类似的子问题,然后对子问题进行递归求解,最后把这些子问题的解集全部合并起来就是原问题的解。
算法具体实现有三个步骤:
1. 从数组中选出一个元素,我们称之为 “基准”(pivot);
2. 先进行一次循环比较,把所有比基准小的数放左边,把所有比基准大的数放右边(相等的值随便哪边放都行),这个操作称为分区 (partition) 操作。当分区完成后,我们就得到了两个子分区, 其中一个分区的所有元素的值都比另外一个分区大。
3. 分别对步骤二分出来的两个子集进行递归排序,直到最后子集只剩一个元素为止。
图片来自维基百科
阅读全文