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);
- }
- }
来源: http://www.phpxs.com/code/1002375/