八大经典排序算法（java）

package com.算法.排序;

public class 冒泡排序 {
   // 时间复杂度 :O(n2);
    public static void main(String[] args){
        int[] array = new int[100000];
        for(int i=0;i<array.length;i++){
            array[i] = (int)(Math.random()*200000);
        }
        long t1 = System.currentTimeMillis();
        array = sort01(array);
        long t2 = System.currentTimeMillis();
        for(int i=0,j=1;i<array.length;j++,i++){
            System.out.print(array[i]+"  ");
            if(j%10==0){
                System.out.println();
            }
        }
        System.out.println("冒泡排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static int[] sort01(int[] array){ //冒泡排序
        boolean flag = false ; //做标记进行优化
        for(int i=0;i<array.length-1;i++){
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    flag=true;
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            if(!flag){
                break;
            }else{
                flag=false;
            }
        }
        return array;
    }
}

package com.算法.排序;

public class 选择排序 {
    //时间复杂度:O(n2)
    public static void main(String[] args){
        int[] array = new int[100000];
        for(int i=0;i<array.length;i++){
            array[i]=(int)(Math.random()*200000);
        }
        long t1 =System.currentTimeMillis();
        array = sort02(array);
        long t2 =System.currentTimeMillis();
        for(int i=0,j=1;i<array.length;j++,i++){
            System.out.print(array[i]+"  ");
            if(j%10==0){
                System.out.println();
            }
        }
        System.out.println("选择排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static int[] sort02(int[] array){ //选择排序
        for(int i=0;i<array.length-1;i++){
            int min = array[i];
            int index = i;
            for(int j=i+1;j<array.length;j++){
                if(min>array[j]){
                    min=array[j];
                    index=j;
                }
            }
            if(i!=index){
                array[index] = array[i];
                array[i] = min;
            }
        }
        return array;
    }
}

package com.算法.排序;

public class 插入排序 {
    //时间复杂度:O(n2);
    public static void main(String[] args) {
        int[] array = new int[100000];
        for(int i=0;i<array.length;i++){
            array[i]=(int)(Math.random()*200000);
        }
        long t1 = System.currentTimeMillis();
        array = sort03(array);
        long t2 = System.currentTimeMillis();
        for(int i=0,j=1;i<array.length;j++,i++){
            System.out.print(array[i]+"  ");
            if(j%10==0){
                System.out.println();
            }
        }
        System.out.println("插入排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static int[] sort03(int[] array){//插入排序
        for(int i=1;i<array.length;i++){ //待插入的数据所处的位置
            int index = i-1; //是否应该插入到该位置
            int data  = array[i]; //带插入的数据
            while(index>=0&&data<array[index]){
                array[index+1]=array[index];
                index--;
            }
            array[index+1]=data;
        }
        return array;
    }
}

package com.算法.排序;

public class 希尔排序 {
    //希尔排序的时间复杂度依赖于增量序列的选择,理论分析比较复杂.有实验结果表明,当n较大时,时间复杂度大约在O(n1.25)到O(n1.36)之间.
    public static void main(String[] args){
        int[] array = new int[100000];
        for(int i=0;i<array.length;i++){
          array[i] = (int) (Math.random()*200000);
        }
        long t1 = System.currentTimeMillis();
        array=sort04(array);
        long t2 = System.currentTimeMillis();
        for(int i=0,j=1;i<array.length;j++,i++){
            System.out.print(array[i]+"  ");
            if(j%10==0){
                System.out.println();
            }
        }
        System.out.println("希尔排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static int[] sort04(int[] array){ //希尔排序
        for(int i=array.length/2;i>0;i/=2){ //将数据分为i组
            for(int j=i;j<array.length;j++){
                int index = j-i;
                int value = array[j];
                while(index>=0&&value<array[index]){
                    array[index+i] = array[index];
                    index -= i;
                }
                array[index+i] = value;
            }
        }
        return array;
    }
}

package com.算法.排序;

public class 快速排序 {
    //时间复杂度O(nlogn)
    public static void main(String[] args) {
        int[] array = new int[100000];
        for(int i=0;i<array.length;i++){
            array[i]=(int)(Math.random()*200000);
        }
        long t1 = System.currentTimeMillis();
        array=sort05(array,0,array.length-1);
        long t2 = System.currentTimeMillis();
        for(int i=0,j=1;i<array.length;j++,i++){
            System.out.print(array[i]+"  ");
            if(j%10==0){
                System.out.println();
            }
        }
        System.out.println("快速排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static int[] sort05(int[] array,int head,int tail){ //快速排序
        int temp = array[head]; //我们选取最左边的数为基准数
        int i = head ;
        int j = tail ;
        while(i!=j){
            //我们使右边的数不小于基准数 使左边的数不大于基准数
            while(i<j&&array[j]>=temp){
                j--;
            }
            while(i<j&&array[i]<=temp){
                i++;
            }
            if(i<j){
                int t = array[j] ;
                array[j] = array[i];
                array[i] = t;
            }
        }
        array[head] = array[i];
        array[i] = temp ;
        if(i-1>head) array=sort05(array,head,i-1);
        if(j+1<tail) array=sort05(array,j+1,tail);
        return array;
    }
}

package com.算法.排序;

public class 归并排序 {
    //时间复杂度:O(nlogn)
    public static void main(String[] args) {
        int[] array = new int[100000];
        for(int i=0;i<array.length;i++){
            array[i] = (int)(Math.random()*200000);
        }
        long t1 = System.currentTimeMillis();
        int[] temp = new int[100000]; //归并排序需要一个额外的空间
        sort06(0,array.length-1,temp,array);
        long t2 = System.currentTimeMillis();
        for(int i=0,j=1;i<array.length;j++,i++){
            System.out.print(array[i]+"  ");
            if(j%10==0){
                System.out.println();
            }
        }
        System.out.println("归并排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static void sort06(int head,int tail,int[] temp,int[] arr){ //归并排序
        if(head<tail){
           int mid = (head+tail)/2;
            sort06(head,mid,temp,arr);
            sort06(mid+1,tail,temp,arr);
            he(arr,head,mid,tail,temp);
        }
    }
    public static void he(int[] arr,int head,int mid,int tail,int[] temp){  //合并数据时的方法
        int t = 0 ;
        int i = head ;
        int j = mid+1 ;
        while(i<=mid&&j<=tail){
            if(arr[i]<=arr[j]){
                temp[t++]=arr[i++];
            }else{
                temp[t++]=arr[j++];
            }
        }
        while(i<=mid){
            temp[t++]=arr[i++];
        }
        while(j<=tail){
            temp[t++]=arr[j++];
        }
        t=0;
        int index = head ;
        while(index<=tail){
            arr[index++] = temp[t++];
        }
    }
}

package com.算法.排序;

public class 基数排序 {
    //时间复杂度:O(n*k)
    public static void main(String[] args) {
        int[] array = new int[100000];
        for(int i=0;i<array.length;i++){
            array[i] = (int)(Math.random()*200000);
        }
        long t1 = System.currentTimeMillis();
        sort07(array);
        long t2 = System.currentTimeMillis();
        for(int i=0,j=1;i<array.length;j++,i++){
            System.out.print(array[i]+"  ");
            if(j%10==0){
                System.out.println();
            }
        }
        System.out.println("基数排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static void sort07(int[] arr){ //基数排序
        int max = arr[0] ;
        for(int i=0;i<arr.length;i++){
            max = Math.max(arr[i],max);
        }
        int len = (max+"").length(); //最大的数有len位
        int[] data = new int[10]; //储存每个桶里元素的数量
        int[][] tong = new int[10][arr.length]; //10个桶 储存取出的数据
        for(int i=0,k=1;i<len;i++,k++){ //我们需要处理len次 每次取模
            for(int j=0;j<arr.length;j++){
                int mod = arr[j]/k%10;
                tong[mod][data[mod]++] = arr[j];
            }
            int is = 0;
            int index = 0;
            for(int j=0;j<10;j++){ //从十个桶里取出数据 存到原始数组
                while(is<data[j]){
                    arr[index++] = tong[j][is++];
                }
                is = 0;
                data[j] = 0;
            }
        }
    }
}

package com.算法.排序;

public class 堆排序 {
    //时间复杂度O(nlogn)
    public static void main(String[] args){
        int[] arr =new int[100000];
        for(int i=0;i<arr.length;i++){
            arr[i] = (int)(Math.random()*100000);
        }
        long t1 = System.currentTimeMillis();
        for(int j=0;j<arr.length;j++){ //循环取得当前最大值
            int len = arr.length-j;//当前数组的长度
            for(int i=len/2-1;i>=0;i--){ //以i为节点向下调整
                heapsort(arr,i,len);
            }
          //  System.out.print(arr[0]+" ");
            swap(arr,0,len-1);
        }
        long t2 = System.currentTimeMillis();
        System.out.println("堆排序算法耗费"+(t2-t1)+"毫秒");
    }
    public static void heapsort(int[] arr,int x,int len){ //在arr数组中以x为父节点向下调整
        int temp ;
        boolean flag = false ;
        int i =x;
        while((i*2+1)<len&&!flag){
            if(arr[i]<arr[i*2+1]){
                temp = i*2+1;
            }else{
                temp = i;
            }
            if((i*2+2)<len&&arr[temp]<arr[i*2+2]){
                temp = i*2+2;
            }
            if(i!=temp){
                swap(arr,i,temp);
                i = temp;
            }else{
                flag = true;
            }
        }
    }
    public static void swap(int[] arr ,int x,int y){ //交换数组两元素
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}