java简单快速排序实例解析
一、基本概念
快速排序是一种基于比较的排序算法，通过选择一个基准元素（pivot），将数组分为两个部分，使得左边的元素小于或等于基准元素，右边的元素大于或等于基准元素，然后使用递归将其他元素排序。每个元素都位于正确的位置，排序完成。
二、选择基准元
选择基准元是快速排序的关键步骤，常见的方法有固定基准元、随机基准元和三数取中。
1. 固定基准元：如果输入序列是随机的，处理时间是可以接受的。但是，如果数组已经有序时，分割就是一个非常不好的分割，时间复杂度为Θ(n^2)。
2. 随机基准元：这是相对安全的策略，因为基准元的位置是随机的，产生的分割也不会总是会出现劣质的分割。实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。
3. 三数取中：这是最佳的划分方法，将待排序的序列分成等长的子序列，使用序列的中间的值作为基准元。可以通过随机选取三个元素并用它们的中值作为基准元。
三、Partition算法
Partition算法是快速排序的核心算法，思路是先找一个枢纽元，然后从数组的两边生成两个指针left和right，每次发现左边的元素大于枢纽元则停下来，右边的元素小于枢纽元就停下来，并且交换这两个数的位置。直到两个指针left，right相遇。
public int partition(int[] num,int left,int right){
if(num==null || num.length<=0 || left<0 || right>=num.length){
return 0;
}
int prio=num[left+(right-left)/2];
while (left<=right){
//从两端交替向中间扫描
while (num[left]<prio)
left++;
while (num[right]>prio)
right--;
if (left<=right){
swap(num,left,right); //最终将基准数归位
left++;
right--;
}
}
return left;
}
四、排序算法实现
快速排序采用了分治策略，就是在一个数组中取一个基准数字，把小的数放基准的左边，大的数放基准的右边。基准左边和右边分别是新的序列。在新的序列中再取一个基准数字，小的放左边，大的放右边。
使用递归实现快速排序算法，需要三个参数，一个是数组，另外两个是序列的边界。
public class QuickSort{
void sort(int num[],int left,int right){
if (left<right){
int index=partition(num,left,right); //算出枢轴值
sort(num,left,index-1); //对低子表递归排序
sort(num,index+1,right); //对高子表递归排序
}
}
}
快速排序是一种高效的排序算法，通过选择基准元和partition算法，递归地对数组进行排序。
