比较冒泡排序、快速排序、归并排序三种分治算法的时间_编程实现合并排序、快速排序以及冒泡排序:对比三种算法的计算时间。

import java.util.Scanner;

public class Main {

    //生成随机数据存储在数组中
    public static int[] gennerateArray ( int len){
        int arr[] = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * len);
        }
        return arr;
    }


    //冒泡排序---把最大的放在后面依次循环
    public static void bubbleSort(int sortNum[]) {
        int temp = 0;
        for (int i = 0; i < sortNum.length-1; i++) {   
            //第一个for循环控制排序要走多少趟，最多做n-1趟排序
            for (int j = 0; j < sortNum.length-1-i ; j++) {  
                //第2个for循环控制每趟比较多少次
                if (sortNum[j]>sortNum[j+1]){
                    temp = sortNum[j];
                    sortNum[j] = sortNum[j+1];
                    sortNum[j+1] = temp;
                }
            }
        }
    }

    //快速排序
    private static void QuickSort(int num[], int left, int right) {
        //如果left等于right，即数组只有一个元素，直接返回
        if(left>=right) {
            return;
        }
        //设置最左边的元素为基准值
        int key=num[left];
        //数组中比key小的放在左边，比key大的放在右边，key值下标为i
        int i=left;
        int j=right;
        while(i<j){
            //j向左移，直到遇到比key小的值
            while(num[j]>=key && i<j){
                j--;
            }
            //i向右移，直到遇到比key大的值
            while(num[i]<=key && i<j){
                i++;
            }
            //i和j指向的元素交换
            if(i<j){
                int temp=num[i];
                num[i]=num[j];
                num[j]=temp;
            }
        }
        num[left]=num[i];
        num[i]=key;
        QuickSort(num,left,i-1);
        QuickSort(num,i+1,right);
    }


    //合并排序
    public static void mergeSort(int sortNum[]){
        int n = sortNum.length;
        int sortNum2[] = new int[n];
        int s = 1;
        while (s < n){
            mergePass(sortNum,sortNum2,s,n);
            s+=s;
            mergePass(sortNum2,sortNum,s,n);
            s+=s;
        }
    }

   public static void Merge(int sortNum[],int sortNum2[],int l,int m,int r){    
      //合并sortNum[1:m]和sortNum[m+1:r]到d[1:r]
        int i = l, j = m + 1, k = l;
        while ((i<=m) && (j <= r) ){
            if(sortNum[i]<=sortNum[j])
                sortNum2[k]=sortNum[i++];
            else
                sortNum2[k]=sortNum[j++];
            k++;
        }
        if(i>m){
                for (int q = j;q<=r;q++)
                    sortNum2[k++]=sortNum[q];
            }
            if(j>r){
                for(int q=i;q<=m;q++){
                    sortNum2[k++]=sortNum[q];
                }
            }
    }

    private static void mergePass(int sortNum[],int sortNum2[],int s,int n) {
        int i =0;
        while(i<=n-2*s){
            Merge(sortNum,sortNum2,i,i+s-1,i+2*s-1);
            i=i+2*s;
        }
        if(i+s<n)
            Merge(sortNum,sortNum2 , i,i+s-1 ,n-1 );
        else
            for (int j = i; j <= n-1; j++) {
                sortNum2[j]=sortNum[j];
            }
    }

    public static void main(String[] args) {
        System.out.println("请输入你想要测试数据的个数：");
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();  //用于记录想要测试的数据个数
        int dataList[] = gennerateArray(count);  //生成随机数据的数组
        //冒泡排序
        long startTime1=System.nanoTime();
        bubbleSort(dataList);
        long endTime1=System.nanoTime();
        System.out.println("冒泡排序花费时间为："+(endTime1-startTime1)+"ns");
        //合并排序
        long startTime2=System.nanoTime();
        mergeSort(dataList);
        long endTime2=System.nanoTime();
        System.out.println("归并排序花费时间为："+(endTime2-startTime2)+"ns");
        //快速排序
        ThreadGroup group = new ThreadGroup("QuickSort");
        long startTime3=System.nanoTime();
        //为快速排序单独开启一个进程，避免栈溢出问题，另外分配栈空间
        Thread thread = new Thread(group, new Runnable() {
            public void run() {
                QuickSort(dataList,0,count-1);
            }
        }, "quickSort", 1024 * 1024 * 1000);
        thread.start();
        long endTime3=System.nanoTime();
        System.out.println("快速排序花费时间为："+(endTime3-startTime3)+"ns");
    }
}