//给定一个包含红，白，蓝且长度为 n 的数组，将数组元素进行分类使相同颜色的元素相邻，并按照红、白、蓝的顺序进行排序。

//我们可以使用整数 0，1 和 2 分别代表红，白，蓝。

使用两种分类方法，第二种使用了更多的空间达到速度更快的目的

include <sys/time.h>

include <time.h>

long recordTime()
{
struct timeval tv;
gettimeofday(&tv,NULL);
return tv.tv_sec * 1000 * 1000 + tv.tv_usec;
}
void compareCategray(int nums[],int size)
{
printf("Orignal Output:\n");
for(int i = 0;i< size;i++)
{
if(i%10 == 0)
{
printf("%d\n",nums[i]);
}else
{
printf("%d ",nums[i]);
}
}
long begin = recordTime();
// write your code here
for(int i = 0;i< size;i++)
{
for(int j = 0; j < size-i-1;j++)
{
if(nums[j] > nums[j+1])
{
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
long end = recordTime();
printf("first cost:%ld\n",end - begin);
printf("first Output:\n");
for(int i = 0;i< size;i++)
{
if(i%10 == 0)
{
printf("%d\n",nums[i]);
}else
{
printf("%d ",nums[i]);
}
}
begin = recordTime();
int zeroIndex = 0;
int oneIndex = 0;
int towIndex = 0;

int* zeroArr = (int*)malloc(size*sizeof(int));
int* oneArr = (int*)malloc(size*sizeof(int));
int* towArr = (int*)malloc(size*sizeof(int));

for (int i = 0;i< size;i++) {
    if(nums[i] == 0)
    {
        *(zeroArr+zeroIndex) = nums[i];
        zeroIndex++;
    }
    if(nums[i] == 1)
    {
        *(oneArr+oneIndex) = nums[i];
        oneIndex++;
    }
    if(nums[i] == 2)
    {
        *(towArr+towIndex) = nums[i];
        towIndex++;
    }
}

for (int i = 0; i<oneIndex; i++) {
    *(zeroArr+zeroIndex) = oneArr[i];
    zeroIndex++;
}

for (int i = 0; i<towIndex; i++) {
    *(zeroArr+zeroIndex) = towArr[i];
    zeroIndex++;
}
end = recordTime();

printf("second cost:%ld\n",end - begin);

printf("second Output:\n");
for(int i = 0;i< size;i++)
{
    if(i%10 == 0)
    {
        printf("%d\n",zeroArr[i]);
    }else
    {
        printf("%d ",zeroArr[i]);
    }
}
free(zeroArr);
free(oneArr);
free(towArr);

}