quicksortarray.cs

十分完善的华容道程序,有多种布局的求解!

using System;

namespace HRD.Core
{
	internal class DataElement
	{
		public int index;
		public int value;
		
		public DataElement()
		{
		}
		
		public DataElement(int index, int value)
		{
			this.index = index;
			this.value = value;
		}
	}

	internal class QuickSortArray
	{
		public static DataElement[] list = new DataElement[12];

		static QuickSortArray()
		{
			for(int i = 0; i<12; i++)
				list[i] = new DataElement(0, 0);
		}

		public static void quickSort()
		{
			recQuickSort(0, list.Length - 1);
		}

		private static void recQuickSort(int first, int last)
		{
			int pivotLocation;

			if(first < last)
			{
				pivotLocation = partition(first, last);
				recQuickSort(first, pivotLocation - 1);
				recQuickSort(pivotLocation + 1, last);
			}
		}

		private static int partition(int first, int last)
		{
			DataElement pivot;

			int index, smallIndex;

			swap(first, (first + last) / 2);

			pivot = list[first];
			smallIndex = first;

			for(index = first + 1; index <= last; index++)
				if(list[index].value < pivot.value)
				{
					smallIndex++;
					swap(smallIndex, index);
				}

			swap(first, smallIndex);

			return smallIndex;
		}

		private static void swap(int first, int second)
		{
			DataElement temp;

			temp = list[first];
			list[first] = list[second];
			list[second] = temp;
		}
	}
}