白话解析快速排序

系统管理员 2023-06-14 04:12 5阅读 0赞

快速排序算法简称快排，就是在数组中选择任意一个元素作为**临界值**，然后遍历数组中的元素将**小于临界值**的放到左边，**大于临界值**的放到右边，这样就完成了一次排序，最后通过递归依次将临界值左右部分的元素进行排序即可。

现在我们来思考下如何实现这样一种排序方式，若不考虑空间复杂度，我们最容易想到的一种方式是新建2个临时数组分别存放左右两部分排序的数据，比如临界值为4，我们将小于4的放到一个数组，大于4的放到另一个数组，然后将2个临时数组中的数据复制到原数组中即可，这样当循环往复完成后，数组中的所有元素就变成有序的了。但是这样排序的空间复杂度最大为O(n).

今天我们来说另一种空间复杂度为O(1)的操作，话不多说，我们直接上代码：

public static void quickSort(int arr[],int left,int right){
            if(left>=right)return;
    
            int q=partition(arr,left,right);
    
            quickSort(arr,left,q-1);
            quickSort(arr,q+1,right);
    
        }
    
        private static int partition(int[] arr, int left, int right) {
            int sortIndex=left;
            int arrIndex=left;
            int pivot=arr[right];
    
            while (arrIndex<right){
                if(arr[arrIndex]<pivot){
                    int tmp=arr[arrIndex];
                    arr[arrIndex]=arr[sortIndex];
                    arr[sortIndex]=tmp;
                    sortIndex++;
                }
                arrIndex++;
            }
            arr[right]=arr[sortIndex];
            arr[sortIndex]=pivot;
            return sortIndex;
        }

其中 arr 为待排序的数组，left 和 right 分别为arr 的左边界和右边界（若数组长度为6，则 left 和 right 分别为0和5），当 **left** 大于等于 **right** 时**，**达到终止条件直接返回。

现在我们来看下数组** 6, 2, 3, 5, 1, 4 **的快排执行过程，其中分治就是执行 partition 方法：

**                                          6 2 3 5 1 4                left=0   right=5  
                    第一次分治            2 3 1 4 6 5                left=0   right=5  
                    第一次递归                 2 3 1                    left=0   right=2  
                    第二次分治                 1 3 2                    left=0   right=2  
                    第二次递归                                             left=0   right=0  left>=right，达到终止条件返回  
                    第三次递归                  3 2                      left=1  right=2  
                    第三次分治                  2 3                      left=1  right=2  
                    第四次递归                                             left=1   right=0  left>=right，达到终止条件返回  
                    第五次递归                                             left=2   right=2   left>=right，达到终止条件返回  
                    第六次递归                 6 5                       left=4   right=5  
                    第四次分治                 5 6                       left=4   right=5  left>=right，达到终止条件返回  
                    第七次递归                                             left=4   right=3  left>=right，达到终止条件返回  
                    第八次递归                                             left=5   right=5  left>=right，达到终止条件返回**  
          上面就是快速排序的详细执行过程了，是以数组的最后一个元素作为**临界值**进行快速排序的，可以看出当最后一次分治完成后数组就变成了**1, 2, 3, 4, 5, 6** 有序的了。

现在我们以上述数组的第一次分治为例，分析一下 partition 方法的执行过程：

**                       
                                          sortIndex                                       pivot  
            第一次循环                    6        2        3        5        1        4                  6和4比较, 6大于4, 数据不交换  
                                          arrIndex                               
                                                      
                                  
                                          sortIndex                                       pivot  
            第二次循环                    6        2        3        5        1        4                 2和4比较, 2小于4, 2和6数据交换   
                                                       arrIndex  
                                                      
                                  
                                                      sortIndex                           pivot  
            第三次循环                    2        6        3        5        1        4                 3和4比较, 3小于4, 3和6数据交换  
                                                                 arrIndex         **

**                                                                                          
                                  
                                                                sortIndex                 pivot  
            第四次循环                    2        3        6        5        1        4                 5和4比较, 5大于4, 数据不交换  
                                                                            arrIndex**

**                                                                                          
                                                                sortIndex                pivot  
            第五次循环                    2        3        6        5        1        4                1和4比较, 1小于4, 1和6数据交换  
                                                                                      arrIndex           
                                                       
                                                                                          
                                                                         sortIndex        pivot  
            第六次循环                    2        3        1        5        6        4                 arrIndex=5, right=5,arrIndex<right 不成立循环结束  
                                                                                                arrIndex           
                                                       
                                                                                        **

**                                                                        sortIndex                    
            最后                              2        3        1        4        6        5                      4和5数据交换  
                                                                             pivot     **

上面就是**以4为临界点**由** 6, 2, 3, 5, 1, 4 变成 2, 3, 1, 4, 5, 6** 的详细执行过程，**标红是快排过程中发生的数据交换。**

其中 arrIndex 为数组下标索引，分别遍历数组的前n-1个元素与**临界点4比较，**若小于临界点的，则将 sortIndex 下标的元素和当前元素交换，并将sortIndex +1，否则不做数据交换。从上述执行过程可以看出 sortIndex 就是用来存储小于临界值4的下标索引，每当有一个元素小于4时，sortIndex 所在的元素就会发生数据交换，并加一，这样当遍历完成后只需要将 sortIndex 所在的元素和临界值4进行交换，就能达到在临界点4的左半部分都是小于4的，右半部分都是大于4的效果，这就是快排的核心思想

## 总结： ##

看过我上一篇[归并排序][Link 1]的可以看出来，快速排序和归并排序的代码很相似，但是归并排序是把一个序列拆分成单个元素后再进行排序合并成为一个有序的序列，而快速排序是将整个序列拆分为单个元素时就已经排好序了。而且在上述  partition 方法中可以看出来，它没有申请额外的内存空间，是通过比较交换在原数组中进行排序，空间复杂度为O(1)。 归并排序需要申请额外的内存空间进行排序，空间复杂度为O(n) 。 因为它们的时间复杂度都是 O(log n)，而且快排在内存利用率上比归并排序更高，所以快排比归并排序会应用的更加广泛。

[Link 1]: https://blog.csdn.net/Royal_lr/article/details/102957074