快速排序算法-个人理解 - 黑马程序员技术交流社区

<span style="font-style: normal;"><span style="font-style: normal;">/**
* 无序区域的划分，找到划分后区域中基准值所在的位置
* @param i 无序区域的最左边下标
* @param j 无序区域最右边下标
* @param pivot 基准值
* @return 划分后基准值所在的位置
*/
private int Partition(int i, int j, int pivot)
{
int l; // 左游标
int r; // 右游标
do{
for(l = i; arr[l] < pivot; l++); // 基准值左侧元素均比其小
for(r = j; arr[r] >= pivot; r--); // 基准值右侧元素均大于等于其
if(l < r)
swap(arr,l,r); // 交换左右两侧不满足大小的值
}while(l <= r); // 当左右游标交叉时，退出
return l; // 返回分界点处位置
}

复制代码

package com.itheima;
/**
* 快速排序法对数组进行排序
* @author Fourier
*/
public class QuickSortDemo {
private int[] arr;
public QuickSortDemo(int[] arr)
{
this.arr = arr;
}
/**
* 基准值的选取。从序列中最先找到两个不同元素中的较大者.
* @param arr 待查找数组
* @param i 待查找数组开始位置
* @param j 待查找数组末尾位置
* @return 两个不同元素中的最大者的下标;如果所有元素值相同，则返回-1
*/
private int FindPivot(int i, int j)
{
int firstValue = arr[i];
int k = 0;
// 从第i+1个元素开始，向右寻找最近的两个不相等的元素，返回较大值的下标
for(k = i+1; k<= j ; k++)
{
if(arr[k] > firstValue)
{
return k;
}else if(arr[k] < firstValue)
return i;
}
// 当序列中所有元素值相同时，返回-1
return -1;
}
/**
* 交换两个元素的值
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return;
}
/**
* 无序区域的划分，找到划分后区域中基准值所在的位置
* @param i 无序区域的最左边下标
* @param j 无序区域最右边下标
* @param pivot 基准值
* @return 划分后基准值所在的位置
*/
private int Partition(int i, int j, int pivot)
{
int l; // 左游标
int r; // 右游标
do{
for(l = i; arr[l] < pivot; l++); // 基准值左侧元素均比其小
for(r = j; arr[r] >= pivot; r--); // 基准值右侧元素均大于等于其
if(l < r)
swap(arr,l,r); // 交换左右两侧不满足大小的值
}while(l <= r); // 当左右游标交叉时，退出
return l; // 返回分界点处位置
}
/**
* 快速排序的递归实现
* @param i 需排序区域最左侧位置
* @param j 需排序区域最右侧位置
*/
public void QuickSort( int i, int j)
{
int pivot; // 存放基准值
int selectIndex; // 选择排序前基准值所在位置
int sortIndex; // 排序后基准值应在位置
selectIndex = FindPivot(i,j);
if(selectIndex != -1)
{
pivot = arr[selectIndex];
//sortIndex = Partition(i,j,pivot);
sortIndex = Partition(selectIndex,j,pivot); // pivotIndex之前的元素在选择时已经排好序
QuickSort(i, sortIndex-1);
QuickSort(sortIndex, j);
}
return;
}
/**
* 显示数组中元素
*/
public void show()
{
System.out.print("[");
for(int i = 0; i < arr.length-1; i++)
{
System.out.print(arr[i]+",");
}
System.out.println(arr[arr.length-1]+"]");
return;
}
public static void main(String[] args) {
int [] arr = {4,4,4,1,7,3,6,9,2,8,6,9,2,3,4,7,2,8};
QuickSortDemo qsd = new QuickSortDemo(arr);
System.out.println("==============快速排序前===============");
qsd.show();
qsd.QuickSort(0, arr.length-1);
System.out.println("==============快速排序后===============");
qsd.show();
return;
}
}

复制代码