#include <stdio.h>
#include <stdlib.h>


/*
void Sort (int L[],  int n)
/ * 條塊顏色依次存放在L[0..n-1]中，本算法利用簡單選擇排序思想，將整個序列按紅、白、藍進行排序。* /
{
	int  i, j, x;
	i=0; 	/ * i指向第一個紅色條塊應該放的位置 * /
	for (j=i;  j<n;  j++)         / * j掃描所有尚未放置好的條塊，尋找紅色條塊 * /
	{	if (L[j]==1)               / * 找到一個紅色條塊* /
		{
			if (j!=i)             / * 找到的紅色條塊不在下一個紅色條塊應該放的位置則換位* /
			{
				x=L[j];
				L[j]=L[i];
				L[i]=x;
			}
			i++;               / * i指向下一個紅色條塊應該放的位置 * /
		}
	}
	/ * 退出前面循環后，i指向第一個白色條塊應該放的位置 * /
	for(j=i;  j<n;  j++)        / * j掃描所有尚未放置好的條塊，尋找白色條塊 * /
		if (L[j]==2)              / * 找到一個白色條塊* /
		{
			if (j!=i)             / * 找到的白色條塊不在下一個白色條塊應該放的位置則換位* /
			{
				x= L[j];
				L[j]= L[i];
				L[i]=x;
			}
			i++;                  / * i指向下一個白色條塊應該放的位置 * /
		}
}*/



void Sort (int L[],  int n)
/* 條塊顏色依次存放在L[0..n-1]中，本算法利用快速排序思想，將整個序列按紅、白、藍進行排序。*/
{
	int  x;
	int  r;          /* r指向紅色條塊區的下一個單元（同時也是白色條塊區的第一個單元）*/
	int  w;        /* w指向白色條塊區的下一個單元（同時也相當于快速排序中的low指針）*/
	int  b;         /* b指向藍色條塊區的前一個單元（同時也相當于快速排序中的high指針）*/
	r=w=0;                           /* 相當于low=0 */
	b=n-1;                           /* 相當于high=n-1 */
	while (w<=b)
	{
		x=L[w];
		if (x==1)           /*  L[w]是紅色條塊，并且在白色條塊區的下一個單元 */
		{
			L[w]= L[r];         /*  L[r]是第一個白色條塊，將其移到白色條塊區最后 */
			w++;                /*  w指向白色條塊區的下一個單元*/
			L[r]=x;             /*  將紅色條塊x放到紅色條塊區的下一個單元*/
			r++;               /* r指向紅色條塊區的下一個單元*/
		}
		else
			if (x==2)     /*  L[w]是白色條塊，并且恰好在白色條塊區的下一個單元 */
				w++;              /*  w指向白色條塊區的下一個單元*/
			else
			{              /*  L[w]是藍色條塊*/
				L[w]= L[b];    /*  b指向藍色條塊區的前一個單元，將L[b]與L[w]交換 */
				L[b]=x;
				b--;                /* b指向藍色條塊區的前一個單元*/
			}
	}
}


void main()
{
	int i,j;
	int r[20];
	int len;
	printf("請輸入待排序記錄的長度:");
	scanf("%d",&len);
	for(i=0;i<len;i++)
	{
		printf("請輸入第%d個記錄元素:",i);
		fflush(stdin);
		scanf("%d",&j);
		r[i] = j;
	}
	for(i=0;i<len;i++)
		printf("%d  ",r[i]);
	printf("\n");
	
	Sort(r,len);
	for(i=0;i<len;i++)
		printf("%d  ",r[i]);
	printf("\n");
	
}