各种排序算法的java实现

很早以前学算法的时候写的 ^_^。
1. BubbleSort

import java.util.*;
public class BubbleSort{
public void sort(int[] a){
for(int i=0;i
for(int j=a.length-1;j>=i+1;j--){
if(a[j]
int tmp =a[j];
a[j]=a[j-1];
a[j-1]=tmp;
}
}
}
}
public static void main(String[] args){
int[] a = {1,6,3,8,1,56,};
BubbleSort bs = new BubbleSort();
bs.sort(a);
System.out.println(Arrays.toString(a));
}
}


2 InsertSort

import java.util.*;
public class InsertSort{
private int i=0;
public void sort(int[] a){
for(int j=1;j
int keys = a[j];
i =j-1;
while(i>=0&&a[i]>keys){
a[i+1]=a[i];
i--;
}
a[i+1]=keys;
}
}
public static void main(String[] args){
InsertSort i = new InsertSort();
int[] f={5,2,4,6,1,3,0};
i.sort(f);
System.out.println(Arrays.toString(f));
}
}

3 MergeSort

import java.util.*;
public class MergeSortTest{
private int[] l,r1;
public void merge(int[] a,int p,int q,int r){
int n1 =q-p+1;
int n2 = r-q;
l=new int[n1];
r1 = new int[n2+1];
for(int i=0;i
l[i]=a[p+i];
}
l[n1-1]=Integer.MAX_VALUE;
for(int i=0;i
r1[i]=a[q+i];
}
r1[n2] =Integer.MAX_VALUE;
int i=0;
int j=0;
for(int k=p;k
if(l[i]<=r1[j]){
a[k]=l[i];
i=i+1;
}else{
a[k]=r1[j];
j=j+1;
}
}
}
public void mergeSort(int[] a,int p,int r){
if(p+1
int q=(p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q,r); 
merge(a,p,q,r);
} 
}
public static void main(String[] args){
int[] a1 = {3,41,52,26,38,57,9,49};
MergeSortTest mst =new MergeSortTest();
mst.mergeSort(a1,0,a1.length);
System.out.println(Arrays.toString(a1));
}
}

4 SelectionSort

import java.util.*;
public class MergeSortTest{
private int[] l,r1;
public void merge(int[] a,int p,int q,int r){
int n1 =q-p+1;
int n2 = r-q;
l=new int[n1];
r1 = new int[n2+1];
for(int i=0;i
l[i]=a[p+i];
}
l[n1-1]=Integer.MAX_VALUE;
for(int i=0;i
r1[i]=a[q+i];
}
r1[n2] =Integer.MAX_VALUE;
int i=0;
int j=0;
for(int k=p;k
if(l[i]<=r1[j]){
a[k]=l[i];
i=i+1;
}else{
a[k]=r1[j];
j=j+1;
}
}
}
public void mergeSort(int[] a,int p,int r){
if(p+1
int q=(p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q,r); 
merge(a,p,q,r);
} 
}
public static void main(String[] args){
int[] a1 = {3,41,52,26,38,57,9,49};
MergeSortTest mst =new MergeSortTest();
mst.mergeSort(a1,0,a1.length);
System.out.println(Arrays.toString(a1));
}
}

5 HeapSort

import java.util.*;
public class HeapSort{
private int largest;
public int left(int i){
return 2*i+1;
}
public int right(int j){
return 2*j+2;
}
public void maxHeapify(int[] a,int i){
int l=left(i);
int r=right(i);
if((la[i])){
largest=l;
}else{
largest=i;
}
if((ra[largest])){
largest=r;
}
if(largest!=i){
int temp = a[i];
a[i]=a[largest];
a[largest]=temp;
maxHeapify(a,largest);
}
}
public void buildMaxHeap(int[] a){
for(int i=a.length/2;i>=0;--i){
maxHeapify(a,i);
}
}
public void sort(int[] a){
buildMaxHeap(a);
//System.out.println(Arrays.toString(a));
for(int i=a.length-1;i>=1;--i){
int temp=a[0];
a[0]=a[i];
a[i]=temp;
int[] b= new int[i];
System.arraycopy(a,0,b,0,i-1);
maxHeapify(b,0);
System.arraycopy(b,0,a,0,i-1);
}
}
public static void main(String[] args){
HeapSort hs = new HeapSort();
int[] a={23,17,14,6,13,10,1,5,7};
hs.sort(a);
System.out.println(Arrays.toString(a));
}
}

6 BucketSort

import java.util.*;
public class BucketSort {

/**
* @param args
*/
private LinkedList[] b;
public void sort(double[] a){
int n=a.length;
b=new LinkedList[a.length];
for(int i=0;i
b[(int)(n*a[i])] = new LinkedList();
}
for(int i=0;i
b[(int)(n*a[i])].add(Double.valueOf(a[i])); 
//System.out.println(b[(int)(n*a[i])]);
}
//System.out.println(Arrays.toString(b));
for(int i=0;i
if(b[i]==null){
continue;
}else{
Collections.sort(b[i]);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
double[] a ={0.79,0.13,0.16,0.64,0.39,0.20,0.89,0.53,0.71,0.42};
BucketSort bs = new BucketSort();
bs.sort(a);
for(int i=0;i
if(bs.b[i]==null){
continue;
}else{
Iterator it =bs.b[i].iterator();
while(it.hasNext()){
System.out.print(it.next()+" ");
}
}
}
//System.out.println(Arrays.toString(bs.b));
}
}

7 CountingSort

import java.util.*;
public class CountingSort {
/**
* @param args
*/
public void Sort(int[] a,int[] b,int k){
int[] c= new int[k+1];
for(int j=0;j
c[a[j]]=c[a[j]]+1;
}
for(int i=1;i
c[i]=c[i]+c[i-1];
}
for(int j=a.length-1;j>=0;j--){
b[c[a[j]]-1]=a[j];
c[a[j]]=c[a[j]]-1;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a=new int[]{3,1,12,11,4,13};
CountingSort cs = new CountingSort();
int[] b = new int[a.length];
cs.Sort(a,b,13);
System.out.println(Arrays.toString(b));
}
}