Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)
本文实例汇总了Java各种排序算法。分享给大家供大家参考，具体如下：
1.冒泡排序：
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
show(a);
bubbleSort(a);
show(a);
}
privatestaticvoidbubbleSort(int[]a){
for(inti=0;i<a.length-1;i++){
for(intj=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
inttmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
2.快速排序(无重复值)：
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,3,12,23,110};
show(a);
quickSort(a,0,a.length-1);
show(a);
}
privatestaticvoidquickSort(int[]a,intstart,intend){
if(start>=end)
return;
inti=start;
intj=end;
intindex=start;
while(i<j){
while(a[j]>a[index]){
j--;
}
index=swap(a,j,index);
while(a[index]>a[i]){
i++;
}
index=swap(a,i,index);
}
quickSort(a,start,index-1);
quickSort(a,index+1,end);
}
privatestaticintswap(int[]a,intn,intindex){
inttmp=a[n];
a[n]=a[index];
a[index]=tmp;
returnn;
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
3.快速排序（可含重复值）
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,345};
show(a);
quickSort2(a,0,a.length-1);
show(a);
}
privatestaticvoidquickSort2(int[]a,intstart,intend){
if(start>=end)
return;
inti=start;
intj=end;
intindex=end;
while(i<j){
while(a[j]>a[index]){
j--;
}
if(j!=index&&a[j]==a[index]){
index=swap(a,--j,index);
}else{
index=swap(a,j,index);
}
while(a[index]>a[i]){
i++;
}
if(i!=index&&a[i]==a[index]){
index=swap(a,++i,index);
}else{
index=swap(a,i,index);
}
}
quickSort2(a,start,index-1);
quickSort2(a,index+1,end);
}
privatestaticintswap(int[]a,intn,intindex){
inttmp=a[n];
a[n]=a[index];
a[index]=tmp;
returnn;
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
4.堆排序
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345};
show(a);
heapSort(a);
show(a);
}
privatestaticvoidheapSort(int[]a){
//建立最大堆
intsize=a.length;
for(inti=size/2-1;i>=0;i--){
createBigHeap(a,i,size-1);
}
//排序
for(intj=0;j<size-1;j++){
inttmp=a[0];
a[0]=a[size-1-j];
a[size-1-j]=tmp;
createBigHeap(a,0,size-2-j);
}
}
privatestaticvoidcreateBigHeap(int[]a,intstart,intend){
inttmp=a[start];
intj=2*start+1;
while(j<=end){
if(j<end&&a[j]<a[j+1]){
j++;
}
if(a[j]>tmp){
a[start]=a[j];
start=j;
j=2*j+1;
}else{
break;
}
}
a[start]=tmp;
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
5.插入排序
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,-1,3};
show(a);
insertSort(a);
show(a);
}
privatestaticvoidinsertSort(int[]a){
for(inti=0;i<a.length-1;i++){
intn=i+1;
inttmp=a[n];
for(intj=i;j>=0;j--){
if(tmp<a[j]){
a[n]=a[j];
n=j;
}
}
if(a[n]!=tmp)
a[n]=tmp;
}
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
6.折半插入排序
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,7,345,2,2,7,2,7,23,2,345,7,32,5,4,-1,3,7,2,3,2,3,4,2,1,2,4,5,3,345,3,2};
show(a);
insertSort2(a);
show(a);
}
privatestaticvoidinsertSort2(int[]a){
for(inti=0;i<a.length-1;i++){
intn=i+1;
inttmp=a[n];
if(tmp>a[i])
continue;
intlow=0;
inthigh=i;
intmid=(high+low)/2;
while(high>=low){
mid=(high+low)/2;
if(tmp<a[mid]){
high=mid-1;
}elseif(tmp>a[mid]){
low=mid+1;
}else{
low=mid;
break;
}
}
for(intj=n;j>mid;j--){
a[j]=a[j-1];
}
a[low]=tmp;
}
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
7.希尔排序
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,-1,3,2,3,5,7,8,90,1};
show(a);
shellSort(a);
show(a);
}
privatestaticvoidshellSort(int[]a){
shellSort(a,a.length);
}
privatestaticvoidshellSort(int[]a,intn){
inti,j,k,temp,gap;
int[]gaps={1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647};
for(k=0;gaps[k]<n;k++);
while(--k>=0){
gap=gaps[k];
for(i=gap;i<n;i++){
temp=a[i];
j=i;
while(j>=gap&&a[j-gap]>temp){
a[j]=a[j-gap];
j=j-gap;
}
a[j]=temp;
}
}
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
8.选择排序
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,-1};
show(a);
selectSort(a);
show(a);
}
privatestaticvoidselectSort(int[]a){
for(inti=0;i<a.length-1;i++){
intmin=i;
for(intj=i+1;j<a.length;j++){
if(a[j]<a[min])
min=j;
}
if(min!=i){
inttmp=a[i];
a[i]=a[min];
a[min]=tmp;
}
}
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
9.归并排序
publicclassSortTest{
publicstaticvoidmain(String[]args){
int[]a={345,7,32,5,4,-1,3,2,3,5,7,8,90,1,432,1};
show(a);
mergeSort(a);
show(a);
}
privatestaticvoidmergeSort(int[]a){
//找出中间值
intmid=a.length/2;
//申请空间存储中间索引以左的值
int[]left=setValue(a,0,mid);
if(left.length>1){//继续拆分左边，直到元素值为1个
mergeSort(left);
}
//申请空间存储中间索引以右的值
int[]right=setValue(a,mid,a.length);
if(right.length>1){//继续拆分右边，直到元素值为1个
mergeSort(right);
}
//将左右值合并
merge(a,left,right);
}
privatestaticvoidmerge(int[]a,int[]left,int[]right){
inti=0,j=0,k=0;
for(;i<left.length&&j<right.length;){
if(left[i]<right[j]){
a[k++]=left[i++];
}else{
a[k++]=right[j++];
}
}
for(;i<left.length;i++){
a[k++]=left[i];
}
for(;j<right.length;j++){
a[k++]=right[j];
}
}
privatestaticint[]setValue(int[]a,intstart,intlength){
int[]x=newint[length-start];
for(inti=0;i<x.length;i++){
x[i]=a[start++];
}
returnx;
}
privatestaticvoidshow(int[]a){
System.out.println(Arrays.toString(a));
}
}
汇总：
publicclassSortUtil{
publicfinalstaticintDESC=-1;
publicfinalstaticintASC=1;
/**
*冒泡排序
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidbubbleSort(int[]a,intsort){
if(sort==ASC)
bubbleSortAsc(a);
else
bubbleSortDesc(a);
}
publicstaticvoidbubbleSortAsc(int[]a){
for(inti=0;i<a.length-1;i++){
for(intj=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
inttmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}
publicstaticvoidbubbleSortDesc(int[]a){
for(inti=0;i<a.length-1;i++){
for(intj=0;j<a.length-i-1;j++){
if(a[j]<a[j+1]){
inttmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
}
}
}
}
//----------------华-丽-的-功-能-分割-线-----------------------
/**
*快速排序（不允许有重复值）
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidquickNoRepeatSort(int[]a,intsort){
if(sort==ASC)
quickNoRepeatSortAsc(a,0,a.length-1);
else
quickNoRepeatSortDesc(a,0,a.length-1);
}
privatestaticvoidquickNoRepeatSortAsc(int[]a,intstart,intend){
if(start>=end)
return;
inti=start;
intj=end;
intindex=start;
while(i<j){
while(a[j]>a[index]){
j--;
}
index=swap(a,j,index);
while(a[index]>a[i]){
i++;
}
index=swap(a,i,index);
}
quickNoRepeatSortAsc(a,start,index-1);
quickNoRepeatSortAsc(a,index+1,end);
}
privatestaticvoidquickNoRepeatSortDesc(int[]a,intstart,intend){
if(start>=end)
return;
inti=start;
intj=end;
intindex=start;
while(i<j){
while(a[j]<a[index]){
j--;
}
index=swap(a,j,index);
while(a[index]<a[i]){
i++;
}
index=swap(a,i,index);
}
quickNoRepeatSortDesc(a,start,index-1);
quickNoRepeatSortDesc(a,index+1,end);
}
/**
*快速排序（允许有重复值）
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidquickSort(int[]a,intsort){
if(sort==ASC)
quickSortAsc(a,0,a.length-1);
else
quickSortDesc(a,0,a.length-1);
}
privatestaticvoidquickSortAsc(int[]a,intstart,intend){
if(start>=end)
return;
inti=start;
intj=end;
intindex=end;
while(i<j){
while(a[j]>a[index]){
j--;
}
if(j!=index&&a[j]==a[index]){
index=swap(a,--j,index);
}else{
index=swap(a,j,index);
}
while(a[index]>a[i]){
i++;
}
if(i!=index&&a[i]==a[index]){
index=swap(a,++i,index);
}else{
index=swap(a,i,index);
}
}
quickSortAsc(a,start,index-1);
quickSortAsc(a,index+1,end);
}
privatestaticvoidquickSortDesc(int[]a,intstart,intend){
if(start>=end)
return;
inti=start;
intj=end;
intindex=end;
while(i<j){
while(a[j]<a[index]){
j--;
}
if(j!=index&&a[j]==a[index]){
index=swap(a,--j,index);
}else{
index=swap(a,j,index);
}
while(a[index]<a[i]){
i++;
}
if(i!=index&&a[i]==a[index]){
index=swap(a,++i,index);
}else{
index=swap(a,i,index);
}
}
quickSortDesc(a,start,index-1);
quickSortDesc(a,index+1,end);
}
privatestaticintswap(int[]a,intn,intindex){
inttmp=a[n];
a[n]=a[index];
a[index]=tmp;
returnn;
}
//----------------华-丽-的-功-能-分割-线------------------
/**
*堆排序
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidheapSort(int[]a,intsort){
if(sort==ASC)
heapSortAsc(a);
else
heapSortDesc(a);
}
publicstaticvoidheapSortAsc(int[]a){
//建立最大堆
intsize=a.length;
for(inti=size/2-1;i>=0;i--){
createBigHeap(a,i,size-1);
}
//排序
for(intj=0;j<size-1;j++){
inttmp=a[0];
a[0]=a[size-1-j];
a[size-1-j]=tmp;
createBigHeap(a,0,size-2-j);
}
}
privatestaticvoidcreateBigHeap(int[]a,intstart,intend){
inttmp=a[start];
intj=2*start+1;
while(j<=end){
if(j<end&&a[j]<a[j+1]){
j++;
}
if(a[j]>tmp){
a[start]=a[j];
start=j;
j=2*j+1;
}else{
break;
}
}
a[start]=tmp;
}
publicstaticvoidheapSortDesc(int[]a){
//建立最小堆
intsize=a.length;
for(inti=size/2-1;i>=0;i--){
createSmallHeap(a,i,size-1);
}
//排序
for(intj=0;j<size-1;j++){
inttmp=a[0];
a[0]=a[size-1-j];
a[size-1-j]=tmp;
createSmallHeap(a,0,size-2-j);
}
}
privatestaticvoidcreateSmallHeap(int[]a,intstart,intend){
inttmp=a[start];
intj=2*start+1;
while(j<=end){
if(j<end&&a[j]>a[j+1]){
j++;
}
if(a[j]<tmp){
a[start]=a[j];
start=j;
j=2*j+1;
}else{
break;
}
}
a[start]=tmp;
}
//----------------华-丽-的-功-能-分割-线---------------------
/**
*插入排序
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidinsertSort(int[]a,intsort){
if(sort==ASC){
insertSortAsc(a);
}else{
insertSortDesc(a);
}
}
publicstaticvoidinsertSortAsc(int[]a){
for(inti=0;i<a.length-1;i++){
intn=i+1;
inttmp=a[n];
for(intj=i;j>=0;j--){
if(tmp<a[j]){
a[n]=a[j];
n=j;
}
}
if(a[n]!=tmp)
a[n]=tmp;
}
}
publicstaticvoidinsertSortDesc(int[]a){
for(inti=0;i<a.length-1;i++){
intn=i+1;
inttmp=a[n];
for(intj=i;j>=0;j--){
if(tmp>a[j]){
a[n]=a[j];
n=j;
}
}
if(a[n]!=tmp)
a[n]=tmp;
}
}
//----------------华-丽-的-功-能-分割-线--------------------
/**
*折半插入排序
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidhalfInsertSort(int[]a,intsort){
if(sort==ASC){
halfInsertSortAsc(a);
}else{
halfInsertSortDesc(a);
}
}
publicstaticvoidhalfInsertSortAsc(int[]a){
for(inti=0;i<a.length-1;i++){
intn=i+1;
inttmp=a[n];
if(tmp>a[i])
continue;
intlow=0;
inthigh=i;
intmid=(high+low)/2;
while(high>=low){
mid=(high+low)/2;
if(tmp<a[mid]){
high=mid-1;
}elseif(tmp>a[mid]){
low=mid+1;
}else{
low=mid;
break;
}
}
for(intj=n;j>mid;j--){
a[j]=a[j-1];
}
a[low]=tmp;
}
}
publicstaticvoidhalfInsertSortDesc(int[]a){
for(inti=0;i<a.length-1;i++){
intn=i+1;
inttmp=a[n];
if(tmp<a[i])
continue;
intlow=0;
inthigh=i;
intmid=(high+low)/2;
while(high>=low){
mid=(high+low)/2;
if(tmp>a[mid]){
high=mid-1;
}elseif(tmp<a[mid]){
low=mid+1;
}else{
low=mid;
break;
}
}
for(intj=n;j>mid;j--){
a[j]=a[j-1];
}
a[low]=tmp;
}
}
//----------------华-丽-的-功-能-分割-线----------------------
/**
*希尔排序
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidshellSort(int[]a,intsort){
if(sort==ASC){
shellSortAsc(a,a.length);
}else{
shellSortDesc(a,a.length);
}
}
publicstaticvoidshellSortAsc(int[]a,intn){
inti,j,k,temp,gap;
int[]gaps={1,5,13,43,113,297,815,1989,4711,11969,27901,
84801,213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647};
for(k=0;gaps[k]<n;k++)
;
while(--k>=0){
gap=gaps[k];
for(i=gap;i<n;i++){
temp=a[i];
j=i;
while(j>=gap&&a[j-gap]>temp){
a[j]=a[j-gap];
j=j-gap;
}
a[j]=temp;
}
}
}
publicstaticvoidshellSortDesc(int[]a,intn){
inti,j,k,temp,gap;
int[]gaps={1,5,13,43,113,297,815,1989,4711,11969,27901,
84801,213331,543749,1355339,3501671,8810089,21521774,
58548857,157840433,410151271,1131376761,2147483647};
for(k=0;gaps[k]<n;k++)
;
while(--k>=0){
gap=gaps[k];
for(i=gap;i<n;i++){
temp=a[i];
j=i;
while(j>=gap&&a[j-gap]<temp){
a[j]=a[j-gap];
j=j-gap;
}
a[j]=temp;
}
}
}
//----------------华-丽-的-功-能-分割-线---------------------
/**
*选择排序
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidselectSort(int[]a,intsort){
if(sort==ASC){
selectSortAsc(a);
}else{
selectSortDesc(a);
}
}
publicstaticvoidselectSortAsc(int[]a){
for(inti=0;i<a.length-1;i++){
intmin=i;
for(intj=i+1;j<a.length;j++){
if(a[j]<a[min])
min=j;
}
if(min!=i){
inttmp=a[i];
a[i]=a[min];
a[min]=tmp;
}
}
}
publicstaticvoidselectSortDesc(int[]a){
for(inti=0;i<a.length-1;i++){
intmax=i;
for(intj=i+1;j<a.length;j++){
if(a[j]>a[max])
max=j;
}
if(max!=i){
inttmp=a[i];
a[i]=a[max];
a[max]=tmp;
}
}
}
//----------------华-丽-的-功-能-分割-线---------------------
/**
*归并排序
*
*@paramasortArray
*@paramsortSortUtil.ASC,SortUtil.DESC
*/
publicstaticvoidmergeSort(int[]a,intsort){
//找出中间值
intmid=a.length/2;
//申请空间存储中间索引以左的值
int[]left=setValue(a,0,mid);
if(left.length>1){//继续拆分左边，直到元素值为1个
mergeSort(left,sort);
}
//申请空间存储中间索引以右的值
int[]right=setValue(a,mid,a.length);
if(right.length>1){//继续拆分右边，直到元素值为1个
mergeSort(right,sort);
}
if(sort==ASC){
mergeAsc(a,left,right);
}else{
mergeDesc(a,left,right);
}
}
privatestaticvoidmergeAsc(int[]a,int[]left,int[]right){
inti=0,j=0,k=0;
for(;i<left.length&&j<right.length;){
if(left[i]<right[j]){
a[k++]=left[i++];
}else{
a[k++]=right[j++];
}
}
for(;i<left.length;i++){
a[k++]=left[i];
}
for(;j<right.length;j++){
a[k++]=right[j];
}
}
privatestaticvoidmergeDesc(int[]a,int[]left,int[]right){
inti=0,j=0,k=0;
for(;i<left.length&&j<right.length;){
if(left[i]>right[j]){
a[k++]=left[i++];
}else{
a[k++]=right[j++];
}
}
for(;i<left.length;i++){
a[k++]=left[i];
}
for(;j<right.length;j++){
a[k++]=right[j];
}
}
privatestaticint[]setValue(int[]a,intstart,intlength){
int[]x=newint[length-start];
for(inti=0;i<x.length;i++){
x[i]=a[start++];
}
returnx;
}
}
希望本文所述对大家Java程序设计有所帮助。