快速排序敢叫快速排序，那它一定得快。
快速排序
概述
快速排序也是分治排序的典型，它快，而且是原地排序。不过，要防止在一些特殊情况下的性能退化，并且它是不稳定的。
实现
快速排序先把序列分成两部分，然后对两部分分别排序。伪代码简单到你想哭：
void qsort(a, from, to) {
if (from >= to) return;
mid = partition(a, from, to);
qsort(a, from, mid -1);
qsort(a, mid+1, to);
}
int partition(a, low, hi) {
temp = a[low];
p = low + 1, q = hi -1;
while( p < q) {
while (a[p] <= temp) p++;
while (a[q] >= temp) q--;
if (p<q) break;
exchage(a, p, q);
}
exchange(a, low, p);
return p;
}
对快速排序的优化主要集中在两点。第一：分治的时候越接近于中间越好；第二：小到一定规模的时候，使用插入排序就可以了。
void qsort(a, from, to) {
if (to - from < threshold) insertionSort(a, from, to);
mid = better_partition(a, from, to);
qsort(a, from, mid -1);
qsort(a, mid +1, to);
}
至于怎么选择切分值才算是好，那就是各有各的搞法了，比如随机选择，比如左右左右选择等等。如果万一每次都没有选择好，只能够切出一个元素，从而退化成插入排序，那只能说是运气实在是太糟糕了。
三向切分的优化
三向切分用来处理中间会有比较多的重复元素时。这时候的切换是要切出一个范围，此范围之内的元素都与切分元素相等。
range range_partition(a, low, hi) {
from = low, len = 1
p = low+1; q = hi -1;
temp = a[low]
while (p < q) {
if (a[p] < temp) {
exchange(a, from, p);
++p;
} else if (a[p] > temp) {
exchange(a, p, q);
--q;
} else ++len;
}
return range(from , len);
}
这段小代码为了腾出中间的范围，所以需要边比较边进行交换，理论上，也可以采取两边逼近的办法，但是那种的话，处理中间元素的办法就没有这么简单了。
优先队列
说到优先队列，第一反应就会想到堆与堆排序。
堆的特点
堆中的每一子树的根节点大于等于它所有的子节点。但是对于左右子树各自的相对大小，是没有进行限制的。通过放宽这个限制，从而容易地得到最大元素（小堆就是最小元素，同理）。堆是堆排序的基础，通过每次取一个元素的方式，就能够完成有序序列的建设。
堆的建立-up
在一个已经建立的堆中，加入一个元素。如果这个元素比它的父元素大，那么就需要进行交换，现在以父元素为根节点的子树已经成堆，但是由于父元素已经被更换了，所以还要看父元素的父元素，一直到根节点。
void up (a, root, i) {
k = parent(a, i)
while ( i != root && less(a, i, k){
exchange(a, i, k);
i = k;
k = parent(i);
}
}
堆的建立-down
把堆的根节点拿掉之后，可以把最后一个元素与根节点进行替换。这时堆被破坏，需要进行修复。通过将根节点与子节点中比较大的一个进行替换，一路向下，就可以修改堆。
void down(a, root, size) {
i = choose_new_root(a, root, size);
if (i == root) return;
exchange(a, root, i);
down(a, i, size);
}
优化方案可以在中间过程中不是交换，而是只修改各子树根元素，最后才填入那个最小元素。
寻找第k个元素
经常碰到的一个问题就是寻找第k个元素，如果k很小，那么优先级队列是可以的，量级就是lgN最级（或者是NlgN，感觉有点吃不定），如果k比较靠近中间，或者占据某个百分比的位置20%，这样的，那么快速排序的划分其实是非常有效的，因为只用找到划分点，而不用将第k个或者前k个排序。
而归并排序或者或者多路堆可以用于非常大的数据集上，甚至数据分布在多台机器上。相当于有一个前端机每次从后端取一个最大值，然后前端机再从这些个最大值里面取最大值。
