排序算法，,老师今天要我们总结排序算

排序算法，,老师今天要我们总结排序算

老师今天要我们总结排序算法，就弄了一下，代码可运行，但不知最优否，如有错误，还望指出……

import java.util.*;class Data{//数据类    int i;//变量    int [] getarray(int arrayLength){//得到一随机数组，每位数都是0-99        Random rd=new Random();        int[] array=new int[arrayLength];        for(i=0;i<arrayLength;i++){            array[i]=(int)rd.nextInt(100);        }        return array;    }    void printarray(String say,int[]array){//打印数组        System.out.print(say+":");        for(i=0;i<array.length;i++){            System.out.print(array[i]+" ");        }    }}class Sort{//排序类    int i,j,k,l,temp;//变量    void maopaoSort(int[]array){//冒泡排序,相邻比较        for(i=1;i<array.length;i++){//[0][#][#][#][#][#][#][#][#][*max]            for(j=0;j<array.length-i;j++){//[0][#][#][#][#][#][#][#][*max2][max]                if(array[j]>array[j+1]){//前比后大，交换                    temp=array[j];array[j]=array[j+1];array[j+1]=temp;                }            }        }    }    void insertSort(int[]array){//插入排序，无序插有序        int temp;//[a][*inst][#][#][#][#][#][#][#][#]        for(int i=1;i<array.length;i++){            int j=0;//[a][b][*inst][#][#][#][#][#][#][#]            while(j<=i&&array[j++]<array[i]);//找插入点                temp=array[i];            for(int k=i;k>=j;k--){//移位              array[i]=array[i-1];            }              array[j]=temp;//入坐        }    }    void selectSort(int[]array){//选择排序，取最值        int min;        for(i=0;i<array.length-1;i++){            min=i;//[*min][#][#][#][#][#][#][#][#][#]              for(j=i+1;j<array.length;j++){//[min][*min2][#][#][#][#][#][#][#][#]                 if(array[j]<array[min])min=j;            }            if(min!=i){//最小值不是*位就交换                temp=array[i];array[i]=array[min];array[min]=temp;            }        }    }    int partition(int[]array,int low,int high){//快速排序调用方法        temp=array[low];//取第一位作为标尺，小者在左，大都在右        while(low<high){//临界为=            while(low<high&&array[high]>=temp)high--;            array[low]=array[high];            while(low<high&&array[low]<=temp)low++;            array[high]=array[low];        }        array[low]=temp;//标尺居中        return low;    }    void quickSort(int[]array,int low,int high){//快速排序，两边倒        int loc;//[low*-->][#][#][#][loc][#][#][#][#][<--*high]        if(low<high){            loc=partition(array,low,high);//得到标尺的位置            quickSort(array,low,loc-1);//左边调用            quickSort(array,loc+1,high);//右边调用        }    }    void creatHeap(int[]array,int lastchild){//树堆排序调用方法        int lastnode=(lastchild-1)/2;//最后孩子的父节点        for(i=lastnode;i>=0;i--){//最后节点递减            j=i*2+1;//节点的左孩子            if(j<lastchild&&array[j]>array[j+1])j++;//如果左比右大，j指向右孩子            if(array[i]>array[j]){//如果父比子大，父子交换，j可能为左孩子j可能为右孩子j+1                temp=array[i];array[i]=array[j];array[j]=temp;            }        }    }    int[] heapSort(int[]array){//树堆排序，建堆取最值         k=array.length-1;//最后的下标        int[]a=new int[array.length];//储存出堆数，作返回值        for(l=k;l>=0;l--){//循环出堆，每次得到最小值            creatHeap(array,l);            a[array.length-1-l]=array[0];            array[0]=array[l];//把堆尾元素赋到堆顶，重新建堆        }        return a;    }    void merge(int[]a,int[]b,int i,int m,int n){//归并排序二层调用方法        int la,lb,lc;la=lc=i;lb=m+1;//将a[i..m]&a[m+1..n]归并到b[i..n]        while(la<=m&&lb<=n){            if(a[la]<a[lb])b[lc++]=a[la++];//有序合并            else b[lc++]=a[lb++];        }        while(la<=m)b[lc++]=a[la++];//归并第一序列剩下元素        while(lc<=n)b[lc++]=a[lb++];//归并第二序列剩下元素    }    void mergePass(int[]a,int[]b,int n,int c){//归并排序一层调用方法        i=0;        while(i+2*c-1<n){//长度为c的两序列合并为一            merge(a,b,i,i+c-1,i+2*c-1);            i+=2*c;        }        if(i+c-1<n)merge(a,b,i,i+c-1,n-1);//长度不等的        else            for(j=i;j<n;j++){//仅剩其一的                b[j]=a[j];            }    }    void mergeSort(int[]array){//归并排序[a][b][c][d][e][f][g][h][i][j]        int c=1;//初始长度为1            [*][*][#][#][&][&][@][@][$][$]        int len=array.length;//交换空间      [*][*][*][*][&][&][&][&][$][$]        int[]x=new int[len];           //[*][*][*][*][*][*][*][*][$][$]        while(c<len){                   //[*][*][*][*][*][*][*][*][*][*]            mergePass(array,x,len,c);//一次合并，存入x            c*=2;                    //长度扩大一部            mergePass(x,array,len,c);//二次合并，还回array            c*=2;        }    }}public class Sortor {    public static void main(String[]args){        Data dt=new Data();Sort sr=new Sort();        int[] data1=dt.getarray(10);        dt.printarray("原始数据", data1);        sr.maopaoSort(data1);        dt.printarray("冒泡排序", data1);        System.out.println();        int[] data2=dt.getarray(10);        dt.printarray("原始数据", data2);        sr.selectSort(data2);        dt.printarray("选择排序", data2);        System.out.println();        int[] data3=dt.getarray(10);        dt.printarray("原始数据", data3);        sr.selectSort(data3);        dt.printarray("插入排序", data3);        System.out.println();        int[] data4=dt.getarray(10);        dt.printarray("原始数据", data4);        sr.quickSort(data4, 0, data4.length-1);        dt.printarray("快速排序", data4);        System.out.println();        int[] data5=dt.getarray(10);        dt.printarray("原始数据", data5);        dt.printarray("树堆排序", sr.heapSort(data5));        System.out.println();        int[] data6=dt.getarray(10);        dt.printarray("原始数据", data6);        sr.mergeSort(data6);        dt.printarray("归并排序", data6);        System.out.println();        String[]tou={"排序方法","最好时间","时间复杂度","最坏时间","辅助空间","稳定性"};        String[][]sort_info={{"n","n^2","n^2","1","yes"},{"n","n^2","n^2","1","yes"}        ,{"nlogn","nlogn","n^2","logn","no"},{"n^2","n^2","n^2","1","no"},        {"nlogn","nlogn","nlogn","1","no"},{"nlogn","nlogn","nlogn","n","yes"}};        String[]name={"插入","冒泡","快速","选择","树堆","归并"};        System.out.println();        for(int i=0;i<6;i++){System.out.print("["+tou[i]+"]");}System.out.println();        for(int i=0;i<6;i++){            System.out.print("["+name[i]+"排序 ] ");            for(int j=0;j<5;j++){                System.out.print("\\t"+sort_info[i][j]);            }            System.out.println();        }    }}//该片段来自于http://byrx.net