QuickSortWithRec

package com.sxt;

import java.util.Arrays;

public class QuickSort {
	public static void main(String[] args) {
		int[] arr ={ -50, 50, 17, 25, 11, 45, 54, 1, 65, 77, 63, 85 };
		quickSort(arr, 0, arr.length - 1);
		System.out.println(Arrays.toString(arr));
	}
	// 使用递归来对数组进行分区
	public static void quickSort(int[] arr,int low,int high){
		if(low<high){
			int n=partition(arr,low,high);//递归头
			quickSort(arr,n+1,high);//递归体，排序后的以n为界限的右半部分进行排序
			quickSort(arr,low,n-1);//递归体，排序后的以n为界限的左半部分进行排序
		}
	}
	// 分区
	public static int partition(int[] arr,int low,int high){
		//设置基数的值
		int temp=arr[low];
		//循环
		while(low<high){
			//循环从数组右边找比基数值小的值
			while(low<high&&temp<=arr[high]){
				high--;
			}
			//如果找到了就将这个值放到基数值的左边
			arr[low]=arr[high];
			// 循环从数组左边找比基数大的值
			while(low<high&&temp>=arr[low]){
				low++;
			}
			// 如果找到了就将这个值放到基数值的右边
			arr[high]=temp;
		}
		return low;
	}
}