笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

【LeetCode力扣】75.颜色分类———快速排序子过程（荷兰国旗问题）

作者：笔触狂放9 | 2024-05-05 20:01:42

踩

1、题目介绍

原题链接：75. 颜色分类 - 力扣（LeetCode）

示例 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 numsSize){
    int i = 0;
    int j = 0;
    int size = numsSize;
    for(i = 0; i < size-1; i++){
        for(j = 0; j < size-i-1; j++){
            if(nums[j] > nums[j+1]){
                int tem = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tem;
            }
        }
    }
}

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

2、2、快速排序的子过程

荷兰国旗解题思想

在数组两边个准备一个区域，一个小于1区域放在数组左边，一个大于1区域放在数组右边，通过对数组里的数字与1进行比较，如果小于1就将其放在小于区域，如果等于1则不动，比较下一个数字，如果大于则将其放在大于区域。

{小于1的区域} [要进行操作的数组] {大于1的区域}

详细过程图：

红色圈圈是小于1的区域，蓝色圈圈是大于1的区域，然后从i=0，arr[i]开始遍历

遍历的规则是：

当arr[ i ]小于1时，arr[ i ]与小于区域的下一个元素交换位置，然后小于区域向右移动一位，i++。
当arr[ i ]等于1时，i++。
当arr[ i ]大于1时，arr[ i ]与大于区域的上一个元素交换位置，然后大于区域向左移动一位，此时i不自增。

这时候arr[i]等于1

【执行规则2】直接i++

这时候arr[i]等于0，小于1

【执行规则1】0与小于区域的下一位元素交换位置，于是第一个1和第一个0交换位置。然后小于区域向右移动一位，i++

这时候arr[i]等于1

【执行规则2】直接i++

这时候arr[i]等于2，大于0

【执行规则3】0与大于区域的上一位元素交换位置，于是第一个2和第三个0交换位置。然后大于区域向左移动一位，i不变

这时候arr[i]等于0，小于1

【执行规则1】0与小于区域的下一位元素交换位置，于是第一个1和第二个0交换位置。然后小于区域向右移动一位，i++

这时候arr[i]等于0，小于1

【执行规则1】0与小于区域的下一位元素交换位置，于是第一个1和第三个0交换位置。然后小于区域向右移动一位，i++

这时候arr[i]等于1

【执行规则2】直接i++

这时候arr[i]等于2，大于0

【执行规则3】0与大于区域的上一位元素交换位置，于是第一个2和第一个2交换位置。然后大于区域向左移动一位，i不变

此时i已经到了最后的一个数并且遇到了大于区域了，就停止执行，此时数组中的值就变成了左边小于1；右边大于1；中间等于1。

2、3、快速排序子过程代码


void sort(int* arr, int L, int R){
    int tem = 0;
    int i = L - 1;
    while(L <= R){
        if(arr[L] < 1){
            tem = arr[i+1];
            arr[++i] = arr[L];
            arr[L] = tem;
            L++;
        } else if(arr[L] > 1){
            tem = arr[R];
            arr[R] = arr[L];
            arr[L] = tem;
            R--;
        } else{
            L++;
        }
    }
}
 
void sortColors(int* nums, int numsSize){
    sort(nums, 0, numsSize-1);
}

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/540606

【LeetCode力扣】75.颜色分类———快速排序子过程（荷兰国旗问题）

1、题目介绍

2、解题

2、1、 冒泡排序

2、2、快速排序的子过程

荷兰国旗解题思想

详细过程图：

2、3、快速排序子过程代码

2、1、冒泡排序