LeetCode-75. 颜色分类

超、凢脫俗 2024-03-23 13:38 71阅读 0赞

#### 目录 ####

*   *  题目思路
     *  代码实现

题目来源  
[75. 颜色分类][75.]

### 题目思路 ###

快速排序原理：  
快速排序算法有两个核心点，分别为 “哨兵划分” 和 “递归” 。  
**哨兵划分操作：** 以数组某个元素（一般选取首元素）为 基准数 ，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。  
![在这里插入图片描述][6f36e2ab5d404ad6ae318333948a76ca.png]  
递归： 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

为示例数组 \[2,4,1,0,3,5\] 的快速排序流程。观察发现，快速排序和 二分法 的原理类似，都是以 logn 时间复杂度实现搜索区间缩小。  
![在这里插入图片描述][2eb6149619ed487fba29a3f9f6cb31fd.png]  
时间复杂度：基于随机选取主元的快速排序时间复杂度为期望 O(nlogn)，其中 n 为数组的长度。

### 代码实现 ###

class Solution {
        
        public void sortColors(int[] nums) {
        
            quickSort(nums,0,nums.length-1);
        }
        public void quickSort(int[] nums,int L, int R){
        
            if(L >= R){
        
                return;
            }
            int left = L;
            int right = R;
            int pivot = L;
            while(left < right){
        
                while(left < right && nums[right] >= nums[pivot]) right--;
                while(left < right && nums[left] <= nums[pivot]) left++;
                swap(nums,left,right);
            }
            swap(nums,pivot,left);
            quickSort(nums,L,left-1);
            quickSort(nums,left+1,R);
    
        }
        public void swap(int[] arr,int i,int j){
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

![在这里插入图片描述][a1605514afd74ecfbe0009bfccdfc51d.png]

[75.]: https://leetcode.cn/problems/sort-colors/
[6f36e2ab5d404ad6ae318333948a76ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/3b1fd120e6b14b888de6522589034bd4.png
[2eb6149619ed487fba29a3f9f6cb31fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/f19343a9caf049318e31535943ebd76e.png
[a1605514afd74ecfbe0009bfccdfc51d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/2dcbc0a7982d45dba0adce60a501d1d8.png