手写QuickSort算法

快速排序(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);
}

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