leetcode官方解释
我的理解是否正确?希望能让大佬看到,不对的地方帮我指出来
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
void sortColors(int *a, int n) {
if(n < 2) return;
// 循环的书写必须遵循, 循环条件不变性原则, 对所有循环都适用
// 1. 首先要确定循环区间的上限与下限
// 2. 正确初始化自变量与参数,使得他们形成的区间满足实际的需求
// 3. 通过上面两步获取到的条件,确定循环的执行条件
// 如果执行条件不好想,就找执行结束的条件,循环结束条件的非就是循环执行条件
// 划分区间使用的规则:
// 1. 下闭上开的原则 2. 始终要保证区间的连续性,即划分后的区间合并后要是整个区间,
// 使得元素不重不漏(这就是找循环运行条件的方法)
// 整个区间: [0, n - 1]
// 引入自变量i后 [0, i), i, (i, n - 1]
// 引入参数左指针p后 [0, p), [p, i), (i, n - 1]
// 引入参数右指针q后 [0, p), [p, i), (q, n - 1]
// 至此,区间划分完毕 A: [0, p), B: [p, i), C: (q, n - 1]
// (q, n - 1]结合指针q的行为,是递减的, 所以认为(q, n - 1]是从n - 1开始到q的下闭上开区间
// 参数与自变量的初始化:
// 初始时,要保证区间A,B,C对应的区间都是空集合, 否则就不算是合理的
// 对于区间A, 当p = 0时即[0, 0)为空
// 对于区间B, 当p = 0且i = 0时即[0, 0)为空
// 对于区间C, 当q = n - 1时即(n - 1, n - 1]为空
// 循环执行条件:i与q划分区间B和C, 但是区间B和C并不是连续的
// 当 i + 1 == q 时, 会漏掉一个元素,所以 i <= q 才能使得B与C不漏掉结合处的那个元素
// 当 i > q 时, i已经进入了区间C,显然不能再往下执行了,
// 否则排列好的值为2的元素会被交换到区间B上, 所以运行条件为 i <= q
// 算法执行的规则:
// 由于要求的是按照升序排列, 同时数组排序必然要两两交换元素的值
// 现在要确定的是,A,B,C哪个区间首先处理
// 显然,指针i与q是对撞指针,q指针的行为非常明确,它就是维护区间C使得C中保存所有值为2的数组元素
// 所以,选择先处理指针P, 这样区间C先达到了题目的要求。这样,问题转化成0, 1排序的问题
// p是维护区间A使得A中保存所有值为0的数组元素,所以,处理完指针q之后紧接着处理指针p,
// 这样就是从0, 1序列中将0排到区间A上,那么剩下的1就自然全部落在了区间B上
// 也就是说对于 a[i] == 1 时, 无需进行交换操作。执行交换会打乱之前已经排好的顺序,只需让i自增即可
int p = 0, q = n - 1;
for(int i = 0; i <= q; i++) {
// 元素值是2且该元素值不区间C上执行交换
for(; a[i] == 2 && i >= 0 && i <= q; --q)
swap(&a[i], &a[q]);
// 元素值是0且该元素值不区间A上执行交换
for(; a[i] == 0 && i >= p && i <= q; ++p)
swap(&a[i], &a[p]);
// 元素值是1的数组元素,通过上面的交换不在区间B上的已经
// 被交换到了区间B上,在区间B上的1就不需要再做交换的动作了
// 否则,已经排好的顺序又会被打乱
}
}
void sortColors(int *a, int n) {
if(n < 2) return;
// [0, p], (p, i], (q, n]
int p = -1, q = n;
for(int i = 0; i < q; i++) {
while (a[i] == 2 && i >= 0 && i < q)
swap(&a[i], &a[--q]);
while (a[i] == 0 && i > p && i < q)
swap(&a[i], &a[++p]);
}
}
void sortColors(int *a, int n) {
if(n < 2) return;
// [0, p), [p, i], (q, n - 1]
// [0, p)为空,必须p = 0
// [p, i]为空, i == 0时, 集合会包含a[0], 所以i = -1
// (q, n - 1]为空, 必须q = n - 1
// i == q时, [p, q]与(q, n - 1]不重也不漏,运行条件: i <= q
// 但是考虑到i的初始值为-1,运行条件要改为 ++i <= q
int p = 0, i = -1, q = n - 1;
while(++i <= q) {
while (a[i] == 2 && i >= 0 && i <= q)
swap(&a[i], &a[q--]);
while (a[i] == 0 && i >= p && i <= q)
swap(&a[i], &a[p++]);
}
}
void sortColors(int *a, int n) {
if(n < 2) return;
// A: [0, p], B: (p, i), C: [q, n]
// 当p = -1时, [0, -1]为空, 如果p = 0时, [0, 0] 包含a[0]不为空
// 一开始p与i同步, 所以i = -1;
// i == -1作为数组元素非法,所以循环运行条件使用i时必须先自增
// 当i == m且q == m时, q先自减一, B: (p, m), C: [m - 1, n)区间存在交集
// 所以,循环运行的条件是: ++i < q
int p = -1, i = -1, q = n;
while(++i < q) {
while (a[i] == 2 && i > -1 && i < q)
swap(&a[i], &a[--q]);
while (a[i] == 0 && i > p && i < q)
swap(&a[i], &a[++p]);
}
}
void sortColors(int *a, int n) {
if(n < 2) return;
// A: [0, p], B: (p, i), C: [q, n]
// p = -1, q = n, 首先要移动指针再与a[i]交换
// 很明显, 指针q首先要做自减1操作,否则对数组访问就是非法的
// 如果i == q时,q先自减这样区间B与区间C就有交集
// i == q是循环停止的条件,即i < q是循环运行的条件
int p = -1, i = 0, q = n;
while(i < q) {
while (a[i] == 2 && i >= 0 && i < q)
swap(&a[i], &a[--q]);
while (a[i] == 0 && i > p && i < q)
swap(&a[i], &a[++p]);
++i;
}
}
void sortColors(int *a, int n) {
if(n < 2) return;
// [0, p], (p, i), [q, n]
int p = -1, i = -1, q = n;
// 显然, i在作为循环运行条件时必须先自增一
// 当 i == q 时, q会按照先自减一然后再操作的原则
// 此时的区间变成, (p, q)和[q - 1, n), 出现交集
// 所以此时的停止条件是, ++i < q
while(++i < q) {
while (a[i] == 2 && i >= 0 && i < q)
swap(&a[i], &a[--q]);
while (a[i] == 0 && i > p && i < q)
swap(&a[i], &a[++p]);
}
}
// p有i打辅助,而q没有任何辅助指针
// 所以, 对于q的维护只能用循环,而p则可用循环或者条件判断来维护
// 指针i对于指针p, q的作用是非对称性的
// 在区间划分上q才是关键因素
// 如果是升序, 在代码书写上最先写维护最大的值代码
// 如果是降序, 在代码书写上最先写维护最小的值代码
// 即都是先写处理右端区间对应的代码
#include <stdio.h>
void show(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
void swap(int* x, int* y) {
int t = *x;
*x = *y;
*y = t;
}
void sortColors(int* a, int n) {
// A: [0, p) == 0 i的取值区间:0 <= i < p
// B: [p, i) == 1 i的取值区间:p <= i <= q
// C: (q, n - 1] == 2 q才是真正划分区间的关键因素
if (n < 2) return;
// 变量的定义必须保证初始时A, B, C三个区间中的元素都为空
// 由于区间B和区间C不连续, 当 i < 时,
// 变量i会遗漏区间B和区间C都不包含的那个元素
// 为了包含这个元素,只能是 i <= q 时B区间包含该元素(i是自变量的原因, p, q看作参数)
// 因此,循环的运行的条件就是i <= q
int p = 0, q = n - 1;
for (int i = 0; i <= q; ++i) {
// 变量i看到的元素a[i] == 2, 它必须在区间C上,所以a[i]要与a[q]交换位置
// a[i] == 2时, i <= q表明a[i]不在区间C中
for (; i >= 0 && i <= q && a[i] == 2; --q)
swap(&a[i], &a[q]);
// a[i] == 0时, p <= i <= q表明a[i]不在区间A中
/*if (i >= p && i <= q && a[i] == 0)
swap(&a[i], &a[p++]);
*/
// 换成循环也没毛病
for(; i >= p && i <= q && a[i] == 0; ++p)
swap(&a[i], &a[p]);
// a[i] == 1 出现在区间B中的1无需移动
if(i >= p && i <= q && a[i] == 1)
continue;
}
}
void sortColors(int* a, int n) {
// A: [0, p) == 0
// B: [p, i) == 1
// C: (q, n - 1] == 2
if(n < 2) return;
int p = 0, q = n - 1;
for (int i = 0; i <= q; ++i) {
for (; i >= 0 && i <= q && a[i] == 2; --q)
swap(&a[i], &a[q]);
for(; i >= p && i <= q; ++p)
if(a[i] == 0) swap(&a[i], &a[p]);
else if(a[i] == 1) break;
}
}
void sortColors(int* a, int n) {
// A: [0, p) == 0
// B: [p, i) == 1
// C: (q, n - 1] == 2
if(n < 2) return;
int p = 0, q = n - 1;
for (int i = 0; i <= q; ++i) {
// 变量i看到的元素a[i] == 2, 它必须在区间C上,所以a[i]要与a[q]交换位置
// a[i] == 2 时, i <= q表明a[i]不在区间C中
for (; i <= q && a[i] == 2; --q)
swap(&a[i], &a[q]);
// a[i] == 0 时, p < i <= q表明a[i]不在区间A中
for(; i >= p && i <= q && a[i] == 0; ++p)
swap(&a[i], &a[p]);
// a[i] == 1 出现在区间B中的1无需移动
}
}
void sortColors(int* a, int n) {
int p = 0;
int q = n - 1;
int i = 0;
while(i <= q) {
if(a[i] == 0) {
swap(&a[i], &a[p]);
++p, ++i;
}
else if(a[i] == 1) ++i;
else if(a[i] == 2) {
//交换完这一步i是不能+1的,因为可能换的是0,如果+1就把这个0忽略了
swap(&a[i], &a[q]);
--q;
}
}
}
int main() {
int a[] = {2, 0, 2, 1, 1, 0 };
int n = sizeof(a) / sizeof(a[0]);
show(a, n);
sortColors(a, n);
show(a, n);
return 0;
}