【LeetCode力扣】75 快速排序的子过程partition（荷兰国旗问题）

布满荆棘的人生 2024-02-22 08:50 50阅读 0赞

![64feb683565b4900bdc7c277732f38b0.png][]

**目录**

1、题目介绍

2、解题思路

2.1、冒泡排序暴力破解

2.2、快速排序的子过程partition

2.2.1、详细过程描述

2.2.2、代码描述

![2b6c0257a161432cbef52061bbc30046.gif][]

### 1、题目介绍 ###

**原题链接：**[75. 颜色分类 - 力扣（LeetCode）][75. _ - _LeetCode]

![f1219bfdd7df49a790bebbc47c97e7b3.png][]

**示例 1：**

> **输入：nums = \[2,0,2,1,1,0\]** 
> 
> **输出：\[0,0,1,1,2,2\]**

**示例 2：**

> **输入：nums = \[2,0,1\]** 
> 
> **输出：\[0,1,2\]**

**提示：**

*  n == nums.length
 *  1 <= n <= 300
 *  nums\[i\] 为 0、1 或 2

### 2、解题思路 ###

> 根据题目的意思，简单来说就是将数组里的数据按照0、1、2的顺序排列。
> 
> 如果只是要求排序，其实投机取巧的方式很多，比如直接使用冒泡排序也能完成此题。

#### 2.1、冒泡排序暴力破解 ####

void sortColors(int* nums, int sz) {
    	int i = 0;
    	int j = 0;
    	for (i = 0; i < sz - 1; i++)
    	{
    		for (j = 0; j < sz - 1 - i; j++)
    		{
    			if (nums[j] > nums[j + 1])
    			{
    				int tmp = nums[j];
    				nums[j] = nums[j + 1];
    				nums[j + 1] = tmp;
    			}
    		}
    	}
    }

