用Java实现几种常见的排序算法.docx
《用Java实现几种常见的排序算法.docx》由会员分享，可在线阅读，更多相关《用Java实现几种常见的排序算法.docx（13页珍藏版）》请在冰点文库上搜索。
用Java实现几种常见的排序算法
用Java实现几种常见的排序算法
2006年03月24日 作者：
treeroot 责任编辑：
xietaoming
用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。
插入排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassInsertSortimplementsSortUtil.Sort{
/*（non-Javadoc）
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
inttemp;
for（inti=1;i for（intj=i;（j>0）&&（data[j] SortUtil.swap（data,j,j-1）;
}
}
}
}
冒泡排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassBubbleSortimplementsSortUtil.Sort{
/*（non-Javadoc）
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
inttemp;
for（inti=0;i for（intj=data.length-1;j>i;j--）{
if（data[j] SortUtil.swap（data,j,j-1）;
}
}
}
}
}
选择排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassSelectionSortimplementsSortUtil.Sort{
/*
*（non-Javadoc）
*
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
inttemp;
for（inti=0;i intlowIndex=i;
for（intj=data.length-1;j>i;j--）{
if（data[j] lowIndex=j;
}
}
SortUtil.swap（data,i,lowIndex）;
}
}
}
Shell排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassShellSortimplementsSortUtil.Sort{
/*（non-Javadoc）
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
for（inti=data.length/2;i>2;i/=2）{
for（intj=0;j insertSort（data,j,i）;
}
}
insertSort（data,0,1）;
}
/**
*@paramdata
*@paramj
*@parami
*/
privatevoidinsertSort（int[]data,intstart,intinc）{
inttemp;
for（inti=start+inc;i for（intj=i;（j>=inc）&&（data[j] SortUtil.swap（data,j,j-inc）;
}
}
}
}
快速排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassQuickSortimplementsSortUtil.Sort{
/*（non-Javadoc）
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
quickSort（data,0,data.length-1）;
}
privatevoidquickSort（int[]data,inti,intj）{
intpivotIndex=（i+j）/2;
//swap
SortUtil.swap（data,pivotIndex,j）;
intk=partition（data,i-1,j,data[j]）;
SortUtil.swap（data,k,j）;
if（（k-i）>1）quickSort（data,i,k-1）;
if（（j-k）>1）quickSort（data,k+1,j）;
}
/**
*@paramdata
*@parami
*@paramj
*@return
*/
privateintpartition（int[]data,intl,intr,intpivot）{
do{
while（data[++l] while（（r!
=0）&&data[--r]>pivot）;
SortUtil.swap（data,l,r）;
}
while（l SortUtil.swap（data,l,r）;
returnl;
}
}
改进后的快速排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassImprovedQuickSortimplementsSortUtil.Sort{
privatestaticintMAX_STACK_SIZE=4096;
privatestaticintTHRESHOLD=10;
/*（non-Javadoc）
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
int[]stack=newint[MAX_STACK_SIZE];
inttop=-1;
intpivot;
intpivotIndex,l,r;
stack[++top]=0;
stack[++top]=data.length-1;
while（top>0）{
intj=stack[top--];
inti=stack[top--];
pivotIndex=（i+j）/2;
pivot=data[pivotIndex];
SortUtil.swap（data,pivotIndex,j）;
//partition
l=i-1;
r=j;
do{
while（data[++l] while（（r!
=0）&&（data[--r]>pivot））;
SortUtil.swap（data,l,r）;
}
while（l SortUtil.swap（data,l,r）;
SortUtil.swap（data,l,j）;
if（（l-i）>THRESHOLD）{
stack[++top]=i;
stack[++top]=l-1;
}
if（（j-l）>THRESHOLD）{
stack[++top]=l+1;
stack[++top]=j;
}
}
//newInsertSort（）.sort（data）;
insertSort（data）;
}
/**
*@paramdata
*/
privatevoidinsertSort（int[]data）{
inttemp;
for（inti=1;i for（intj=i;（j>0）&&（data[j] SortUtil.swap（data,j,j-1）;
}
}
}
}
归并排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassMergeSortimplementsSortUtil.Sort{
/*（non-Javadoc）
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
int[]temp=newint[data.length];
mergeSort（data,temp,0,data.length-1）;
}
privatevoidmergeSort（int[]data,int[]temp,intl,intr）{
intmid=（l+r）/2;
if（l==r）return;
mergeSort（data,temp,l,mid）;
mergeSort（data,temp,mid+1,r）;
for（inti=l;i<=r;i++）{
temp[i]=data[i];
}
inti1=l;
inti2=mid+1;
for（intcur=l;cur<=r;cur++）{
if（i1==mid+1）
data[cur]=temp[i2++];
elseif（i2>r）
data[cur]=temp[i1++];
elseif（temp[i1] data[cur]=temp[i1++];
else
data[cur]=temp[i2++];
}
}
}
改进后的归并排序:
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassImprovedMergeSortimplementsSortUtil.Sort{
privatestaticfinalintTHRESHOLD=10;
/*
*（non-Javadoc）
*
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
int[]temp=newint[data.length];
mergeSort（data,temp,0,data.length-1）;
}
privatevoidmergeSort（int[]data,int[]temp,intl,intr）{
inti,j,k;
intmid=（l+r）/2;
if（l==r）
return;
if（（mid-l）>=THRESHOLD）
mergeSort（data,temp,l,mid）;
else
insertSort（data,l,mid-l+1）;
if（（r-mid）>THRESHOLD）
mergeSort（data,temp,mid+1,r）;
else
insertSort（data,mid+1,r-mid）;
for（i=l;i<=mid;i++）{
temp[i]=data[i];
}
for（j=1;j<=r-mid;j++）{
temp[r-j+1]=data[j+mid];
}
inta=temp[l];
intb=temp[r];
for（i=l,j=r,k=l;k<=r;k++）{
if（a data[k]=temp[i++];
a=temp[i];
}else{
data[k]=temp[j--];
b=temp[j];
}
}
}
/**
*@paramdata
*@paraml
*@parami
*/
privatevoidinsertSort（int[]data,intstart,intlen）{
for（inti=start+1;i for（intj=i;（j>start）&&data[j] SortUtil.swap（data,j,j-1）;
}
}
}
}
堆排序：
packageorg.rut.util.algorithm.support;
importorg.rut.util.algorithm.SortUtil;
/**
*@authortreeroot
*@since2006-2-2
*@version1.0
*/
publicclassHeapSortimplementsSortUtil.Sort{
/*（non-Javadoc）
*@seeorg.rut.util.algorithm.SortUtil.Sort#sort（int[]）
*/
publicvoidsort（int[]data）{
MaxHeaph=newMaxHeap（）;
h.init（data）;
for（inti=0;i h.remove（）;
System.arraycopy（h.queue,1,data,0,data.length）;
}
privatestaticclassMaxHeap{
voidinit（int[]data）{
this.queue=newint[data.length+1];
for（inti=0;i queue[++size]=data[i];
fixUp（size）;
}
}
privateintsize=0;
privateint[]queue;
publicintget（）{
returnqueue[1];
}
publicvoidremove（）{
SortUtil.swap（queue,1,size--）;
fixDown
（1）;
}
//fixdown
privatevoidfixDown（intk）{
intj;
while（（j=k<<1）<=size）{
if（j
升级会员 