陈利人博客面试题之我解：数组排序

排序只有1、2、3三个元素的数组，不能统计1、2、3的个数

分析：
假如我们按照常规的排序算法来做的话，最快也要（nlgn）的时间复杂度，既然我们知道数组中仅仅存在1、2、3三个数字，很自然的想到我们可以把数组重新排列成三块，如何排列呢？
我们可以用三个指针，分别指向1的序列的末尾，2的序列的末尾，3的序列的开头位置，初始化p1 = p2 = 0，p3 = size -  1，依次扫描整个数组，假如碰到的是2，指针p2后移，如果遇到1，交换p1和p2所指向的元素，两个指针同时后移，如果遇到3，向右移动p3，直到p3指向一个不为3的元素，交换p2 和 p3，这样扫描一遍数组，即可完成排序。

代码如下：

/*************************************************************************
    > File Name: 27.cpp
    > Author: dongdaoxiang
    > Func: sort array just have 1,2,3，can not statistic the number of them
    > Mail: [e-mail]
    > Created Time: 2013年07月22日 星期一 13时58分09秒
 ************************************************************************/
#include<iostream>
using namespace std;

void sort(int *arr, const int size)
{
    if(NULL == arr)
        return;
    int p1 = 0, p2 = 0, p3 = size - 1;
    while(p2 < p3)
    {
        if(arr[p2] == 2)
        {
            p2++;
        }
        if(arr[p2] == 1)
        {
            swap(arr[p1], arr[p2]);
            p1++;
            p2++;
        }
        if(arr[p2] == 3)
        {
            while(p2 < p3 && arr[p3] == 3)
            {
                p3--;
            }
            swap(arr[p2], arr[p3]);
        }
    }
}

int main()
{
    int arr[10] = {2, 1,2,3,1,1,2,3,2,3};
    sort(arr, 10);
    int i = 0;
    for(i = 0; i < 10; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}