java七大排序——6_快速排序-创新互联

一、快速排序：

在待排元素中找出一个基准元素,然后比较基准元素和其他元素，以基准元素为基准，将大于准的元素的放后边，小于
基准的元素放前边。然后再对分好的左右两个小区间进行快速排序
以基准元素划分区间的方式有以下2种：
第一种：设两个参考变量less,great，less先从第一个元素开始往后遍历，直到找到的当前元素大于基准元素。
然后让great从最后一个元素开始往前遍历，直到找到当前元素小于基准元素，交换当前less和great指向的值。
再接着从less开始，重复上述动作，遍历结束的条件是less>=great;
遍历结束后，交换当前less(或great)指向的值与基准元素的值。再进行下一次的小区间内的查找

成都创新互联公司网站建设公司一直秉承“诚信做人，踏实做事”的原则，不欺瞒客户，是我们最起码的底线！ 以服务为基础，以质量求生存，以技术求发展，成交一个客户多一个朋友！专注中小微企业官网定制，成都做网站、成都网站设计、成都外贸网站建设，塑造企业网络形象打造互联网企业效应。

二、图示

注意：新划分的两个区间的范围是：
第一段：原本的left到上一轮基准元素最终位置的前一位；即[left,pivotIndex-1]
第二段：上一轮基准元素最终位置的后一位到原本的right;即[pivotIndex+1,right]
最终结果:

三、代码实现

public static void quickSort ( int[] array){
int left = 0;
int right = array.length - 1;
quickSortInternal1(array, left, right);
}
public static void quickSortInternal ( int[] array, int left, int right){
if (left >= right) {
return;
}
int pivotIndex = partion1(array, left, right);//找基准值的函数
// int[] indice=partion4(array,left,right);
// quickSortInternal(array,left,indice[0]-1);
// quickSortInternal(array,indice[1]+1,right);
quickSortInternal(array, left, pivotIndex - 1);//注意区间范围
quickSortInternal(array, pivotIndex + 1, right);

}
private static int partion1 ( int[] array, int left, int right){
int pivot = array[right];
int less = left;
int great = right;
while (less < great) {
while (less < great && array[less] <= pivot) {
less++;
}
while (less < great && array[great] >= pivot) {
great--;
}
swap(array, less, great);
}
swap(array, less, right);
return less;
}

第二种：挖坑法
找到基准元素pivot,设两个变量less和great,less从第一个数开始向后遍历,直到找到大于pivot的数，停下，将array[less]的值放到array[great]处。（即array[great]=array[less]）
然后让right从当前区间最后一个数开始往前遍历，直到找到小于pivot的数，停下，进行array[less]=array[great]的操作。再接着less++向后遍历，重复以上操作，结束条件为left>=right;
结束后将pivot的值赋给当前less(great)的数组元素
图示：





注意：pivot基准元素可以任意选，但这里为了讲述方便，每次选择区间的最后一个元素
最终结果

代码实现

private static int partion1 ( int[] array, int left, int right){
int pivot = array[right];//基准值
int less = left;
int great = right;
while (less < great) {
while (less < great && array[less] <= pivot) {
less++;
}
array[great] = array[less];
while (less < great && array[great] >= pivot) {
great--;
}
array[less] = array[great];
}
array[less] = pivot;
return less;
}

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

网页名称：java七大排序——6_快速排序-创新互联
文章链接：http://bzwzjz.com/article/ieipp.html