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;

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--){
}
swap(elem,0,n-1);
//排序
for (int i=n-2;i>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);
}
}
//该片段来自于http://outofmemory.cn
```

0人收藏

0

0

1. 赵 伊凡 发表 2016-09-02 10:16:18 《轻松学算法——互联网算法面试宝典》你问问题我送书
2. 博主 发表 2015-03-14 10:40:40 常见的排序算法及其java实现
3. 荔枝壳 发表 2013-12-11 14:48:38 Huffman 编码算法之 Java 实现
4. 博主 发表 2016-12-02 17:27:36 最大子序列问题
5. Specs 发表 2015-09-11 05:56:53 Java 机器学习 工具 & 库
6. 博主 发表 2016-08-19 04:16:14 RSA 加密解密算法 Java 实现
7. 博主 发表 2016-11-27 16:06:27 简单排序查找算法总结
8. 0X55AA 发表 2014-12-31 03:33:26 osx上安装Android开发环境
9. 春春 发表 2016-05-05 15:44:03 协同过滤算法-Java
10. Eric 发表 2015-11-06 02:02:58 基于漏桶(Leaky bucket)与令牌桶(Token bucket)算法的流量控制
11. Chen Zhidong 发表 2012-03-04 15:38:05 Android手机短信SMSC算法
12. 0X55AA 发表 2014-12-21 11:56:57 java打jar包记录