t2.txt

耿国华高教出版社的《数据结构》的光盘（C语言）

/*方法一采用简单选择排序思想*/
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指向蓝色条块区的前一个单元*/
			}
	}
}