快速排序——详细且简单易懂的讲解

假设现在要对{3，4，0，2，1，5，9，6，7，8}快速排序：需要在数组里选出一个数作为基准数，为了方便起见，可以选第一个数字5作为准基数

接着，需要把大于准基数的数放在准基数的右边，小于准基数的数放在准基数的左边：

但是，如何做到这点呢，接下来我详细说明：

方法很简单，从这个数组的两边开始进行探测，令i为数组的最左边，j为数组的最右边。
先让j从右出发往走走，找一个小于5的数，再从左出发往右走，找一个大于5的数，然后交换这两个数，直到i与j相遇。

首先让j出发，因为基准数选的是最左边得数，所以应该让右边的j先走，依次向左直到找到小于5的数0，再让i往右走直到找到大于5的数6。

然后交换这两个数：

接着继续走，j走到3，发现3比6小，然后i开始走，一直走到9，发现9比5大：

交换：

然后，j继续向左走，发现3比5小，i开始走，走到3，此时i和j相遇，所以此次探测结束

接着让基准数与3交换，让基准数归位：

到了这一步，已经把比5小的数放在了5的左边，把比5大的数放在了5的右边，但是左右都是乱的，所以接下来，还需要用刚才的方法处理左边和右边。
那么先处理5的左边吧：

同样的方法，选择左边的3作为基准数：


此时探测结束，再依次用同样的方法处理3的左边和右边。
……
……
……
接下来用一张图说明问题：

代码实现：

void QuickSort(int *a, int left, int right)
{
    if (left > right)
        return;

    int base = a[left];
    int i = left;
    int j = right;
    while (i < j)
    {
        while (a[j] >= base && i < j)
            j--;
        while (a[i] <= base && i < j)
            i++;
        if (i < j)
            swap(a[i], a[j]);
    }
    swap(a[left], a[i]);

    QuickSort(a, left, i - 1);
    QuickSort(a, i+1, right);
}

最后

以上就是土豪菠萝为你收集整理的快速排序——详细且简单易懂的讲解的全部内容，希望文章能够帮你解决快速排序——详细且简单易懂的讲解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。