题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 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
进阶：
你能想出一个仅使用常数空间的一趟扫描算法吗？
解题方案
快速排序
- C 冒泡排序法
void bubbleSort(int *array, int size) { for (int step = 0; step < size - 1; ++step) { // 在每一轮中，最大的元素会冒泡到最后 for (int i = 0; i < size - step - 1; ++i) { // 根据元素值比较和交换位置 if (array[i] > array[i + 1]) { // 使用异或操作交换两个元素，不需要额外的存储空间 array[i] = array[i] ^ array[i + 1]; array[i + 1] = array[i] ^ array[i + 1]; array[i] = array[i] ^ array[i + 1]; } } } } void sortColors(int* nums, int numsSize) { bubbleSort(nums, numsSize); // 冒泡排序 }
复杂度分析
时间复杂度平均情况下为 O(n2)，其中 n 是数组 nums 的长度。
空间复杂度为 O(1)，不需要额外的存储空间。
- C 单指针法
void swap(int *a, int *b) // 交换函数 { int temp = *a; *a = *b; *b = temp; } void sortColors(int *nums, int numsSize) { int ptr = 0; for (int i = 0; i < numsSize; ++i) // 第一次遍历 { if (nums[i] == 0) { swap(&nums[i], &nums[ptr]); // 将 0 移动到前端 ++ptr; } } for (int i = ptr; i < numsSize; ++i) //第二次遍历 { if (nums[i] == 1) { swap(&nums[i], &nums[ptr]); // 将 1 移动到前端 ++ptr; } } }
复杂度分析
时间复杂度为O(n)，其中 n 是数组 nums的长度。
空间复杂度为O(1)，不需要额外的存储空间。
- C 双指针
void swap(int *a, int *b) // 交换函数 { int temp = *a; *a = *b; *b = temp; } void sortColors(int *nums, int numsSize) { int head = 0, tail = numsSize - 1; for (int i = 0; i <= tail; ) // 一次遍历 { if (nums[i] == 0) { swap(&nums[i], &nums[head]); // 将 0 移动到前端 head++; i++; } else if (nums[i] == 2) { swap(&nums[i], &nums[tail]); // 将 2 移动到尾端 tail--; } else { i++; } } }
复杂度分析
时间复杂度为O(n)，其中 n 是数组 nums的长度。
空间复杂度为O(1)，不需要额外的存储空间。
