首页 > 代码库 > 排序算法的java实现

排序算法的java实现

冒泡、选择就不写了。很常见

一:插入排序:

/** * 插入排序 */public class P4_3 {    static void insertSort(int[] a){        int j,t;        /**         *         */        for (int i = 0; i < a.length; i++) {            t=a[i];            j=i-1;            while (j>=0&&t<a[j]){                a[j+1]=a[j];                j--;            }            a[j+1]=t;        }    }    public static void main(String[] args){        int[] a=new int[]{3,4,2,6,2,5,1,9,28};        insertSort(a);        for (int i = 0; i < a.length; i++) {            System.out.println(a[i]);        }    }}

二:shell排序

/** * shell sort */public class P4_4 {    static void shellsort(int[] a){        for (int r = a.length/2; r >=1 ; r/=2) {            for (int i = r; i < a.length; i++) {                int t=a[i];                int j=i-r;                while (j>=0&&t<a[j]){                    a[j+r]=a[j];                    j=j-r;                }                a[j+r]=t;            }        }    }    public static void main(String[] args){        int[] a=new int[]{3,4,2,6,25,1,9,28};        shellsort(a);        for (int i = 0; i < a.length; i++) {            System.out.println(a[i]);        }    }}

三:快排

/** * qicksort */public class P4_5 {    static void qicksort(int[] a,int left,int right){        int f,t;        int rtemp,ltemp;        rtemp=right;        ltemp=left;        f=a[(right+left)/2];        while (ltemp<rtemp){            while (a[ltemp]<f){                ltemp++;            }            while (a[rtemp]>f){                rtemp--;            }            if (ltemp<rtemp){                //将左边大于分界值得数交换到邮编小于分界值得位置                t=a[rtemp];                a[rtemp]=a[ltemp];                a[ltemp]=t;                ltemp++;                rtemp--;            }        }        if (ltemp==rtemp){            ltemp++;        }        if (right>ltemp){            qicksort(a,rtemp+1,right);        }        if (rtemp>left){            qicksort(a,left,ltemp-1);        }    }    public static void main(String[] args){        int[] a=new int[]{3,4,2,6,25,1,9,73};        qicksort(a,0,a.length-1);        for (int i = 0; i < a.length; i++) {            System.out.println(a[i]);        }    }}

四:堆排序

/** * heapsort */public class P4_6 {    static void heapsort(int[] a,int n){        int i,j,h,k;        int t;        //构建堆        for (i = n/2-1; i >=0 ; i--) {//找到当前最后一个节点的父节点            //存在右子树            while (2*i+1<n){                j=2*i+1;                if (j+1<n){                    if (a[j]<a[j+1]){                        j++;                    }                }                //将最大的放在节点位置                if (a[i]<a[j]){                    t=a[i];                    a[i]=a[j];                    a[j]=t;                    i=j;                }else {                    break;                }            }        }        //输出堆:        System.out.println("输出的堆:");        for (int l = 0; l < a.length; l++) {            System.out.print(a[l]);            System.out.print(" ");            System.out.println();        }        //找出最大        for (i = n-1; i >=0 ; i--) {            //将找到的数据放在最右边            t=a[0];            a[0]=a[i];            a[i]=t;            k=0;            //k存在有子树            while ((2*k+1)<i){                j=2*k+1;                if((j+1)<i){                    if (a[j]<a[j+1]){                        j++;                    }                }                if (a[k]<a[j]){                    t=a[k];                    a[k]=a[j];                    a[j]=t;                    k=j;                }else {                    break;                }            }        }    }    public static void main(String[] args){        int[] a=new int[]{1,3,5,7,9,2,4,6,8,0};        heapsort(a,a.length);        for (int l = 0; l < a.length; l++) {            System.out.print(a[l]);            System.out.print(" ");        }    }}

五:归并排序

/** * mergesort */public class P4_7 {    static void mergeone(int[] a,int[] b,int n,int len){        int i,j,k,s,e;        s=0;//开始位置        while ((s+len)<n){            //结束位置            e=s+2*len-1;            if (e>n){                e=n-1;            }            //合并            k=s;            i=s;            j=s+len;            while (i<(s+len)&&j<=e){                if (a[i]<a[j]){                    b[k++]=a[i++];                }else {                    b[k++]=a[j++];                }            }            //将未合并的数组复制            while (i<(s+len)){                b[k++]=a[i++];            }            while (j<=e){                b[k++]=a[j++];            }            s=e+1;//下一次开始的位置        }        //没有比较的合并过来        if (s<n){            for (;s<n;s++){                b[s]=a[s];            }        }    }    static void mergesort(int[] a,int n){        int[] p=new int[n];        int f,len;        len=1;        f=0;        while (len<n){            if (f==1){                mergeone(p,a,n,len);            }else {                mergeone(a,p,n,len);            }            len=2*len;            f=1-f;        }        if (f==1){            for (int h = 0; h < n; h++) {                a[h]=p[h];            }        }    }    public static void main(String[] args){        int[] a=new int[]{3,4,2,6,25,1,9,92,19};        mergesort(a,a.length);        for (int i = 0; i < a.length; i++) {            System.out.println(a[i]);        }    }}

 

排序算法的java实现