浅谈快速排序

小鱼儿 2022-08-22 06:27 152阅读 0赞

今天早上花了大约两个小时时间研究了下快排的思想（请别嘲笑我可怜的智商），终于把其中的奥妙搞得比较清楚了。为了防止忘掉，特地写这篇文章来加深印象。
    总的来说，快排是运用了分治和递归的思想：先找一个基准点，然后把数组中比这个基准大的数放到一边，把比它小的数放到另一边。比如找基准9，那么把比9小的数放在9的左边，把比9大的数放在9的右边。然后调用递归使9左边和9右边的数字们也同样的分别排序，最后一定可以从小到大的排好序的。
    所以问题的关键是如何将数字按大小放到这个找到的基准点的两侧呢？这里介绍两种方法（大同小异）：

方法一：  
我们先取第一个为基准  
先用两个变量l，r分别从头到尾和从尾到头的遍历数组。先让r从尾到头来找，找到一个比基准小的数就停下来，这时候l从头到尾开始寻找比基准大的数，一旦找到交换r和l所在的数。然后两者继续往中间靠，直到两者相遇。相遇之后把相遇的那个点的数给第一个数（注意：这个时候相遇处的数一定比基准数小，这是由我们先从尾到头查找决定的），基准的数给相遇处的数。

void quicksort(int *num, int first, int last)
    {
        if (first > last)//必须加上，不然会无限递归调用
            return;
        int l = first,r = last;
        int temp = num[first];
        while (l != r)
        {
            while (r > l&&num[r] >= temp)
                --r;
            while (l < r&&num[l] <= temp)
                ++l;
            if (l < r)
            {
                int t;
                t = num[l];
                num[l] = num[r];
                num[r] = t;
            }
            //l += 1;
        }
        num[first] = num[l];
        num[l] = temp;
        quicksort(num, first, l - 1);
        quicksort(num, l + 1, last);
    }

续：觉得之前写的还有些地方没有讲清楚，所以重新修改了一下。  
关于循环什么时候停止：最后r肯定是在数组中比基准数小的所有书中的最后一个那儿停下（这时候r和它左边的数都比基准数小或相等，r右边的数都比基准数大），那么l这时候开始往右走，走到r的位置，但是这个位置的数还是没有基准数大，不过这时候由于被条件l

void quicksort(int *num, int left, int right)
    {
        if (left > right)
            return;
        int temp = num[left];
        int l = left, r = right;
        while (r != l)
        {
            while (num[r] >= temp&&r > l)
                --r;
            num[l] = num[r];
            while (num[l] <= temp&&r > l)
                ++l;
            num[r] = num[l];
        }
        num[l] = temp;
        quicksort(num, left, l - 1);
        quicksort(num, l + 1, right);

以上都是从小到大排的，改改符号就能从大到小排了。：）