前言
这两天看到阮一峰前辈的快排引起的一系列事件...(居然DDOS都出来了)，前端界又被顺路diss了一番，想起来了以前在有道云中记得笔记，顺便在这里再记录下。
快速排序
快速排序采用了一种分治的策略，通常称其为分治法，其基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序的具体过程如下：
- 在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录分成两组，第1组各记录的排序码都小于等于该排序码，第2组各记录的排序码都大于该排序码，并把该记录排在这两组中间。
- 采用同样的方法，对左边的组和右边的组进行排序，直到所有记录都排到相应的位置为止。
算法复杂度
最好的情况下：因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)，故为 O(NlogN)
最坏的情况下：基本有序时，退化为冒泡排序，几乎要比较NN次，故为O(N*N)
稳定性
由于每次都需要和中轴元素交换，因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说，快速排序是不稳定的！
一种比较容易理解的方式
这个例子是原地快排，阮老师文章中为非原地快排。
假设我们现在对[3,2,6,7,0,9,1,4,5,8]这个10个数进行排序。
- 找一个数作为基准数（就是一个用来参照的数）。
为了方便，就让第一个数3作为基准数。接下来，需要将这个序列中所有比基准数大的数放在3的右边，比基准数小的数放在3的左边。
方法其实很简单：分别从数组两端开始“探测”。先从右往左找一个小于3的数，再从左往右找一个大于3的数，然后交换他们。
这里可以用两个变量i和j，分别指向序列最左边和最右边。刚开始的时候让i指向序列的最左边（即i=0），指向数字3。j指向序列的最右边（即=9），指向数字8。
首先j开始移动j--，直到找到一个小于3的数停下来。因为此处设置的基准数是最左边的数，所以需要让j先出动，这一点非常重要。接下来i++，直到找到一个数大于3的数停下来。最后j指向1，i指向6。
第一次探测
现在交换i j所指的元素的值。交换之后的序列如下：
交换
到此，第一次交换结束。接下来开始j继续向左挪动。移动到0时，比基准数3要小，满足要求，停止移动。i继续向右挪动的，到7之后停了下来。此时再次进行交换，交换之后的序列如下：
第二次交换
第二次交换结束，继续j先开始移动，但是此时i 和 j重合，i和j都到了0面前。说明此轮“探测”结束。我们将基准数3和0进行交换。交换之后的序列如下：
第一轮结束
到此第一轮“探测”真正结束。此时以基准数3为分界点，3左边的数都小于等于3，3右边的数都大于等于3。回顾一下刚才的过程，j的使命就是要找小于基准数的数，i的使命就是要找大于基准数的数，直到i和j重合。
现在基准数3已经归位，它正好处在序列的第3位(从0计数)。此时我们已经将原来的序列，以3为分界点拆分成了两个序列，左边的序列是0 2 1，右边的序列是7 9 6 4 5 8。接下来以同样的方法处理这两个序列即可。
function quickSort(list, low, high) {
if (low > high)
return;
var l = low, h = high;
var mark = list[low];
while (l !== h) {
while (list[h] >= mark && l < h)
h--;
while (list[l] <= mark && l < h)
l++;
if (l < h) {
var temp = list[h];
list[h] = list[l];
list[l] = temp;
}
}
list[low] = list[l];
list[l] = mark;
quickSort(list, low, l - 1);
quickSort(list, l + 1, high);
}
必须从右侧开始的原因是
例如上例子右侧的序列7 9 6 4 5 8
当我们先从左边开始时，第一次交换完的序列是
7 5 6 4 9 8
此时i指向5 j指向9
继续，i先移动，找到第一个大于7的元素9，i即与j重合，此时按理论来说，本轮探测已结束，所以要交换基准数和ij重合的数，序列即变成了
9 5 6 4 7 8
我们原本 交换后数字7左边应该是全部小于7，右边全部大于7.但现在不行了。
于是，我们必须从右边开始，也就是从基数的对面开始。
网友评论