快速排序partition写法（一道力扣题目引出的Lomuto和Hoare的partition方法区别）

浅浅的花香味﹌ 2023-03-04 09:30 4阅读 0赞

做力扣的一道题目：

169 多数元素

的时候，用到了快速排序，所以复习了一下快排。

### 一、快排 ###

快排思想就是：

1.  选定一个哨兵元素pivot；
2.  把小于pivot的元素放在pivot左边，大于pivot的放在右边，这样，划分完后pivot就在自己**最终应该在的位置**了；
3.  对于pivot位置的左边和右边，递归进行 1、2 的过程。

其中，quickSort就是主方法，是分支递归的过程，2的步骤就是核心的partition方法，他进行划分，使得每一轮用 O(n) 的时间确定了一个元素的位置。

因此快速排序的渐近时间复杂度是 O（nlogn）。

快排代码：

public void quickSort(int[] nums){
        
            sort(nums, 0, nums.length-1);
        }
    	//递归
        public void sort(int[] nums, int i, int j){
        
            if( i >= j )return;//递归结束条件
            int p = partition(nums, i, j);
            sort(nums, i, p-1);
            sort(nums, p+1, j);
        }
    	//划分
        public int partition(int[] nums, int i, int j){
        
            //选最左边为哨兵
            int pivot = nums[i];
            while( i < j ){
        
                while( i < j && nums[j] >= pivot ){
        
                    j--;//从右往左找到第一个<pivot的
                }
                nums[i] = nums[j];
                while( i < j && nums[i] <= pivot ){
        
                    i++;//从左往右找到第一个>pivot的
                }
                nums[j] = nums[i];
            }
            nums[i] = pivot;//最后把pivot放到对应位置
            return i;
        }

### 二、题目 ###

这个题目是这样的：

给定一个大小为 n 的数组，找到其中的多数元素。**多数元素**是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

> **示例 1:**  
> 输入: \[3,2,3\]  
> 输出: 3  
> **示例 2:**  
> 输入: \[2,2,1,1,1,2,2\]  
> 输出: 2

这道题目的做法可以是用哈希，用摩尔投票算法，也可以排序。

排序的原因是，多数元素出现次数大于了 ⌊ n/2 ⌋ ，所以序过后，**处于 nums.length/2 位置的元素就是答案。**

并且不用全部排序，每次 partition 的结果是对应的位置，我们只要**判断这个位置和要的 ⌊ nums.length/2 ⌋ 的关系**，然后决定向哪一半继续调用sort就可以了。

代码就是这样：

class Solution {
        
        public int majorityElement(int[] nums) {
        
            int target = nums.length/2;
            int ans = sort( nums, 0, nums.length-1, target );
            return nums[ans];
        }
        //递归排序过程，但是逐渐缩小范围部分进行
        public int sort( int[] nums, int i, int j, int k){
        
            int pos = partition( nums, i, j );
            if( pos==k )return pos;
            if( pos>k )return sort( nums, i, pos-1, k );
            else return sort( nums, pos+1, j, k );
        }
    
        //划分过程
        public int partition( int[] nums, int i, int j ){
        
    		//。。。
        }
    }

可是 **运行速度非常慢**，但是看到题解中也有用一样的思路来做的，只是快排部分的partition代码不同，时间快了几乎 50 倍。

那个 partition 代码是这样写的：

public int partition( int[] nums, int i, int j ){
        
            int pivot = nums[i];
            int left = i;
            int right = j+1;
            while( true ){
        
                while( ++left<=j && nums[left]<pivot);
                while( --right>=i && nums[right]>pivot );
                if( left>=right )break;
                int t = nums[right];
                nums[right] = nums[left];
                nums[left] = t;
            }
            nums[i] = nums[right];
            nums[right] = pivot;
            return right;
        }

看起来逻辑上没有相差什么，只是交换的顺序不同，另外加了后处理。

于是分析原因：

*  本地生成随机数，对100-10000000数量级的数组，分别采用两种快速排序代码进行了测试，结果是：采用这两种partition代码运行的时间都是同一个数量级，相差不大。
 *  然后控制变量，改了自增自减的前后缀位置，改了提前 break 的语句，结果仍然是差别不大。
 *  最后，为了贴合这个题目，把输入修改，一半为随机数，一半为固定值，也就是 **有众数的情况**，再测试，区别非常明显的出现了。

结合代码，定位到两种partition方案的区别在于对于每一个 pivot 的划分处理：

方法 1

while( i < j && nums[j] >= pivot ){
        
                    j--;
                }

方法 2

while( ++left<=j && nums[left]<pivot);

然后我搜了一下，才想起来，《算法导论》里曾经出现过这个问题，那就是Lomuto和Hoare的partition方法的不同。

第一种就是我采用的常规方法 1 ，第二种则是现在大多使用的，比较推荐的Hoare的partition方法。第一种实际上只用了一次的单向扫描，并且跳过了重复元素，这样会导致重复元素很多的时候，划分非常不平衡，而这道题目恰恰是重复元素很多的。

第二种做法采用的是双指针，并且不跳过重复元素，按照不严格的逆序对进行交换，可能会多交换几次元素，但是整体来看，重复元素很多的时候，他能划分的更加均匀，这样分治之后反倒更加节省时间。

比如：

[5 6 7 5 5 5 7 5 5]

那第一种直接 right 就会跑到和 left 相等，左边划分为空，右边是划分为原数组去掉一个5；

[5 | 6 7 5 5 5 7 5 5]