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);
    }
}

标签： swap

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。