排序算法的JAVA实现.docx
《排序算法的JAVA实现.docx》由会员分享，可在线阅读，更多相关《排序算法的JAVA实现.docx（16页珍藏版）》请在冰点文库上搜索。
排序算法的JAVA实现
packagesort;
/**
*排序算法的的种类：
1.冒泡排序2.选择排序3.插入排序4.快速排序5.归并排序6.基数排序7.希尔排序8.堆排序
*
*@author海浪之心
*
*/
publicclassMySort{
/**
*希尔排序：
是插入排序的一种，也称缩小增量排序
*/
publicvoidmyShellSort（）{
}
/**
*冒泡排序：
算法原理：
比较相信的元素，如果第一个比第二个大，就交换，每一轮之后就比较出最大的一个元素并放置到最后。
*算法分析：
最好的时间复杂度是O（n）
*
*@parama
*/
publicstaticint[]bubbleSort（int[]array）{
inttemp;
for（inti=array.length-1;i>0;i--）{
for（intj=0;jif（array[j]>array[j+1]）{
swap（array,j,j+1）;
}
}
}
returnarray;
}
/**
*选择排序：
对比数组中前一个元素跟后面元素的大小，如果后面的元素比前面的元素小则用一个变量min来记住他的位置
*第一轮选出最小的值放在第一位置，第二轮选出次小的放置在第二位置，依此类推
*
*@paramarray
*@return
*/
publicstaticvoidselectSort（int[]array）{
inttemp=0;
intmin=0;
for（inti=0;imin=i;
for（intj=i+1;jif（array[j]min=j;
}
}
if（i!
=min）{
swap（array,i,min）;
}
}
//returnarray;
}
/**
*插入排序：
在一个已经有序的数据序列，要求在这个已经排序好的数据序列中插入一个数。
但要求插入后此数据序列仍然有序。
*基本思想：
每一步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，走到全部插入完。
分类：
直接插入，链表插入，希尔排序。
*分类：
直接插入排序，链表插入排序，十分法插入排序（折半插入排序），希尔排序（又称缩小增量排序）种类：
稳定排序。
*
*
*/
/**
*直接插入排序：
每次从无序表中取出第一个元素，把它插入有序中的合适位置，使有序表仍然有序。
*插入排序羽毛球稳定性排序，最坏时间复杂度为O（n^2），空间复杂度为O
（1）
*
*@paramarray
*/
publicstaticvoidstraightInsertSort（int[]array）{
for（inti=1;iinttemp;//设置中间值记录最小值
intj=0;//用于数组元素热平衡的下标
if（array[i]temp=array[i];//保存array[i]的值
for（j=i-1;j>=0&&temparray[j+1]=array[j];
}
array[j+1]=temp;
}
}
}
/**
*折半插入排序是直接插入排序的一个变种，也算是一种改进。
由于排序算法超额过程中，就是不断的仿效将元素插入前面已经排好的序列中。
*
*@paramarray
*/
publicstaticvoidbinaryInsertSort（int[]array）{
for（inti=0;iinttemp=array[i];
intlow=0;
inthig=i-1;
while（low<=hig）{
intmid=（low+hig）/2;
if（temphig=mid-1;
}else{
low=mid+1;
}
}
for（intj=i-1;j>hig;j--）{
array[j+1]=array[j];
}
array[hig+1]=temp;
}
}
/**
*快速排序
（一）：
基本思想：
第一趟排序将数据分割成左右两部分，并保证左侧的数据都比右侧的小，然后再按此方法对两部分数据进行排序，可以用递归的思想。
*
*@paramarray
*@return
*/
publicstaticint[]quickSort0（int[]array）{
intli=0;//左侧的索引leftIndex
intri=array.length-1;//右侧的索引RightIndex
if（liintleftValue=array[li];
inti=li;
intj=ri+1;
while（true）{
//向右查找
while（i+1;
}
}
returnarray;
}
/**
*快速排序：
使用递归
*
*@paramarr
*@paramlow
*@paramhigh
*/
publicstaticvoidquickSort（int[]arr,intlow,inthigh）{
intl=low;
inth=high;
intvalue=arr[low];
while（lwhile（l=value）{
h--;
}
if（lswap（arr,h,l++）;
}
while（ll++;
}
if（lswap（arr,h--,l）;
}
}
if（l>low）{
quickSort（arr,low,l-1）;
}
if（hquickSort（arr,l+1,high）;
}
}
/**
*快速排序
（一）使用递归,左边元素设为轴
*
*@paramarray
*@paramleft
*@paramright
*/
privatestaticvoidquickSort1（int[]array,intleft,intright）{
if（leftintvalue=array[left];
intl=left;
intr=right+1;
while（true）{
//向右找
while（l+1;
//向左找
while（r-1>-1&&array[--r]>value）
;
if（l>=r）
break;
swap（array,l,r）;
}
array[left]=array[r];
array[r]=value;
quickSort1（array,left,r-1）;
//对左边进行递回
quickSort1（array,r+1,right）;
//对右边进行递回
}
}
/**
*快速排序
（二）使用递归,中间元素设为轴
*
*@paramarr
*轴心元素
*@paramleft
*左遍历
*@paramright
*右遍历
*/
publicstaticvoidquickSort2（int[]arr,intleft,intright）{
if（leftintvalue=arr[（left+right）/2];//将中间元素设置为轴
intl=left-1;
intr=right+1;
while（true）{
while（arr[++l];
while（arr[--r]>value）
;
if（l>=r）{
break;
}
swap（arr,l,r）;
}
quickSort2（arr,left,l-1）;
quickSort2（arr,r+1,right）;
}
}
/**
*基数排序：
也称桶排序
*
*@paramarr
*要排序的数组
*@paramd
*表示最大的数有多少位,如排序的数都是个位数，d=1,如果最大的为十位，（70），d=2
*/
publicstaticvoidradixSort（int[]arr）{
intk=0;
intn=1;
intm=1;
intd=10;//表示最大的数有多少位,如排序的数都是个位数，d=1,如果最大的为十位，（70），d=2。
。
。
。
。
。
。
。
。
。
。
d=10,表示10亿以内的数都可能参与排序了，我个人觉得已经够大了
int[][]temp=newint[10][arr.length];//数组的第一维表示可能存在的余数0～9
int[]order=newint[10];//数组order[i]用来表示该位是i的数的个数
while（m<=d）{
for（inti=0;iintlsd=（（arr[i]/n）%10）;
temp[lsd][order[lsd]]=arr[i];
order[lsd]++;
}
for（inti=0;i<10;i++）{
if（order[i]!
=0）{
for（intj=0;jarr[k]=temp[i][j];
k++;
}
}
order[i]=0;
}
n*=10;
k=0;
m++;
}
}
/**
*堆排序：
*
*@paramarray
*@return
*/
publicstaticint[]heapSort（int[]array）{
for（inti=（int）Math.floor（（array.length-1）/2）;i>0;i--）{
heapAdjust（array,i,array.length-1）;
}
for（inti=array.length-1;i>=1;i--）{
swap（array,1,i）;
heapAdjust（array,1,i-1）;
}
returnarray;
}
/**
*建堆方法
*
*@paramarray
*@params
*@paramm
*/
publicstaticvoidheapAdjust（int[]array,ints,intm）{
/*
*array[0]=array[s];//用0下标作为暂存单元for（intj=2*s;j<=m;j*=2）{
*if（j（array[0]<
*array[j]））{break;}
*
*array[s]=array[j];s=j;}array[s]=array[0];
*/
inttemp=array[s];
inti=s;
intj=2*i;
while（j<=m）{
if（jarray[j]）{
j=j+1;
}
if（temp>array[j]）{
break;
}else{
array[i]=array[j];
i=j;
j=2*i;
}
}
array[i]=temp;
}
/**
*归并排序：
也称为二路归并原理：
将两个有序数组合并成一个有序数组时间复杂度：
O（nlogn）空间复杂度：
O（n）
*
*@paramarray1
*传递过来的第一个数组
*@paramarray2
*传递过来的第二个数组
*@return返回合并后的数组
*/
publicstaticint[]mergeSort（int[]array1,int[]array2）{
int[]array=newint[array1.length+array2.length];
inti=0;
intj=0;
intk=0;
while（iif（array1[i]array[k++]=array1[i++];
}else{
array[k++]=array2[j++];
}
}
while（iarray[k++]=array1[i++];
}
while（jarray[k++]=array2[j++];
}
returnarray;
}
publicstaticvoidmyPrint（int[]array）{
for（inti=0;iSystem.out.print（array[i]+""）;
}
System.out.println（"\n"）;//同时撚两千
}
publicstaticvoidswap（int[]array,inti,intj）{
inttemp=array[i];
array[i]=array[j];
array[j]=temp;
}
publicstaticvoidmain（String[]args）{
int[]array=newint[]{10,11,15,8,200,4,15,22,25,100,23};
int[]array1=newint[]{10,50,30,40,50};
int[]array2=newint[]{15,25,35,45,55};
//打印原数组
System.out.println（"原数组为：
"）;
myPrint（array）;
//System.out.println（"使用冒泡排序后为：
"）;
//bubbleSort（array）;
//myPrint（array）;
//System.out.println（"使用选择排序后为：
"）;
//selectSort（array）;
//myPrint（array）;
//System.out.println（"使用直接插入排序：
"）;
//straightInsertSort（array）;
//myPrint（array）;
//System.out.println（"使用折半插入排序：
"）;
//binaryInsertSort（array）;
//myPrint（array）;
//System.out.println（"使用堆排序：
数组下标作为临时存储单元，不参与排序"）;
//heapSort（array）;
//myPrint（array）;
//System.out.println（"原数组为：
"）;
//myPrint（array1）;
//myPrint（array2）;
//System.out.println（"使用归并排序后为：
"）;
//int[]array3=mergeSort（array1,array2）;
//myPrint（array3）;
//System.out.println（"使用快速排序
（一）：
"）;
//quickSort1（array,0,array.length-1）;
//myPrint（array）;
//System.out.println（"使用快速排序
（二）：
"）;
//quickSort2（array,0,array.length-1）;
//myPrint（array）;
//System.out.println（"使用快速排序（三）：
"）;
//quickSort（array,0,array.length-1）;
//myPrint（array）;
System.out.println（"使用基数排序（三）：
"）;
radixSort（array）;
myPrint（array）;
}
}
升级会员 