LQ0219 三部排序【程序填空】

题目来源：蓝桥杯2013初赛 C++ B组F题

题目描述
本题为代码补全填空题，请将题目中给出的源代码补全，并复制到右侧代码框中，选择对应的编译语言（C/Java）后进行提交。若题目中给出的源代码语言不唯一，则只需选择其一进行补全提交即可。复制后需将源代码中填空部分的下划线删掉，填上你的答案。提交后若未能通过，除考虑填空部分出错外，还需注意是否因在复制后有改动非填空部分产生错误。

一般的排序有许多经典算法，如快速排序、希尔排序等。

但实际应用时，经常会或多或少有一些特殊的要求。我们没必要套用那些经典算法，可以根据实际情况建立更好的解法。

比如，对一个整型数组中的数字进行分类排序：

使得负数都靠左端，正数都靠右端，0 在中部。注意问题的特点是：负数区域和正数区域内并不要求有序。可以利用这个特点通过 1 次线性扫描就结束战斗!!

以下的程序实现了该目标。

其中 x 指向待排序的整型数组，len 是数组的长度。

请分析代码逻辑，并推测划线处的代码。

源代码
C

#include 

void show(int* x, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        printf("%d,",x[i]);
    }
    
    printf("\n");
}

void sort3p(int* x, int len)
{
    int p = 0;
    int left = 0;
    int right = len-1;
    
    while(p<=right){
        if(x[p]<0){
            int t = x[left];
            x[left] = x[p];
            x[p] = t;
            left++;
            p++;
        }
        else if(x[p]>0){
            int t = x[right];
            x[right] = x[p];
            x[p] = t;
            right--;
            //p++;                
        }
        else{
            _______________;
        }
    }
    
    show(x, len);
}

int main()
{
    int a[] = {-1,0,1,-2,0,2,-3,0,0,3,-4,-5,4,-6,0,5,6};
    int b[] = {-1,0,-1,-2,0,-2,-3,0,0,-3,-4,-5,-4,-6,0,-5,-6};
    int c[] = {1,0,1,2,0,2,3,0,0,3,4,5,4,6,0,5,6};
    
    sort3p(a,sizeof(a)/sizeof(int));
    sort3p(b,sizeof(b)/sizeof(int));
    sort3p(c,sizeof(c)/sizeof(int));
        
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

Java

import java.util.*;
public class Main
{
    static void sort(int[] x)
    {
        int p = 0;
        int left = 0;
        int right = x.length-1;
        
        while(p<=right){
            if(x[p]<0){
                int t = x[left];
                x[left] = x[p];
                x[p] = t;
                left++;
                p++;
            }
            else if(x[p]>0){
                int t = x[right];
                x[right] = x[p];
                x[p] = t;
                right--;
                //p++;                
            }
            else{
                ______________;
            }
        }
        
        show(x);
    }
    
    static void show(int[] x)
    {
        for(int i=0; i<x.length; i++)
        {
            System.out.print(x[i] + ",");
        }
        
        System.out.println();
    }
    
    public static void main(String[] args)
    {
        //int[] x = {25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0};
        sort(new int[]{-1,0,1,-2,0,2,-3,0,0,3,-4,-5,4,-6,0,5,6});
        sort(new int[]{-1,0,-1,-2,0,-2,-3,0,0,-3,-4,-5,-4,-6,0,-5,-6});
        sort(new int[]{1,0,1,2,0,2,3,0,0,3,4,5,4,6,0,5,6});
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

问题分析
C语言程序填入“p++”
Java语言程序也是填入“p++”

AC的C语言程序如下：

#include 

void show(int* x, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        printf("%d,",x[i]);
    }
    
    printf("\n");
}

void sort3p(int* x, int len)
{
    int p = 0;
    int left = 0;
    int right = len-1;
    
    while(p<=right){
        if(x[p]<0){
            int t = x[left];
            x[left] = x[p];
            x[p] = t;
            left++;
            p++;
        }
        else if(x[p]>0){
            int t = x[right];
            x[right] = x[p];
            x[p] = t;
            right--;
            //p++;                
        }
        else{
            p++;
        }
    }
    
    show(x, len);
}

int main()
{
    int a[] = {-1,0,1,-2,0,2,-3,0,0,3,-4,-5,4,-6,0,5,6};
    int b[] = {-1,0,-1,-2,0,-2,-3,0,0,-3,-4,-5,-4,-6,0,-5,-6};
    int c[] = {1,0,1,2,0,2,3,0,0,3,4,5,4,6,0,5,6};
    
    sort3p(a,sizeof(a)/sizeof(int));
    sort3p(b,sizeof(b)/sizeof(int));
    sort3p(c,sizeof(c)/sizeof(int));
        
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

AC的Java语言程序如下：

import java.util.*;
public class Main
{
    static void sort(int[] x)
    {
        int p = 0;
        int left = 0;
        int right = x.length-1;
        
        while(p<=right){
            if(x[p]<0){
                int t = x[left];
                x[left] = x[p];
                x[p] = t;
                left++;
                p++;
            }
            else if(x[p]>0){
                int t = x[right];
                x[right] = x[p];
                x[p] = t;
                right--;
                //p++;                
            }
            else{
                p++;
            }
        }
        
        show(x);
    }
    
    static void show(int[] x)
    {
        for(int i=0; i<x.length; i++)
        {
            System.out.print(x[i] + ",");
        }
        
        System.out.println();
    }
    
    public static void main(String[] args)
    {
        //int[] x = {25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0};
        sort(new int[]{-1,0,1,-2,0,2,-3,0,0,3,-4,-5,4,-6,0,5,6});
        sort(new int[]{-1,0,-1,-2,0,-2,-3,0,0,-3,-4,-5,-4,-6,0,-5,-6});
        sort(new int[]{1,0,1,2,0,2,3,0,0,3,4,5,4,6,0,5,6});
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50