快速排序

这几天在找工作，今天被问到快速排序，结果想不出来快速排序怎么弄的；回来搜索了一下，现在记录下来，方便以后查看。

注意：快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。（你可以想象一下i和j是两个机器人，数据就是大小不一的石头，先取走i前面的石头留出回旋的空间，然后他们轮流分别挑选比k大和比k小的石头扔给对面，最后在他们中间把取走的那块石头放回去，于是比这块石头大的全扔给了j那一边，小的全扔给了i那一边。只是这次运气好，扔完一次刚好排整齐。）为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。 —— 取自百度百科（链接）

C/C++ 实现：

void quick_sort(int* a, int low, int high){
if (low >= high) {
    return;
}
int first = low;
int last = high;
int key = a[first];
while (first < last) {
    while (first < last && a[last] >= key) {
        --last;
    }
    a[first] = a[last];

    while (first < last && a[first] <= key) {
        ++first;
    }
    a[last] = a[first];
}
a[first] = key;
quick_sort(a, low, first-1);
quick_sort(a, first+1, high);
}

快速排序

原文：http://my.oschina.net/u/146011/blog/335975