快速排序那点事（上）

淩亂°似流年 2022-05-30 04:38 158阅读 0赞

快速排序很多博客多讲，很多书都写。图解快速排序可以让我们很快了解快速排序的步骤。此文借助图解、通过具体可用代码讲解快速排序，通过解析快速排序算法中需要注意的问题。

纵观目前常用的快速排序的实现方法，可以大致分为两种：互换模式快速排序、传递模式快速排序。

本文主要对**互换模式快速排序**进行讲解。

# 1. 图解算法原理 #

1.设置检察官：互换模式下的快速排序如很多所知的一样，需要设置两个检察官（很多人也称哨兵）。**检察官i和检察官j，检查官i的职责是在职权范围内按序寻找大于标准值的数，在检查官i眼中，大于标准值的数就是超重；检查官j的职责是在职权范围内按序寻找小于标准值的数，在检察官j眼中，小于标准值的数就是掺假。两位检察官的偏好互补，所以可以通过交换实现偏好互补**其中，职权范围就是指检察官在数组中可以移动的范围，而标准值就是我们选定的数，一般选取首位。

如下图所示，在队列首位设置检察官i，在队列尾设置检察官j。同时选取队列首位标准值x=6。  
![这里写图片描述][70]

2.检察官巡逻检查：首先开始移动的是检察官j，移动直到寻找到一个小于标准值的数。当检察官j找出小于标准值的数之后。检察官i出动，向检察官j移动，寻找一个大于标准值的数。

在下图中，检察官j找到了数值5，检察官找到了数值7。达到了双方互换数值的要求。  
![这里写图片描述][70 1]

思考题：
    （1）.为什么首先只能是检察官j先移动？
    （2）.两个检察官移动的范围在哪里？
    （3）.如果某一个检察官没有找到不符合要求的值怎么处理？

3.交换数值：在两位检察官都找到了不符合自己偏好标准的数之后，即可进行数值互换。如下图所示，完成互换后，i和j均得到了自己喜欢的数值。于是又可以返回步骤二进行巡逻检查。  
![这里写图片描述][70 2]

4.重复步骤2和步骤3，进行检察官巡逻检查和数值交换。  
![这里写图片描述][70 3]  
在这一轮巡逻中，i和j也都找到了不满足自己偏好的数值，于是进行交换。  
![这里写图片描述][70 4]  
完成了数值交换之后，结果就是如上图所示。  
于是可以继续开始检察官的巡逻检查。

5.检察官相遇：检察官相遇有两种相遇情形。第一种是i固定，j通过单步移动与i相遇并停在同一位置；第二种是j固定，i通过单步移动与j相遇并停在同一位置。前者情况是j巡逻中未发现过轻的数，以至于直接移动到i所在位置；后者的情况是j已经发现了过轻的数，i未寻找到超重的数，以至于直接移动到j所在的位置。

值得注意的是，无论是i逼近j还是j逼近i，最终i和j相遇的位置的数值都是比标准值小的数。正因为这样的特性，才使得相遇位置数值与标准值交换成为可能。即在i和j相遇之后，交换标准值和相遇位置数值。

![这里写图片描述][70 5]

在上图中，首先是j向左移动到数值3的上方，寻找到了这样一个过轻的小数值，于是停在数值3。此时，i向右移动，遇见j并停在统一位置。这也就是前面所述的第二种的情况，i逼近j的情形。  
![这里写图片描述][70 6]  
在上图中，交换相遇位置的数值与标准值。

通过以上不断的交换之后，得到新的队列。可以看出通过上述系列操作之后，队列分成两个部分：比标准值小的部分、比标准值大的部分。分别对两个部分进行上述交换操作，继续分成两个部分再处理。直到某个部分的数值个数小于2则不需要进行交换排序操作。此处用到了分而治之和递归调用的思想。  
![这里写图片描述][70 7]

思考题：
    （4）.分而治之的思想体现在哪里？
    （5）.递归调用具体使用在哪里？有哪些注意事项？

最后，交换模式的快速排序也可以用过该文章的图解进行了解：[坐在马桶上看算法：快速排序][Link 1]

# 2. C++代码实现算法 #

问题描述：对长度为L的定长数组中的数值进行快速排序  
思想：分而治之、递归实现

/*
    function：对存储在整型队列中的数进行从小到大的排序
    
    param:  int *arr: 存储待排序数列的数组
            int left: 参与排序数首位在队列中的位置
            int right：参与排序数末尾在队列中的位置
    */
    void QuickSort(int *arr, int left, int right)
    {
        if(left >= right)   //如果不满足该条件，说明该部分已经完成排序，可以直接返回
            return;
        int i = left, j = right;
        int x = arr[left];
        while(i < j)
        {
            while(i < j && arr[j] >= x)
                j--;
            while(i < j && arr[i] <= x)
                i++;
            if(i < j)
            {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }
        arr[left] = arr[i];
        arr[i] = x;
        QuickSort(arr,left,i-1);
        QuickSort(arr,i+1,right);
    
    }

为了说明递归调用的条件，明确递归调用停止的情形，写如下的代码。两份代码实现的效果一样。

下面的代码与上面的区别在于：在调用的时候添加条件，当且仅当满足某条件的时候才可以调用。通过这个条件我们可以发现，也就是当需要进行交换排序的数小于等于1个的时候，就不需要再通过交换来排序了。

鼓励使用上面的代码，因为将判断条件设置在函数内部，方便其他用户调用。

void QuickSort(int *arr, int left, int right)
    {
        int i = left, j = right;
        int x = arr[left];
        while(i < j)
        {
            while(i < j && arr[j] >= x)
                j--;
            while(i < j && arr[i] <= x)
                i++;
            if(i < j)
            {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }
        arr[left] = arr[i];
        arr[i] = x;
        if(left<i-1) //添加调用条件
            QuickSort(arr,left,i-1);
        if(right>i+1) //添加调用条件
            QuickSort(arr,i+1,right);
    
    }

> # **3.写在最后** #
> 
> --------------------
> 
> 看完算法思想、看完代码，如果你就觉得对快速排序的细节掌握的不够，对文中出现的思考题还不理解，可以参考[快速排序那点事（中）][Link 2]了解思考题的答案。

[70]: /images/20220530/22e7c4cda787474cb51d647eb6709022.png
[70 1]: /images/20220530/b639089a45f84f9f87179d883a5fa4bc.png
[70 2]: /images/20220530/f71c261276ab4781ab5a067312d048ba.png
[70 3]: /images/20220530/d34a032f4eb34e26895c06c8b3e505dc.png
[70 4]: /images/20220530/f14de674389d43f78063cfb785d240c7.png
[70 5]: /images/20220530/9b41d8c6736b4c2cbaba8a35a8ff2494.png
[70 6]: /images/20220530/c83df5cf1b164eb1aaa1fe2a9f0e29eb.png
[70 7]: /images/20220530/1eaf543d4b624755b4c62b47d0ccd4b6.png
[Link 1]: http://developer.51cto.com/art/201403/430986.htm
[Link 2]: http://blog.csdn.net/loongkingwhat/article/details/79454095