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小的第一个数值，下标为righttemp=A[right];A[right]=A[left];A[left]=temp;while(left<right&&key>A[left])left++;//从左向右找出比key大的第一个数值，下标为lefttemp=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 stubint[] 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]+",");}}