5种java排序算法汇总工具类
工具类简单明了地总结了java的快速排序，希尔排序，插入排序，堆排序，归并排序五种排序算法，代码中并没有对这几种排序算法的一个说明，关于思想部分希望在自行查阅相关说明，这里只是对这几种算法进行一个概括，以供大家使用。
publicclassSort{
publicstatic<AnyTypeextendsComparable<?superAnyType>>voidinsertionSort(AnyType[]a){
insertionSort(a,0,a.length-1);
}
privatestatic<AnyTypeextendsComparable<?superAnyType>>voidinsertionSort(AnyType[]a,intleft,intright){
intj;//记录第一个比tmp小的元素的后边一位的位置
for(intp=left;p<=right;p++){
AnyTypetmp=a[p];
for(j=p;j>left&&tmp.compareTo(a[j-1])<0;j--){
a[j]=a[j-1];
}
a[j]=tmp;
}
}
publicstatic<AnyTypeextendsComparable<?superAnyType>>voidshellSort(AnyType[]arr){
intj;
for(intgap=arr.length/2;gap>0;gap/=2){
for(inti=gap;i<arr.length;i++){
AnyTypetmp=arr[i];
for(j=i;j>=gap&&tmp.compareTo(arr[j-gap])<0;j-=gap){
arr[j]=arr[j-gap];
}
arr[j]=tmp;
}
}
}
privatestaticintleftChild(inti){
returni*2+1;
}
privatestatic<AnyTypeextendsComparable<?superAnyType>>voidperculateDown(AnyType[]arr,inti,intsize){
AnyTypetmp=arr[i];
for(intchild;(child=leftChild(i))<size;i=child){
if(child!=size-1&&arr[child].compareTo(arr[child+1])<0){
child++;
}
if(tmp.compareTo(arr[child])<0){
arr[i]=arr[child];
}else{
break;
}
}
arr[i]=tmp;
}
publicstatic<AnyTypeextendsComparable<?superAnyType>>voidheapSort(AnyType[]arr){
for(inti=arr.length/2;i>=0;i--){
perculateDown(arr,i,arr.length);
}
for(inti=arr.length-1;i>=0;i--){
swapReferences(arr,0,i);
perculateDown(arr,0,i);
}
}
privatestatic<AnyTypeextendsComparable<?superAnyType>>voidswapReferences(AnyType[]arr,inti,intj){
AnyTypetmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
publicstatic<AnyTypeextendsComparable<?superAnyType>>voidmergeSort(AnyType[]arr){
AnyType[]tmp=((AnyType[])newComparable[arr.length]);
mergeSort(arr,0,arr.length-1,tmp);
}
privatestatic<AnyTypeextendsComparable<?superAnyType>>voidmergeSort(AnyType[]arr,intstart,intend,AnyType[]tmp){
if(start<end){
intmid=(start+end)>>1;
mergeSort(arr,start,mid,tmp);
mergeSort(arr,mid+1,end,tmp);
merge(arr,start,mid,end,tmp);
}
}
privatestatic<AnyTypeextendsComparable<?superAnyType>>voidmerge(AnyType[]arr,intstart,intmid,intend,AnyType[]tmp){
inti=start,j=mid+1,k=start;
while(i<=mid&&j<=end){
if(arr[i].compareTo(arr[j])<0){
tmp[k++]=arr[i++];
}else{
tmp[k++]=arr[j++];
}
}
while(i<=mid){
tmp[k++]=arr[i++];
}
while(j<=end){
tmp[k++]=arr[j++];
}
for(intm=start;m<=end;m++){
arr[m]=tmp[m];
}
}
publicstatic<AnyTypeextendsComparable<?superAnyType>>voidquickSort(AnyType[]arr){
quickSort(arr,0,arr.length-1);
}
privatestatic<AnyTypeextendsComparable<?superAnyType>>voidquickSort(AnyType[]arr,intleft,intright){
if(left+LENGTH_DIFF<=right){
AnyTypepivot=medium(arr,left,right);
inti=left,j=right;
while(true){
while(arr[++i].compareTo(pivot)<0);
while(arr[--j].compareTo(pivot)>0);
if(i<j){
swapReferences(arr,i,j);
}else{
break;
}
}
swapReferences(arr,i,right);
quickSort(arr,left,i-1);
quickSort(arr,i+1,right);
}else{
insertionSort(arr,left,right);
}
}
privatestatic<AnyTypeextendsComparable<?superAnyType>>AnyTypemedium(AnyType[]arr,intleft,
intright){
intcenter=(left+right)/2;
if(arr[center].compareTo(arr[left])<0){
swapReferences(arr,center,left);
}
if(arr[left].compareTo(arr[right])>0){
swapReferences(arr,left,right);
}
if(arr[center].compareTo(arr[right])<0){
swapReferences(arr,center,right);
}
returnarr[right];
}
privatefinalstaticintLENGTH_DIFF=20;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。