乍一看这个题目觉的被限制了很多条件,觉得这个排序不好实现,但是仔细想想这个不一定要正常的思维方式来实现排序,也可以说排序在题目上出现只是误导你的。
仔细读题发现两个关键点:
一个是只能与0 swap,大家都能发现不多说。
另一个是数组的下标和值是一一对应的。
第二个容易被忽略。所以只要读到一个元素时,如果值和下标不等,那么可以直接把这个元素的值放到正确位置上去,目标位置的值挪回来。当然这个过程要借助元素0来完成。
所以这样子就很简单的完成这题了。
void swap(int* num, int a, int b){
if(a == b) return;
int tmp = num[a];
num[a] = num[b];
num[b] = tmp;
}
void sort(int* num, int size){
int i = 0;
//move 0 to num[0]
for(;i<size;i++){
if(num[i] == 0){
swap(num, i, 0);
}
}
i = 1;
while(i<size){
//postion matched value
if(num[i] == i){
i++;
}
//postion mismatch value, then need to place value to the correct postition and continue
else{
int tarpos = num[i];
swap(num, 0, tarpos); // num[tarpos] = 0
swap(num, tarpos,i); // num[i] = 0
swap(num, 0, i); // num[0] = 0
}
}
}
int main(){
int input[] = {2,0,3,1};
sort(input, 4);
int t = 0;
for(;t<4;t++)
printf("%d->",input[t]);
printf("n");
}