算法-快速排序

package com.arithmetic.sort;
/**
 * 快速排序法：
 * 1 选择轴值 ，尽可能使得Left and Right 相等
 * 策略： 选择最左边；随机选择；选择平均值
 * 
 * @author Administrator
 *
 */
public class QuickSort {
	public static void main(String[] args) {
		int [] arrays = new int[]{8,2,7,3,6,4,9,1,5,10};
		quickSort(arrays, 0, arrays.length-1);
		for(int i = 0; i<arrays.length;i++){
			System.out.print(arrays[i]+" ");
		}
		System.out.println();
	}
	/**
	 * 这个函数用于产生轴值或者叫做基准值的位置
	 * @param begin
	 * @param end
	 * @return
	 */
	public static int getPivot(int begin, int end){
		return (begin + end) >> 1;
	}
	/**
	 * 每一次的分割
	 * @param arrays
	 * @param begin
	 * @param end
	 * @return
	 */
	private static int partition(int[] arrays, int begin, int end){
		//得到基准值位置
		int pivot = getPivot(begin, end);
		//得到基准值
		int pivotValue = arrays[pivot];
		/*将最后一个值赋给pivot 位置,意思就是把轴值作为一个临时变量用于和子序列进行比较，而最后一个
		 *空着，我们会第一个大于轴值得数据
		 */
		arrays[pivot] = arrays[end];
		//只要begin 和 end不相等 ，我们就认为本次排序没有结束
		while(begin != end){
			//如果begin <end 且 array[begin] < 轴值,我们就认为这个数比轴值小，而不用去管他，就继续比较下一个
			while(begin < end && arrays[begin] < pivotValue){
				begin++;
			}
			//如果begin <end 但是array[begin] > 轴值，我们就把当前值放在最后一个位置
			//并且 end位置往前移动一个指针
			if(begin < end && arrays[begin] > pivotValue){
				arrays[end] = arrays[begin];
				end--;
			}
			//此时我们就从右边开始比较比，比轴值小的放到刚才begin的位置,如果比轴值大，我们不管
			while(begin < end && arrays[end] >= pivotValue ){
				end --;
			}
			//如果begin < end， 但是array[end] < 轴值，我们就把当前值放在begin空着的那个位置
			if(begin < end && arrays[end] < pivotValue){
				arrays[begin] = arrays[end];
				begin++;
			}
		}
		//如果begin 和 end 相遇，即begin == end,此时两个下标指向同一个元素，即轴值
		arrays[begin] = pivotValue;
		return begin;
	}
	/**
	 * 开始进行快速排序
	 * @param arrays
	 * @param low
	 * @param high
	 */
	public static void quickSort(int[] arrays, int low, int high){
		if((high - low) < 1){//如果只有一个数或者为空 直接返回
			return;
		}
		if((high - low) == 1){//如果只有2个数，且前面的数大于后面的数，我们直接交换没有必要快速排序
			if(arrays[low] > arrays[high]){
				swap(arrays, low, high);
			}
		}
		int pivotPosition = partition(arrays, low, high);
		quickSort(arrays, low, pivotPosition);//（递归）前面那个子序列
		quickSort(arrays, pivotPosition+1, high);//（递归）后面子序列
	}
	/**
	 * 进行值交换
	 * @param arrays
	 * @param index1
	 * @param index2
	 */
	public static void swap(int[] arrays,int index1, int  index2 ){
		int tmp = arrays[index1];
		arrays[index1] = arrays[index2];
		arrays[index2] = tmp;
	}
}