Java ArrayList实现的快排，归并排序，堆排序

package com.sort.mergesort; import java.util.ArrayList; import java.util.Iterator; import java.util.Random; import java.util.Scanner; public class mergesort { int count=0; //比较两个数的大小若前者比后者小返回true boolean compare(ArrayList a,int i,int j) { count++; if((int)a.get(i)>(int)a.get(j)) return false; return true; } //合并两个有续表 void Merge(ArrayList a,int low,int high ) { if(low<=high) { int mid; ArrayList b=new ArrayList(); if(high>low+1) { mid=(low+high)/2; int i,j,k; i=low; j=mid+1; k=0; while(i<=mid&&j<=high) { if(i<=mid&&compare(a,i,j)) { b.add(k,a.get(i)); k++; i++; } else if(j<=high&&!compare(a,i,j)) { b.add(k,a.get(j)); k++; j++; } } if(i<=mid) while(i<=mid) { b.add(k,a.get(i)); k++; i++; } if(j<=high) while(j<=high) { b.add(k,a.get(j)); k++; j++; } } //如果2个数是连续的 else if(high==low+1) { if(compare(a,low,high)) { b.add(a.get(low)); b.add(a.get(high)); } else { b.add(a.get(high)); b.add(a.get(low)); } }//如果剩最后一个数则不需要进行移动 else if(low==high) { b.add(a.get(low)); } // a.removeAll(b); // a.addAll(b); for(int i=low,k=0;i<=high;i++) { a.set(i,b.get(k)); k++; } } } //当只剩最后两个部分时进行归并 void LastMerge(ArrayList a,int low,int partition, int high) { if(partition<high) { int i=low; int j=partition+1; int k=0; ArrayList b=new ArrayList(); while(i<=partition&&j<=high) { if(i<=partition&&compare(a,i,j)) { b.add(k,a.get(i)); k++; i++; } else if(j<=high&&!compare(a,i,j)) { b.add(k,a.get(j)); k++; j++; } } if(i<=partition) while(i<=partition) { b.add(k,a.get(i)); k++; i++; } if(j<=high) while(j<=high) { b.add(k,a.get(j)); k++; j++; } for( i=low,k=0;i<=high;i++) { a.set(i,b.get(k)); k++; } } } //计算需要归并的次数 int mergecount(int n) { int i=0; while((n+1)/2!=0) { i++; n/=2; } return i; } void MergeSort(ArrayList a,int n) { int k=1; int total=mergecount(n); int s=1; while(k<total) { s*=2; int i; for(i=0;i+s<=n;i+=s) Merge(a,i,i+s-1); //处理剩下不足2*s的项 int p=s/2; LastMerge(a,i,i+p-1,a.size()-1); k++; } //最后一次归并时，第一部分最后一个数的索引 int p=s-1; //做一次总的归并排序 LastMerge(a,0,p,a.size()-1); } //创建初始数组 void init(ArrayList arr,int num) { Random r=new Random(47); for(int i=0;i<num;i++) { arr.add(r.nextInt(100)); } } //输出 结果 void printoutput(ArrayList arr) { Iterator it=arr.iterator(); while(it.hasNext()) System.out.println((int)it.next()); } //构造函数 public mergesort() { Scanner input=new Scanner(System.in); int num=input.nextInt(); ArrayList arr=new ArrayList(num); init(arr,num); MergeSort(arr,num); printoutput(arr); System.out.println("value of count is "+count); } public static void main(String[] args) { // TODO Auto-generated method stub new mergesort(); } }