排序算法之快速排序（详细推导）

短命女 2023-02-17 11:08 28阅读 0赞

今天介绍另一种大名鼎鼎的排序算法——快速排序。见名知意，这个算法排序速度一定相当快。接下来逐步分析分析。

**首先了解快速排序的基本思路：  
1.选的中间轴Pivot  
2.将大于Pivot的数据放在Pivot右边  
3.将小于Pivot的数据放在Pivot左边  
4.分别对左右子序列重复上述三步操作  
具体过程就是：定义两个指针，left,right.分别指向数组的头和尾，一般而言，我们选择头也就是arr\[0\]作为我们选定的中间轴Pivot。然后从right开始遍历直到找到小于Pivot的元素，将这个元素的值赋给left指向的元素及arr\[left\] = arr\[right\]。接着开始遍历left指针，直到找到大于Pivot的元素，然后将arr\[right\] = arr\[left\],最终left,right会指向同一个元素，这个元素就是中间轴Pivot的插入位置。**

听起来是不是很简单？惯例，还是给出详细推导步骤，如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
然后开始遍历left指针,如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]  
(每次遍历都会找到小于（right移动）或者大于(left移动)Pivot的元素，不然就会一直遍历直到left >= right，如上图left遍历到a\[1\]发现大于Pivot所以需要进行赋值arr\[right\] == arr\[left\],接下来类似过程不再讲述)

然后重复上述的步骤，left,right交替遍历。直到left,right指向同一个元素。接下来给出变换的过程，但不一一概述了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 4]  
第一轮完成结果如下：  
![第一次排序的结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 5]  
经过第一轮的顺序执行后不难发现，此时Pivot的左边都是小于Pivot的元素，右边都是大于Pivot的元素。至此，初步的完成了从小到大的排序任务。接下来就是对左、右子序列进行上述的重复操作（这里可以用递归实现，这里的递归左右就是持续往下执行，不存来回溯，这个过程不难体会）。

最后给出完整的代码及分析：

private static void quickSort(int[] arr,int left,int right){
        
            //递归结束
            if (left >= right){
        
                return;
            }
    
            //定义中心轴
            int pivot = arr[left];
            int l = left;//左指针
            int r = right;//右指针
            while (l < r) {
        
                //因为是从右先开始判断所以下面while必须放在前面
                while (l < r && arr[r] >= pivot){
        //这里的l < r不能省略
                    r --;
                }
                //这里循环结束表示找到了大于pivot的元素，接下来进行赋值
                if (l < r){
        //这里是做了优化，如果左右指针不相等则进行赋值，如果相等就找到pivot的位置,不用进行赋值
                    //此处的if需要体会,下面的if作用相同
                    arr[l] = arr[r];
                }
                while (l < r && arr[l] <= pivot){
        
                    l ++;
                }
                if (l < r){
        
                    arr[r] = arr[l];
                }
            }
            //这里循环结束表示找到了pivot的位置
            arr[l] = pivot;
            //此时中间元素确定了，且左边全小于该元素，右边都大于该元素
            //接下来继续对左右两边确定pivot
            quickSort(arr,left,l - 1);
            quickSort(arr,l + 1 ,right);
        }

总结：  
快速排序是冒泡排序的一种改进，执行效率就像它的名字一样。采用递归，利用空间的开销获取执行的速度，往往Pivot的选择好坏也决定着排序的效率。  
代码方面可以看到，代码不算难，但是许多细节出都需要体会。比如那个if为什么要添加，其实不添加也可以执行。但是添加了相当于做了优化。笔者整个代码也体会了很久，debug了运行了多次。可能我的想法有些片面或者错误，还望提出指教。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200613140235333.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200613140339686.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200613140522766.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20200613144416936.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20200613144614333.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20200613141708780.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center