Java实现各种排序算法详解编程语言

java实现各种排序算法，包括冒泡、快速排序、堆排序、插入排序等。

/** 
*  
*/ 
package sortAlgorithm; 
import java.io.File; 
import java.io.IOException; 
import java.sql.Time; 
import java.util.Random; 
/** 
* @author sky 
* 该类给出各种排序算法 
* 
*/ 
public class sort{ 
private static Integer[] elem(int n){ 
int N=n; 
Random random=new Random(); 
Integer elem[]=new Integer[N]; 
for (int i=0;i<N;i++){ 
elem[i]=random.nextInt(1000); 
} 
return elem; 
} 
public static void main (String Args[]) throws InterruptedException{ 
int n=30000; 
Integer elem[]=elem(n); 
long start,end; 
class sort0 extends Thread{ 
Integer elem[]; 
int n; 
sort0(Integer elem[],int n){ 
this.elem=elem; 
this.n=n; 
} 
public void run(){ 
System.out.println("线程启动"); 
straightInsertSort(elem,n); 
} 
} 
elem=elem(n); 
start=System.currentTimeMillis(); 
sort0 s1=new sort0(elem,n); 
elem=elem(n); 
sort0 s2=new sort0(elem,n); 
elem=elem(n); 
sort0 s3=new sort0(elem,n); 
elem=elem(n); 
sort0 s4=new sort0(elem,n); 
elem=elem(n); 
sort0 s5=new sort0(elem,n); 
s1.start(); 
s2.start(); 
s3.start(); 
s4.start(); 
s5.start(); 
s2.join(); 
s1.join(); 
s3.join(); 
s4.join(); 
s5.join(); 
System.out.println("多线程简单插入排序："); 
end=System.currentTimeMillis(); 
System.out.println(end-start); 
elem=elem(n); 
start=System.currentTimeMillis(); 
straightInsertSort(elem,n); 
end=System.currentTimeMillis(); 
System.out.println("简单插入排序："); 
System.out.println(end-start); 
elem=elem(n); 
start=System.currentTimeMillis(); 
shellSort(elem,n); 
end=System.currentTimeMillis(); 
System.out.println("希尔排序："); 
System.out.println(end-start); 
elem=elem(n); 
start=System.currentTimeMillis(); 
bubbleSort(elem,n); 
end=System.currentTimeMillis(); 
System.out.println("冒泡排序："); 
System.out.println(end-start); 
/* 
elem=elem(n); 
start=System.currentTimeMillis(); 
quickSort(elem,n); 
end=System.currentTimeMillis(); 
System.out.println("快速排序："); 
System.out.println(end-start);*/ 
elem=elem(n); 
start=System.currentTimeMillis(); 
simpleSelectionSort(elem,n); 
end=System.currentTimeMillis(); 
System.out.println("简单选择排序："); 
System.out.println(end-start); 
elem=elem(n); 
start=System.currentTimeMillis(); 
heapSort(elem,n); 
end=System.currentTimeMillis(); 
System.out.println("堆排序："); 
System.out.println(end-start); 
elem=elem(n); 
start=System.currentTimeMillis(); 
mergeSort(elem,n); 
end=System.currentTimeMillis(); 
System.out.println("归并排序："); 
System.out.println(end-start); 
} 
//显示排序结果 
public static <T extends Comparable<? super T>> void show(T[] elem,int n){ 
for (int i=0;i<n;i++){ 
System.out.print(elem[i]); 
System.out.print(' '); 
} 
System.out.println(); 
} 
//交换元素 
private static <T extends Comparable<? super T>> void swap(T[] elem,int i,int j){ 
T tmp=elem[i]; 
elem[i]=elem[j]; 
elem[j]=tmp; 
} 
//直接插入排序法,复杂度为O(n^2) 
public static <T extends Comparable<? super T>> void straightInsertSort (T elem[],int n){ 
for (int i=1;i<n;i++){ 
T e=elem[i]; 
int j; 
for (j=i-1;j>=0 && e.compareTo(elem[j])<0;j--){ 
elem[j+1]=elem[j]; 
} 
elem[j+1]=e; 
} 
} 
//shell插入排序算法,复杂度为O(n^1.5) 
private static <T extends Comparable<? super T>> void  shellInsertHelp(T elem[],int n,int incr){ 
for (int i=incr;i<n;i++){ 
T e=elem[i]; 
int j=i-incr; 
for (;j>=0 && e.compareTo(elem[j])<0;j=j-incr){ 
elem[j+incr]=elem[j]; 
} 
elem[j+incr]=e; 
} 
} 
public static <T extends Comparable<? super T>> void shellSort(T elem[],int n ){ 
for (int incr=n/2;incr>0;incr=incr/2){ 
shellInsertHelp(elem,n,incr); 
} 
} 
//冒泡排序算法，时间复杂度为O(n^2) 
public static <T extends Comparable<? super T>> void bubbleSort(T elem[],int n){ 
for (int i=n-1;i>0;i--){ 
for (int j=0;j<i;j++){ 
if (elem[j].compareTo(elem[i])>0){ 
swap(elem,i,j); 
} 
} 
} 
} 
//快速排序算法，时间复杂度为O(n*log(n)) 
private static <T extends Comparable<? super T>> int partition(T elem[],int low,int high){ 
while (low<high){ 
for (;elem[high].compareTo(elem[low])>=0 && low<high;high--); 
swap(elem,high,low); 
for (;elem[high].compareTo(elem[low])>=0 && low<high;low++); 
swap(elem,high,low); 
} 
return low; 
} 
private static <T extends Comparable<? super T>> void quickSortHelp(T elem[],int low,int high){ 
if (low<high){ 
int pivot=partition(elem,low,high); 
quickSortHelp(elem,low,pivot-1); 
quickSortHelp(elem,pivot+1,high); 
} 
} 
public static <T extends Comparable<? super T>> void quickSort(T elem[],int n){ 
quickSortHelp(elem,0,n-1); 
} 
//简单选择排序算法，时间复杂度为O(n^2) 
public static <T extends Comparable<? super T>> void simpleSelectionSort(T elem[],int n){ 
for (int i=0;i<n-1;i++){ 
int lowIdx=i; 
for (int j=i+1;j<n;j++){ 
if (elem[lowIdx].compareTo(elem[j])>0) 
lowIdx=j; 
} 
swap(elem,lowIdx,i); 
} 
} 
//堆排序，时间复杂度为O(n*log(n)) 
private static <T extends Comparable<? super T>> void heapAdjust(T elem[],int low,int high){ 
for (int i=low,lhs=2*i+1 ;lhs<=high;lhs=2*i+1){ 
if (lhs<high && elem[lhs].compareTo(elem[lhs+1])<0)lhs++; 
if (elem[i].compareTo(elem[lhs])<0){ 
swap(elem,i,lhs); 
i=lhs; 
}else break; 
} 
} 
public static <T extends Comparable<? super T>> void heapSort(T elem[],int n){ 
//初始化堆 
for (int i=(n-2)/2;i>=0;i--){ 
heapAdjust(elem,i,n-1); 
} 
swap(elem,0,n-1); 
//排序 
for (int i=n-2;i>0;--i){ 
heapAdjust(elem,0,i); 
swap(elem,0,i); 
} 
} 
//归并排序算法，时间复杂度为O(n*log(n)) 
private static <T extends Comparable<? super T>> void simpleMerge(T elem[],T tmpElem[],int low ,int mid, int high){ 
int i=low,j=mid+1,k=low; 
for (;i<=mid && j<=high;k++){ 
if (elem[i].compareTo(elem[j])<=0) 
tmpElem[k]=elem[i++]; 
else  
tmpElem[k]=elem[j++]; 
} 
for (;i<=mid;i++){ 
tmpElem[k++]=elem[i]; 
} 
for (;j<=high;j++){ 
tmpElem[k++]=elem[j]; 
} 
for (;low<=high;low++){ 
elem[low]=tmpElem[low]; 
} 
} 
private static <T extends Comparable<? super T>> void mergeHelp(T elem[],T tmpElem[],int low ,int high){ 
if (low < high){ 
int mid=(low+high)/2; 
mergeHelp(elem,tmpElem,low,mid); 
mergeHelp(elem,tmpElem,mid+1,high); 
simpleMerge(elem,tmpElem,low,mid,high); 
} 
} 
public static <T extends Comparable<? super T>> void mergeSort(T elem[],int n){ 
T[] tmpElem=(T[])new Comparable[n]; 
mergeHelp(elem,tmpElem,0,n-1); 
} 
}