/**
* 快速排序算法：分解：数据arr[p..r]被划分成两个(可能空)的子数组arr[p..q-1]和arr[q+1..r]
* 使得arr[p..q-1]中的每个元素都小于等于arr(q)，而arr[q+1..r]中的每个元素大于等于arr[q]
* 解决：通过递归调用快速排序，对子数组arr[p..q-1]和arr[q+1..r]排序
* 合并：因为两个子数组是就地排序，将它们合并不需要操作：整个数组arr[p..r]已排序
*/
public class QuickSort {
/**
* 选择arr[r]作为主元，将比arr[r]小的元素放在arr[r]前面(这里记为小元素部分)，
* 将比arr[r]小的元素放在arr[r]后面(这里记为大元素部分)
* @param arr
* @param p 分解的开始元素位置
* @param r 分解的结束元素位置
*/
static int partition(int arr[],int p,int r){
//i为小元素部分中下标最大的位置，也就是它的下一个位置(即i+1)就是大元素部分下标最小的位置，初始化为p的前一个位置
int i = p-1;
//从p个元素开始，一直检查到r前面的一个元素
for(int j= p;j<r;j++){
//如果arr[j]是比arr[r]小的元素，要放在小元素位置，由于i标记的是小元素部分下标最大的位置，
//所以arr[j]应该被换到i+1的位置
if(arr[j]<arr[r]){
i++;
int temp = arr[i];
arr[i]= arr[j];
arr[j]= temp;
}
}
//最后把arr[r]放在小元素部分和大元素部分中间
int tem = arr[r];
arr[r] = arr[i+1];
arr[i+1]=tem;
return i+1;
}
/**
* 外层的排序函数，先分解，然后再递归调用quickSort排序函数对分解的两部分进行排序
* @param arr
* @param p
* @param r
*/
static void quickSort(int arr[],int p,int r){
if(p<r){
int q = partition(arr,p,r);
quickSort(arr,p,q-1);
quickSort(arr,q+1,r);
}
}
//测试.....
public static void main(String[] args) {
int arr[] = {2,8,7,1,3,5,6,4};
quickSort(arr,0,arr.length-1);
for(int i = 0;i<arr.length;i++)
System.out.println(arr[i]);
}
}
