2012/3/29-快速排序

2012/3/29----快速排序

前面用到了分治算法所演变出来的一种排序---归并排序。这里，我们介绍另一种分治算法演变出来的排序算法---快速排序。

快速排序通过选取数组中的关键字，把一个A[n]数组划分为3部分：A[key]=关键字，A[0...key-1]={比关键字小的元素}，A[key+1...n-1]={比关键字大的元素}。然后递归调用这个过程便可实现对数组的排序。

 

/*
 *分治算法引申出来的又一种排序算法---快速排序算法
 *version 1.0 2012、3、29
 *author akon
 */
 package com.akon405.www;
public class QuickSort {
	
	public int division(int[] A,int left,int right){
		int key=A[left];//确定最右边的数组元素为关建数值
		int temp;
		//下面循环可以把输入的数组A以key值为界限，分为两拨。key前面的数值比key小，key后面的数值比key大
		while(left!=right){
		while(left<right&&key<A[right])
			right--;//从右向左找出比key小的第一个数值，下标为right
		temp=A[right];
		A[right]=A[left];
		A[left]=temp;
		while(left<right&&key>A[left])
			left++;//从左向右找出比key大的第一个数值，下标为left
		temp=A[right];
		A[right]=A[left];
		A[left]=temp;
		}
		return left;//分割点的下标，left=right
	}
	
	public void quickSort(int[] A,int left,int right){
		int i;
		if(left<right){
			i=division(A,left,right);
			quickSort(A,left,i-1);//对key前面的数组进行排序
			quickSort(A,i+1,right);//对key后面的数组进行排序
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={20,39,10,4,87,46,83,57};
		QuickSort qs=new QuickSort();
		int left=0;
		int right=A.length-1;
		qs.quickSort(A,left,right);
		System.out.print("排序结果：");
		for(int i=0;i<6;i++)
			System.out.print(A[i]+",");
	}

}