描述：基数排序问题
错误代码c语言代码⬇️
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void sortColors(int* nums, int numsSize){
int p1,p2,i;
p1 = 0;
p2 = numsSize - 1;
for(i = 0; i <= p2; i++){
if(nums[i] == 0){
swap(&nums[i], &nums[p1]);
p1++;
}
else if(nums[i] == 2){
// while(nums[i] == 2){
// swap(&nums[i], &nums[p2]);
// p2--;
// }
swap(&nums[i], &nums[p2]); p2--;
}
}
}
输入：
[1,2,0]
输出：
[1,0,2]
预期结果：
[0,1,2]
错误原因：这里当i指向2时，num[i] 与 nums[p2] 交换了位置，而后i++，这就引起了换过来的0被越过去了
解决的方法是先进行 =0？的 判断，而后再进行=2？的判断。
现在考虑一下，为什么先判断0就可以，而先判断2就不可以
因为但凡i走过去了，那么
1⃣️如果当前节点的值是2，那么遇到了nums[i] = 2时，交换了之后还是2，所以需要将p2往前移动一次，在进行交换，重复进行，直到p2指向的值不等于2。
2⃣️如果当前节点值为0，遇到了nums[i] = 2,交换了之后，nums[i] = 0,因此还需要和p1指向的值交换一次。
所以应该先判断p2指针指向的情况，然后在判断p1指针指向的值的情况。
以下是改正了之后的代码⬇️
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void sortColors(int* nums, int numsSize){
int p0,p2,i;
p0 = 0;
p2 = numsSize - 1;
for(i = 0; i <= p2; i++){
if(nums[i] == 2){
while(nums[i] == 2){
swap(&nums[i], &nums[p2]);
p2--;
}
//swap(&nums[i], &nums[p2]); p2--;
}
if(nums[i] == 0){
swap(&nums[i], &nums[p0]);
p0++;
}
}
}
提示堆缓冲区溢出
最后输入[2]
错误原因：当nums[i] == 2时，swap函数交换了nums[i], nums[p2]的值，随后p2的值-1，此时p2的值为-1， 而此时nums[i]的值仍为2，继续执行swap函数，而此时访问的数组的下标为-1，访问越界
改正方法：在whlie循环中加入判断，&& i <= p2
如此事可成矣，代码为通过代码2
换了一种思路，既然遇到2换2的时候，总需要一次while循环，之所以需要进行一次while循环，是因为p2指针当前指向的值为2，那我我可不可以先进行一次while循环，将p2往前走，直到指向一个非2的值，于是代码如下⬇️
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void sortColors(int* nums, int numsSize){
int p0,p2,i;
p0 = 0;
p2 = numsSize - 1;
while(nums[p2] == 2)
numsSize--;
for(i = 0; i <= p2; i++){
if(nums[i] == 2){
swap(&nums[i], &nums[p2]);
p2--;
}
if(nums[i] == 0){
swap(&nums[i], &nums[p0]);
p0++;
}
}
}
最后输入[2],
提示超时，同样的样例，不同的错误，妙
失误，改了while语句，同样的错误提示了
改成p2–之后仍然错误，遍寻错误，百思不解，思索许久，终于找到原来是while循环，当第一次while循环之后，p2- - ，减至-1，此时第二遍while循环进行，又是对nums[-1]进行了判断，出现了数组越界的情况。
解答以上错误⬇️，但仍是错误的
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void sortColors(int* nums, int numsSize){
int p0,i;
p0 = 0;
int p2 = numsSize - 1;
while(p2 >= 0 && nums[p2] == 2)
p2--;
for(i = 0; i <= p2; i++){
if(nums[i] == 2){
swap(&nums[i], &nums[p2]);
p2--;
}
if(nums[i] == 0){
swap(&nums[i], &nums[p0]);
p0++;
}
}
}
输入：
[0,2,2,2,0,2,1,1]
输出：
[0,0,1,2,1,2,2,2]
预期结果：
[0,0,1,1,2,2,2,2]
分析下这里的错误，因为只是在第一次避免了2换2的情况，而忽略了以后也可能出现2换2的情况，所以应该在每一次p2往前移之后，都再进行一次while循环，保证p2当前指向的值不是2，
事至此，时间复杂度已经和method2一般无二，可惜。
略显笨拙的基数排序，需要一次遍历，再加一次赋值，时间复杂度O（n）
c语言代码⬇️
void sortColors(int* nums, int numsSize){
int arr[3];
memset(arr, 0, sizeof(int)*3);
for(int i = 0; i < numsSize; i++){
arr[nums[i]] ++;
}
int j = 0;
for(int i = 0; i < 3; i++){
while(arr[i] != 0){
nums[j++] = i;
arr[i] --;
}
}
}
通过代码2:
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void sortColors(int* nums, int numsSize){
int p0,p2,i;
p0 = 0;
p2 = numsSize - 1;
for(i = 0; i <= p2; i++){
if(nums[i] == 2){
while(nums[i] == 2 && i <= p2){
swap(&nums[i], &nums[p2]);
p2--;
}
}
if(nums[i] == 0){
swap(&nums[i], &nums[p0]);
p0++;
}
}
}
通过代码3:
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void sortColors(int* nums, int numsSize){
int p0,i;
p0 = 0;
int p2 = numsSize - 1;
while(p2 >= 0 && nums[p2] == 2)
p2--;
for(i = 0; i <= p2; i++){
if(nums[i] == 2){
swap(&nums[i], &nums[p2]);
p2--;
while(p2 >= 0 && nums[p2] == 2)
p2--;
}
if(nums[i] == 0){
swap(&nums[i], &nums[p0]);
p0++;
}
}
}
总结
总结：无
