快速排序算法本质上是通过把一个数组划分为两个子数组,然后递归的调用自身为每一个子数组进行快速排序来实现的。
这里首先讲递归的快速排序算法。
1.递归的排序算法
public void recQuickSort(int left, int right){
if(right-left<=0){ //如果right-left<=0,表示已经排好序了
return;
}else{
long pivot = theArray[right];
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
}
正如上面的代码,有三个基本步骤:
这个递归的基值(终止)条件:检查数组是否只包含一个数据项,如果是,就定义数组已经有序,方法返回。
那么如何检查数组只包含一个数据项呢?即right - left <= 0;
patitionIt()方法应该使用什么样的枢纽呢?
递归排序算法思想简图
递归排序实际数据效果图
这里贴出递归方式快速排序代码实现
package com.vincent.suanfa;
public class quickSort1 {
public static void main(String[] args){
int maxSize = 16;
ArrayIns arr;
arr = new ArrayIns(maxSize);
//填充数组
for(int j=0; j < maxSize; j++){
long n = (int)(java.lang.Math.random()*99); //生成随机数
arr.insert(n);
}
arr.display();
arr.quickSort();
arr.display();
}
}
class ArrayIns{
private long[] theArray; //数组
private int nElems; //标识数组最大下标(即长度-1)
//构造函数
public ArrayIns(int max){
theArray = new long[max];
nElems = 0;
}
//把数据插入数组
public void insert(long value){
theArray[nElems] = value;
nElems++;
}
//打印数组
public void display(){
System.out.print("A=");
for(int j=0; j<nElems; j++){
System.out.print(theArray[j] + " ");
}
System.out.println("");
}
public void quickSort(){
recQuickSort(0,nElems-1);
}
public void recQuickSort(int left, int right){
if(right-left<=0){ //如果right-left<=0,表示已经排好序了
return;
}else{
long pivot = theArray[right];
int partition = partitionIt(left, right, pivot);
recQuickSort(left, partition-1);
recQuickSort(partition+1, right);
}
}
//分区函数
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left-1;
int rightPtr = right;
while(true)
{
//leftPtr表示数组下标为leftPtr时,其值小于pivot;目的是找到下标大于等于pivot的下标;即分出pivot左边的部分
while( theArray[++leftPtr] < pivot);
//rightPtr表示数组下标为rightPtr时,其值大于pivot;目的是找到下标小于等于pivot的下标;即分出pivot右边的部分
while( rightPtr>0 && theArray[--rightPtr] > pivot);
if(leftPtr >= rightPtr) //表示小于pivot的下标和大于pivot的下标交叉了,分区结束
break;
else
swap(leftPtr, rightPtr); //把数据项按枢纽分成两组
}
swap(leftPtr, right);
System.out.println("分区:");
display();
System.out.println("分区下标: "+leftPtr);
return leftPtr;
}
//交换数据
public void swap(int dex1, int dex2)
{
long temp = theArray[dex1];
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
}