快速排序敢叫快速排序，那它一定得快。

快速排序

概述

快速排序也是分治排序的典型，它快，而且是原地排序。不过，要防止在一些特殊情况下的性能退化，并且它是不稳定的。

实现

快速排序先把序列分成两部分，然后对两部分分别排序。伪代码简单到你想哭：

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个排序。

而归并排序或者或者多路堆可以用于非常大的数据集上，甚至数据分布在多台机器上。相当于有一个前端机每次从后端取一个最大值，然后前端机再从这些个最大值里面取最大值。