快速排序

快速排序的效率较高。如下代码：

 

public class QuickSort 
{	
	public static void main(String[] args)
	{
		int[] array = new int[12];
		for(int i=0; i<array.length; i++)
			array[i] = (int)(Math.random() * 100);
		
		Display(array, "Befor sort: ");
		
		Start(array);
		
		Display(array, "After sort: ");
	}
	
	public static void Start(int[] array)
	{
		Sort(array, 0, array.length-1);
	}
	
	public static void Sort(int[] array, int left, int right)
	{
		if(right - left <= 0)
			return;
		else
		{
			int temp = array[right];
			int index = Partition(array, left, right, temp);
			Sort(array, left, index-1);
			Sort(array, index+1, right);
		}
	}
	
	public static int Partition(int[] array, int left, int right, int value)
	{
		int leftValue = left - 1;
		int rightValue = right;
		
		while(true)
		{
			while(array[++leftValue] < value)
				;
			
			while(rightValue > 0 && array[--rightValue] > value)
				;
			
			if(leftValue >= rightValue)
				break;
			else
				Swap(array, leftValue, rightValue);
		}
		
		Swap(array, leftValue, right);
		
		return leftValue;
	}

	public static void Swap(int[] array, int i, int j)
	{
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
	public static void Display(int[] array, String str)
	{
		System.out.println(str);
		for(int i=0; i<array.length; i++)
			System.out.print(array[i] + "  ");
		System.out.println();
	}
}

 

 

一种输出结果为：

 

Befor sort: 
76  7  62  35  74  37  30  80  52  61  67  10  
After sort: 
7  10  30  35  37  52  61  62  67  74  76  80