qcksrt.cpp

VC常用数值算法集C7 ECLASS.CPP ECLAZZ.CPP INDEXX.CPP PIKSR2.CPP PIKSRT.CPP QCKSRT.CPP RANK.CPP SHELL

void qcksrt(int n, double arr[])
{
    int m = 7; int nstack = 50; int fm = 7875; int fa = 211;
	int fc = 1663; double a,fmi = 0.00012698413;
    int istack[51];
    int jstack = 0;
    int i,j,done,iq,l = 1;
    int ir = n;
    int fx = 0;
    do
	{
		if (ir - l < m)
		{
			for (j = l + 1; j<=ir; j++)
			{
				a = arr[j];
				for (i = j - 1; i>=1; i--)
				{
					if (arr[i] <= a)
					{
						break;
					}
					arr[i + 1] = arr[i];
				}
				if (arr[i] == 0)
				{
					i = 0;
				}
				arr[i + 1] = a;
			}
			if (jstack == 0)
			{
				return;
			}
			ir = istack[jstack];
			l = istack[jstack - 1];
			jstack = jstack - 2;
		}
		else
		{
			i = l;
			j = ir;
			fx = fx * fa + fc - fm * int((fx * fa + fc) / fm);
			iq = l + (ir - l + 1) * (fx * fmi);
			a = arr[iq];
			arr[iq] = arr[l];
			do
			{
				do
				{
					if (j > 0)
					{
						if (a < arr[j])
						{
							j = j - 1;
							done = 0;
						}
						else
						{
							done = -1;
						}
					}
				}while(!done);
				if (j <= i)
				{
					arr[i] = a;
					break;
				}
				arr[i] = arr[j];
				i = i + 1;
				do
				{
					if (i <= n)
					{
						if (a > arr[i])
						{
							i = i + 1;
							done = 0;
						}
						else
						{
							done = -1;
						}
					}
				}while(!done);
				if (j <= i)
				{
					arr[j] = a;
					i = j;
					break;
				}
				arr[j] = arr[i];
				j = j - 1;
			}while(1);
			jstack = jstack + 2;
			if (jstack > nstack)
			{
				cout<<"nstack must be made larger."<<endl;
				return;
			}
			if (ir - i >= i - l)
			{
				istack[jstack] = ir;
				istack[jstack - 1] = i + 1;
				ir = i - 1;
			}
			else
			{
				istack[jstack] = i - 1;
				istack[jstack - 1] = l;
				l = i + 1;
			}
		}
	}while(1);
}