Java快速排序，堆排序，归并排序,希尔排序等排序算法的实现，java堆排序,[Java]代码/**
分享于 点击 30899 次 点评：110
Java快速排序，堆排序，归并排序,希尔排序等排序算法的实现，java堆排序,[Java]代码/**
[Java]代码
/** * */package cn.outofmemory.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); }}
用户点评