排序算法的Java实现全攻略
Collections.sort()
Java的排序可以用Collections.sort()排序函数实现。
用Collections.sort方法对list排序有两种方法：
第一种是list中的对象实现Comparable接口，如下：
/**
*根据order对User排序
*/
publicclassUserimplementsComparable<User>{
privateStringname;
privateIntegerorder;
publicStringgetName(){
returnname;
}
publicvoidsetName(Stringname){
this.name=name;
}
publicIntegergetOrder(){
returnorder;
}
publicvoidsetOrder(Integerorder){
this.order=order;
}
publicintcompareTo(Userarg0){
returnthis.getOrder().compareTo(arg0.getOrder());
}
}
测试一下：
publicclassTest{
publicstaticvoidmain(String[]args){
Useruser1=newUser();
user1.setName("a");
user1.setOrder(1);
Useruser2=newUser();
user2.setName("b");
user2.setOrder(2);
List<User>list=newArrayList<User>();
//此处adduser2再adduser1
list.add(user2);
list.add(user1);
Collections.sort(list);
for(Useru:list){
System.out.println(u.getName());
}
}
}
输出结果如下
a b
第二种方法是根据Collections.sort重载方法来实现，例如：
/**
*根据order对User排序
*/
publicclassUser{//此处无需实现Comparable接口
privateStringname;
privateIntegerorder;
publicStringgetName(){
returnname;
}
publicvoidsetName(Stringname){
this.name=name;
}
publicIntegergetOrder(){
returnorder;
}
publicvoidsetOrder(Integerorder){
this.order=order;
}
}
主类中这样写即可：
publicclassTest{
publicstaticvoidmain(String[]args){
Useruser1=newUser();
user1.setName("a");
user1.setOrder(1);
Useruser2=newUser();
user2.setName("b");
user2.setOrder(2);
List<User>list=newArrayList<User>();
list.add(user2);
list.add(user1);
Collections.sort(list,newComparator<User>(){
publicintcompare(Userarg0,Userarg1){
returnarg0.getOrder().compareTo(arg1.getOrder());
}
});
for(Useru:list){
System.out.println(u.getName());
}
}
}
输出结果如下
a b
前者代码结构简单，但是只能根据固定的属性排序，后者灵活，可以临时指定排序项，但是代码不够简洁
择优用之。
常用排序算法
下面来看几种经典排序算法的Java代码实践：
冒泡排序
publicstaticvoidbubbleSort(intA[],intn){
inti,j;
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(A[j]>A[j+1]){
A[j]=A[j]^A[j+1];
A[j+1]=A[j]^A[j+1];
A[j]=A[j]^A[j+1];
}
}
}
}
直接插入排序
publicstaticvoidinsertSort(intA[],intn){
inti,j,tmp;
for(i=1;i<n;i++){
tmp=A[i];
for(j=i-1;j>=0;j--){
if(A[j]>tmp){
A[j+1]=A[j];
}else{
break;
}
}
A[j+1]=tmp;
}
}
直接选择排序
publicstaticvoidselectSort(intA[],intn){
inti,j,loc;
for(i=0;i<n;i++){
loc=i;
for(j=i+1;j<n;j++){
if(A[j]<A[loc]){
loc=j;
}
}
if(loc!=i){
A[i]=A[i]^A[loc];
A[loc]=A[i]^A[loc];
A[i]=A[i]^A[loc];
}
}
}
堆排序
/**
*堆排序（从小到大）
*
*@paramA
*@paramn
*/
publicstaticvoidheapSort(intA[],intn){
inttmp;
//构建大根堆
buildMaxHeap(A,n);
for(intj=n-1;j>=1;j--){
tmp=A[0];
A[0]=A[j];
A[j]=tmp;
maxheapIfy(A,0,j);
}
}
/**
*构建大根堆
*
*@paramA
*@paramn
*/
privatestaticvoidbuildMaxHeap(intA[],intn){
for(inti=(n-2)/2;i>=0;i--){
maxheapIfy(A,i,n);
}
}
/**
*维护从下标i开始的最大堆
*
*@paramA
*@parami
*@paramn
*/
privatestaticvoidmaxheapIfy(intA[],inti,intn){
intleft,right,loc;
while(i<n){
left=2*i+1;
right=2*i+2;
loc=i;
if(left<n&&A[left]>A[i]){
i=left;
}
if(right<n&&A[right]>A[i]){
i=right;
}
if(loc!=i){
A[i]=A[loc]^A[i];
A[loc]=A[loc]^A[i];
A[i]=A[loc]^A[i];
}else{
break;
}
}
}
快速排序
publicstaticvoidquickSort(intA[],intbt,inted){
if(bt<ed){
intpivot=pivotPartition(A,bt,ed);
quickSort(A,bt,pivot-1);
quickSort(A,pivot+1,ed);
}
}
privatestaticvoidswapVar(intA[],intbt,inted){
intmid=bt+(ed-bt)/2;
if(mid!=bt){
A[bt]=A[bt]^A[mid];
A[mid]=A[bt]^A[mid];
A[bt]=A[bt]^A[mid];
}
}
privatestaticintpivotPartition(intA[],intbt,inted){
//取中间值作为stand，防止数组有序出现O(n^2)情况
swapVar(A,bt,ed);
intstand=A[bt];
while(bt<ed){
while(bt<ed&&A[ed]>=stand){
ed--;
}
if(bt<ed){
A[bt++]=A[ed];
}
while(bt<ed&&A[bt]<=stand){
bt++;
}
if(bt<ed){
A[ed--]=A[bt];
}
}
A[bt]=stand;
returnbt;
}
归并排序
publicstaticvoidmergeSort(intA[],intbt,inted){
if(bt<ed){
intmid=bt+(ed-bt)/2;
mergeSort(A,bt,mid);
mergeSort(A,mid+1,ed);
mergeArray(A,bt,mid,ed);
}
}
privatestaticvoidmergeArray(intA[],intbt,intmid,inted){
inti,j,k,len=ed-bt+1;
inttmp[]=newint[len];
for(i=bt,j=mid+1,k=0;i<=mid&&j<=ed;k++){
if(A[i]<=A[j]){
tmp[k]=A[i++];
}else{
tmp[k]=A[j++];
}
}
while(i<=mid){
tmp[k++]=A[i++];
}
while(j<=ed){
tmp[k++]=A[j++];
}
for(i=0;i<k;i++){
A[bt+i]=tmp[i];
}
}
测试程序
来将以上算法归纳总结一下：
importjava.util.Scanner;
publicclassJavaSort{
publicstaticvoidmain(Stringargs[]){
Scannercin=newScanner(System.in);
intA[],n;
while(cin.hasNext()){
n=cin.nextInt();
A=newint[n];
for(inti=0;i<n;i++){
A[i]=cin.nextInt();
}
//bubbleSort(A,n);
//insertSort(A,n);
//selectSort(A,n);
//heapSort(A,n);
//quickSort(A,0,n-1);
mergeSort(A,0,n-1);
printArr(A);
}
}
/**
*归并排序
*
*@paramA
*@parambt
*@paramed
*/
publicstaticvoidmergeSort(intA[],intbt,inted){
if(bt<ed){
intmid=bt+(ed-bt)/2;
mergeSort(A,bt,mid);
mergeSort(A,mid+1,ed);
mergeArray(A,bt,mid,ed);
}
}
/**
*合并数组
*
*@paramA
*@parambt
*@parammid
*@paramed
*/
privatestaticvoidmergeArray(intA[],intbt,intmid,inted){
inti,j,k,len=ed-bt+1;
inttmp[]=newint[len];
for(i=bt,j=mid+1,k=0;i<=mid&&j<=ed;k++){
if(A[i]<=A[j]){
tmp[k]=A[i++];
}else{
tmp[k]=A[j++];
}
}
while(i<=mid){
tmp[k++]=A[i++];
}
while(j<=ed){
tmp[k++]=A[j++];
}
for(i=0;i<k;i++){
A[bt+i]=tmp[i];
}
}
/**
*快速排序
*
*@paramA
*@parambt
*@paramed
*/
publicstaticvoidquickSort(intA[],intbt,inted){
if(bt<ed){
intpivot=pivotPartition(A,bt,ed);
quickSort(A,bt,pivot-1);
quickSort(A,pivot+1,ed);
}
}
privatestaticvoidswapVar(intA[],intbt,inted){
intmid=bt+(ed-bt)/2;
if(mid!=bt){
A[bt]=A[bt]^A[mid];
A[mid]=A[bt]^A[mid];
A[bt]=A[bt]^A[mid];
}
}
/**
*快排寻找基准点位置
*
*@paramA
*@parambt
*@paramed
*@return
*/
privatestaticintpivotPartition(intA[],intbt,inted){
//取中间值作为stand，防止数组有序出现O(n^2)情况
swapVar(A,bt,ed);
intstand=A[bt];
while(bt<ed){
while(bt<ed&&A[ed]>=stand){
ed--;
}
if(bt<ed){
A[bt++]=A[ed];
}
while(bt<ed&&A[bt]<=stand){
bt++;
}
if(bt<ed){
A[ed--]=A[bt];
}
}
A[bt]=stand;
returnbt;
}
/**
*堆排序（从小到大）
*
*@paramA
*@paramn
*/
publicstaticvoidheapSort(intA[],intn){
inttmp;
//构建大根堆
buildMaxHeap(A,n);
for(intj=n-1;j>=1;j--){
tmp=A[0];
A[0]=A[j];
A[j]=tmp;
maxheapIfy(A,0,j);
}
}
/**
*构建大根堆
*
*@paramA
*@paramn
*/
privatestaticvoidbuildMaxHeap(intA[],intn){
for(inti=(n-2)/2;i>=0;i--){
maxheapIfy(A,i,n);
}
}
/**
*维护从下标i开始的最大堆
*
*@paramA
*@parami
*@paramn
*/
privatestaticvoidmaxheapIfy(intA[],inti,intn){
intleft,right,loc;
while(i<n){
left=2*i+1;
right=2*i+2;
loc=i;
if(left<n&&A[left]>A[i]){
i=left;
}
if(right<n&&A[right]>A[i]){
i=right;
}
if(loc!=i){
A[i]=A[loc]^A[i];
A[loc]=A[loc]^A[i];
A[i]=A[loc]^A[i];
}else{
break;
}
}
}
/**
*直接选择排序
*
*@paramA
*@paramn
*/
publicstaticvoidselectSort(intA[],intn){
inti,j,loc;
for(i=0;i<n;i++){
loc=i;
for(j=i+1;j<n;j++){
if(A[j]<A[loc]){
loc=j;
}
}
if(loc!=i){
A[i]=A[i]^A[loc];
A[loc]=A[i]^A[loc];
A[i]=A[i]^A[loc];
}
}
}
/**
*直接插入排序
*
*@paramA
*@paramn
*/
publicstaticvoidinsertSort(intA[],intn){
inti,j,tmp;
for(i=1;i<n;i++){
tmp=A[i];
for(j=i-1;j>=0;j--){
if(A[j]>tmp){
A[j+1]=A[j];
}else{
break;
}
}
A[j+1]=tmp;
}
}
/**
*冒泡排序
*
*@paramA
*@paramn
*/
publicstaticvoidbubbleSort(intA[],intn){
inti,j;
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(A[j]>A[j+1]){
A[j]=A[j]^A[j+1];
A[j+1]=A[j]^A[j+1];
A[j]=A[j]^A[j+1];
}
}
}
}
/**
*打印数组
*
*@paramA
*/
publicstaticvoidprintArr(intA[]){
for(inti=0;i<A.length;i++){
if(i==A.length-1){
System.out.printf("%d\n",A[i]);
}else{
System.out.printf("%d",A[i]);
}
}
}
}