quicksorter.java.bak

利用遗传算法解决TSP旅行商问题的Java原码

public class QuickSorter extends Sorter
{
	private IllegalArgumentException err1=new IllegalArgumentException("stack overflow in quickSort");

	private class StackItem
	{
		public int left;
		public int right;
	};

	/**
	*method:getvalue()
	*param:
	*return: double
	*/
	private  double getvalue(CityMap[] cm)
	{
		//CityMap[] cm=new CityMap[GENE_NUMBER];
		//cm=citymap;
		double routevalue=0.0;
		double px,py,qx,qy;
		for (int i=0;i<cm.length-1;i++)
		{
			px=cm[i].getxpos();
			py=cm[i].getypos();
			qx=cm[i+1].getxpos();
			qy=cm[i+1].getypos();
			routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		}
		double first_end;
		px=cm[0].getxpos();
		py=cm[0].getypos();
		qx=cm[cm.length-1].getxpos();
		qy=cm[cm.length-1].getypos();
		first_end=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		return routevalue+first_end;

	}

	public void Sort(Object []list,SortTool tool,boolean descending)
	{
		//creat stack
		final int stackSize=32;
		StackItem [] stack=new StackItem[stackSize];

		for (int n=0;n<32;++n)
		{
			stack[n]=new StackItem();
		}

		int stackPtr=0;  //stack top pointer

		//determine direction of sort
		int comp;
		if (descending)
		{
			comp=SortTool.COMP_GRTR;
		}
		else
		{
			comp=SortTool.COMP_LESS;
		}

		//size of nimum partition to median of three;
		final int Threshold=7;

		//size of left and right partitions 
		int lsize,rsize;

		//create working indexes

		int l,r,mid,scanl,scanr,pivot;

		//set initial values
		l=0;
		r=list.length-1;
		//System.out.println("rrrrrr= "+r);

		Object temp;

		//main loop
		while (true)
		{
			while (r>l)
			{
				//test
				//System.out.println("________________-");
				if ((r-l)>Threshold)
				{
					//median of three partitioning
					mid=(r+l)/2;

					//three-sort left,middle ,and right elements
					if (tool.compare(getvalue((CityMap[])list[mid]),getvalue((CityMap[])list[l]))==comp)
					{
						temp=list[mid];
						list[mid]=list[l];
						list[l]=temp;
					}

					if (tool.compare(getvalue((CityMap[])list[r]), getvalue((CityMap[])list[l]))==comp)
					{
						temp=list[r];
						list[r]=list[l];
						list[l]=temp;
					}

					if (tool.compare(getvalue((CityMap[])list[r]),getvalue((CityMap[])list[mid]))==comp)
					{
						temp=list[mid];
						list[mid]=list[l];
						list[l]=temp;
					}
					//setup for partitioning
					pivot=r-l;
					temp=list[mid];
					list[mid]=list[pivot];
					list[pivot]=temp;

					scanl=l+1;
					scanr=r-2;

				}
				else
				{
					//set up for partitioning
					pivot=r;
					scanl=l;
					scanr=r-1;
				}

				for (; ; )
				{
					//
					//scanf from left for element >=to pivot
					//System.out.println("scanl "+ scanl+"\tscanr "+scanr);
					while ((tool.compare(getvalue((CityMap[])list[scanl]),getvalue((CityMap[])list[pivot]))==comp)&& (scanl<r))
					{
						++scanl;
					}

					while ((tool.compare(getvalue((CityMap[])list[pivot]),getvalue((CityMap[])list[scanr]))==comp)&& (scanr>l))
					{
						--scanr;
						//System.out.println("--scanr"+scanr);
					}

					//if scans have met,exit inner loop
					if (scanl>=scanr)
					{
						break;
					}
					//exchange elements
					temp=list[scanl];
					list[scanl]=list[scanr];
					list[scanr]=temp;

					if (scanl<r)
					{
						++scanl;
					}
					if (scanr>l)
					{
						--scanr;
					}
				}
				//exchange final elements

				temp=list[scanl];
				list[scanl]=list[pivot];
				list[pivot]=temp;

				//place largest partition of stack
				//System.out.println("scaplace largest partition of stackr ");
				lsize=scanl-l;
				rsize=r-scanl;

				if (lsize>rsize)
				{
					if (lsize!=1)
					{
						++stackPtr;

						if (stackPtr==stackSize)
						{
							throw err1;
						}
						stack[stackPtr].left=1;
						stack[stackPtr].right=scanl-1;

					}
					//
					if (rsize!=0)
					{
						l=scanl+1;
					}
					else
					{
						break;
					}
				}
				else
				{
					if (rsize!=1)
					{
						//
						++stackPtr;

						if (stackPtr==stackSize)
						{
							throw err1;
						}
						stack[stackPtr].left=scanl+1;
						stack[stackPtr].right=r;

					}
					if (lsize!=0)
					{
						r=scanl-1;
					}
					else
					{
						break;
					}
				}
				

			}
			//
			//iterate with values from stack

			if (stackPtr!=0)
			{
				l=stack[stackPtr].left;
				r=stack[stackPtr].right;

				--stackPtr;
			}
			else
			{
				break;
			}


		}
	}
};