手写 QuickSort 算法

快速排序(QuickSort)，是一种比较经典的排序算法，在很多基础库中都有实现。

今天给大家介绍一下原理，并且咱们自己动手实现一把。

QuickSort 的原理如下：

我们先从数组中取一个基准元素，然后通过多次比较和元素交换，最终找到一个位置，使得左侧元素都比这个基准元素小，右侧元素都比这个基准元素大。然后把基准元素放到这个位置上，这个位置，就是这个基准元素在最终排好序的数组中的位置，因此它就不需要变动了。然后，我们左侧和右侧分别变成一个数组，应用上面的方法，对其进行排序。最终，每个元素都找到并被放置到相应的位置。当被排序的数组元素长度为 0 时，排序结束。

基准元素的选取，可以取最左边，可以取最右边，当然也可以取随机数。通常我们取最左边的那个数。

下面用一个整数数组，来展示一下 QuickSort 排序的实现过程：

1）我们取最左侧的元素为基准元素，把元素的值记录到 base 中。被排序数组元素的最小下标为 low, 最大下标为 high，用两个不同颜色的箭头表示。

2）在区间[low..high]，从 high 向 low 的方向，查找比 base 小的元素，发现第一个即停止。查找过程会移动 high，最终 high 会停在比 base 小的元素位置上。

3）将 high 位置的元素，赋值给 low 位置的元素。这步的目的，是将比 base 小的元素，都放到左边。

4）在区间[low..high]，从 low 向 high 的方向，查找比 base 大的元素，发现第一个即停止。查找过程会移动 low，最终 low 会停在比 base 小的元素位置上。

5）将 low 位置的元素，赋值给 high 位置的元素。这步的目的，是将比 base 大的元素，都放到右边。

6）循环执行步骤 2)~5），直至 low 和 high 相等。

7. 将 low 位置的元素值，改为 base。这个位置，就是基准元素的最终位置。

8. low 位置左右两边，各形成一个数组。对这个两个数组，再次应用上述从 1）到 7）的排序算法，这样整个数组就排好序了。

上述原理，C 语言代码实现，如下：

void quick_sort(int* parr, int left, int right) {    if (left >= right) {        return;    }
    int low = left;    int high = right;    int base = parr[low];
    while (low < high) {        while ((low < high) && (parr[high] >= base)) {            high--;        }        parr[low] = parr[high];

        while ((low < high) && (parr[low] < base)) {            low++;        }        parr[high] = parr[low];    }
    parr[low] = base;    quick_sort(parr, left, low-1);    quick_sort(parr, low+1, right);}

我的微信号是 实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。