> 冒泡排序：时间复杂度为O(n^2)，空间复杂度为O(1）

#### 2.2、快速排序的子过程partition ####

> 但是根据题目的难度标识为中等，很明显这道题不是在考察冒泡排序的。
> 
> 该题的难点在于如何原地遍历的情况下使得：时间复杂度为O(n)，空间复杂度为O(1)。即仅使用常数空间的一趟扫描算法。
> 
> 而这里就用到了快速排序的子过程partition，partition能够通过一次遍历将所有元素按照标志数进行划分，小于放标志数左边，大于放标志数右边。
> 
> 首先这里有个数组，规定小num的值放在左侧，大于num的值放在右侧，而等于num的值放在中间，下面进行partition过程讲解。

![e07af0e4f42e49daabe28de361afaf4f.png][]

> 首先蓝色方框是小于num的区域，橙色方框是大于num的区域，i从0开始循环遍历。
> 
> 规则：
> 
> 1.  当arr\[ i \]**小于**num时，arr\[ i \]与小于区域的下一个元素交换位置，然后小于区域向右移动一位，i++。
> 2.  当arr\[ i \]**等于**num时，i++。
> 3.  当arr\[ i \]**大于**num时，arr\[ i \]与大于区域的上一个元素交换位置，然后大于区域向左移动一位，**此时i不自增**。

##### **2.2.1、详细过程描述** #####

> 首先arr\[ i \] 等于3，小于5
> 
> 【执行规则1】3与小于区域的下一位元素交换位置，而此时小于区域的下一个元素就是3，因此交换其实已经完成了。然后小于区域向右移动一位，i++。

![43cb806cffdf49d0bbc2d26fc0b3f956.png][]

> 此时arr\[ i \] 等于5
> 
> 【执行规则2】直接 i++。

![39220787718a44eeaa05d2044f4a2faa.png][]

> 此时arr\[ i \] 等于6，大于5
> 
> 【执行规则3】3与大于区域的上一位元素交换位置，于是6和8交换位置。然后大于区域向左移动一位。

![9bc161d049f648d58000edb0dffc34b6.png][]

> 此时arr\[ i \] 等于8，大于5
> 
> 【执行规则3】8与大于区域的上一位元素交换位置，于是8和第二个5交换位置。然后大于区域向左移动一位。

![d9cf8c08187440069f352e0a482388fe.png][]

> 此时arr\[ i \] 等于5
> 
> 【执行规则2】直接 i++。

![721206868cc54c4db690b2f3fb9ea6d8.png][]

> 此时arr\[ i \] 等于7，大于5
> 
> 【执行规则3】7与大于区域的上一位元素交换位置，于是7和第二个3交换位置。然后大于区域向左移动一位。

![e33fe797f5174e7b853e75a5c2009934.png][]

> 此时arr\[ i \] 等于3，小于5
> 
> 【执行规则1】3与小于区域的下一位元素交换位置，于是第一个5和第二个3交换位置。然后小于区域向右移动一位，i++。

![44d4abc8b495404d914fa97382906574.png][]

> 此时arr\[ i \] 等于4，小于5
> 
> 【执行规则1】4与小于区域的下一位元素交换位置，于是第一个5和4交换位置。然后小于区域向右移动一位，i++。

![33a3c21bff914425a8db38ec5bcb6b01.png][]

> 此时i遇到了大于区域了，就停止执行，此时数组中的值就变成了**左边小右边大中间等于。**

##### 2.2.2、代码描述 #####

> 按照快速排序的子过程partition的方法，改造代码 ，使标志数为1，然后将小于1的放左边，大于1的放右边，既完成排序。

void sortColors(int* nums, int numsSize){
        int signal  =  1;  //标志数
        int i = 0;
        int left = -1; //left为下标，是小于区域的右边界，刚开始还未进入数组，因此为-1
        int right = numsSize; //right为下标，是大于区域的左边界，刚开始还未进入数组，因此为numsSize
        while(i<right)   //当i遇上大于区域时停止循环，此时就完成了排序
        {
            if(nums[i] < signal)  //当nums[i]小于标志数
            {
                int tmp = nums[left+1];   //交换小于区域的下一个元素
                nums[left+1] = nums[i];
                nums[i] =  tmp;
                left++;
                i++;
            }
            else if(nums[i] > signal)  //当nums[i]大于标志数
            {
                int tmp = nums[right-1];  //交换大于区域的上一个元素
                nums[right-1] = nums[i];
                nums[i] = tmp;
                right--;
                
            }
            else
            {
                i++;   //等于时直接i++
            }
        }
    }

> 快速排序的子过程partition：时间复杂度为O(n)，空间复杂度为O(1）

![0dfcb194c6bb4b1789d5bc09b578a808.png][]

![0ea6de6a6f0e412083e25c71dd8ce8e6.gif][]

**如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！**

[64feb683565b4900bdc7c277732f38b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/ae76b3da89ea498ebfa804d1b42caebe.png
[2b6c0257a161432cbef52061bbc30046.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/429f93769e8c4fee966dfbcda30bc360.png
[75. _ - _LeetCode]: https://leetcode.cn/problems/sort-colors/description/?envType=list&envId=ixRuNo8f
[f1219bfdd7df49a790bebbc47c97e7b3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/08ec299dcc9b4b538d31b30d587c5886.png
[e07af0e4f42e49daabe28de361afaf4f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/3bdbf89ac01b4988aaae671b9b781bd2.png
[43cb806cffdf49d0bbc2d26fc0b3f956.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/926ba4c301134610b24e40b5d06ad442.png
[39220787718a44eeaa05d2044f4a2faa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/da0b73bfc6d741f59e551400d19c23e3.png
[9bc161d049f648d58000edb0dffc34b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/99bc69e4f16b476b9f0a0ce537fae7e7.png
[d9cf8c08187440069f352e0a482388fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/b426580496a844dabff4ff9c694c2ffc.png
[721206868cc54c4db690b2f3fb9ea6d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/5dcf2f52426c4c2fad4633b203a70db1.png
[e33fe797f5174e7b853e75a5c2009934.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/48f6726f36a64898b9368a2ded7236d3.png
[44d4abc8b495404d914fa97382906574.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/be5bdc58f7114a1e970d4106e5c51d74.png
[33a3c21bff914425a8db38ec5bcb6b01.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/4ddebc73c3c84d32a624cbf491718387.png
[0dfcb194c6bb4b1789d5bc09b578a808.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f17b04d780d54e37a4348cc0d7b4e329.png
[0ea6de6a6f0e412083e25c71dd8ce8e6.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/22/f0d23d4e96dc4795b2e78cf4dfccd613.png