用Java实现几种常见的排序算法Word文件下载.docx

用Java实现几种常见的排序算法Word文件下载.docx

《用Java实现几种常见的排序算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《用Java实现几种常见的排序算法Word文件下载.docx（13页珍藏版）》请在冰点文库上搜索。

data.length;

i++）{

for（intj=i;

（j>

0）&

&

（data[j]<

data[j-1]）;

j--）{

SortUtil.swap（data,j,j-1）;

}

} 

}

冒泡排序：

publicclassBubbleSortimplementsSortUtil.Sort{

for（inti=0;

for（intj=data.length-1;

j>

i;

if（data[j]<

data[j-1]）{

选择排序：

publicclassSelectionSortimplementsSortUtil.Sort{

/*

*（non-Javadoc）

* 

for（inti=0;

i<

data.length;

i++）{

intlowIndex=i;

for（intj=data.length-1;

j>

i;

j--）{

if（data[j]<

data[lowIndex]）{

lowIndex=j;

SortUtil.swap（data,i,lowIndex）;

Shell排序：

publicclassShellSortimplementsSortUtil.Sort{

for（inti=data.length/2;

i>

2;

i/=2）{

for（intj=0;

j<

j++）{

insertSort（data,j,i）;

insertSort（data,0,1）;

/**

*@paramdata

*@paramj

*@parami

privatevoidinsertSort（int[]data,intstart,intinc）{

for（inti=start+inc;

i+=inc）{

=inc）&

data[j-inc]）;

j-=inc）{

SortUtil.swap（data,j,j-inc）;

快速排序：

publicclassQuickSortimplementsSortUtil.Sort{

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）;

*@return

privateintpartition（int[]data,intl,intr,intpivot）{

do{

while（data[++l]<

pivot）;

while（（r!

=0）&

data[--r]>

SortUtil.swap（data,l,r）;

while（l<

r）;

returnl;

改进后的快速排序：

publicclassImprovedQuickSortimplementsSortUtil.Sort{

privatestaticintMAX_STACK_SIZE=4096;

privatestaticintTHRESHOLD=10;

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];

//partition

l=i-1;

r=j;

（data[--r]>

pivot））;

SortUtil.swap（data,l,j）;

if（（l-i）>

THRESHOLD）{

stack[++top]=i;

stack[++top]=l-1;

if（（j-l）>

stack[++top]=l+1;

stack[++top]=j;

//newInsertSort（）.sort（data）;

insertSort（data）;

privatevoidinsertSort（int[]data）{

归并排序：

publicclassMergeSortimplementsSortUtil.Sort{

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;

=r;

temp[i]=data[i];

inti1=l;

inti2=mid+1;

for（intcur=l;

cur<

cur++）{

if（i1==mid+1）

data[cur]=temp[i2++];

elseif（i2>

r）

data[cur]=temp[i1++];

elseif（temp[i1]<

temp[i2]）

else

改进后的归并排序:

publicclassImprovedMergeSortimplementsSortUtil.Sort{

privatestaticfinalintTHRESHOLD=10;

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）;

insertSort（data,l,mid-l+1）;

if（（r-mid）>

THRESHOLD）

mergeSort（data,temp,mid+1,r）;

insertSort（data,mid+1,r-mid）;

for（i=l;

=mid;

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<

b）{

data[k]=temp[i++];

a=temp[i];

}else{

data[k]=temp[j--];

b=temp[j];

*@paraml

privatevoidinsertSort（int[]data,intstart,intlen）{

for（inti=start+1;

start+len;

start）&

data[j]<

data[j-1];

堆排序：

publicclassHeapSortimplementsSortUtil.Sort{

MaxHeaph=newMaxHeap（）;

h.init（data）;

i++）

h.remove（）;

System.arraycopy（h.queue,1,data,0,data.length）;

privatestaticclassMaxHeap{ 

voidinit（int[]data）{

this.queue=newint[data.length+1];

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<

size&

queue[j]<

queue