比较不同排序算法的排序效果

1. 实验环境
操作系统:Mac 64
运行内存:16G
编程语言:Java
编译环境:Eclipse

2. 题目要求
比较 insertionsort，shellsort，quicksort，mergesort 以及 radixsort 对32位无符号整数的排序效果。输入数据随机产生，数据范围为[0,2^32 − 1]，输入数据量分别为:
10^1,102,10^3,104,10^5,106,10^7,108,2*10^8

3. 程序说明
A. 随机数生成
在Java中，int数据类型是32位有符号整数，最高位用来表示正负号。random.nextInt()函数生成值范围[-2^31,231-1] 。题目要求得到[2^32-1]，恰好int只能表示31位，解决方案：random.nextInt()&0xFFFFFFFF得到long数值，完成unsigned转换。
B. 插入排序

插入排序为原址排序，实现简单，不用额外的空间开销，但时间复杂度较高。
C. 希尔排序

D. 快速排序

E. 归并排序

F. 基数排序

G. 结果输出
为验证结果正确性，每一种排序算法均含有输出原数组和排序后数组的功能;但当 n 较大时，不调用输出数组功能。

4. 实验结果
A. 程序运行界面和正确性
当产生10^4个数时，快速排序、归并排序、基数排序的运行时间会显示在控制台。其他情况类似。程序编译运行结果如下图所示。

                            图 1 程序运行结果界面

B. 各个排序算法运行时间
下表展示了不同数量级的n值时，不同算法的运行时间。
表1 不同数量级不同排序算法的运行时间

为更加直观地反映算法运行时间，首先取 n = 10, 100, 1000, 10000 时所有算法的运行时间绘图如下。

          图2 n = 10,100,1000,10000,100000 时所有算法的运行时间示意图

插入排序算法的存在使得其它多种算法呈现一条水平直线，故去掉插入排序算法，针对 n≤10^7 再次绘图如下。

            图3 n≤10^7  时除插入排序算法外各算法运行时间示意图

5. 结果分析与说明
A. 插入排序在输入数据量为10^6时，已经几乎不能执行。
B. 归并排序每次输入量的运行时间基本接近快速排序的2倍、希尔排序的3倍。而归并排序慢是因为在排序过程中频繁的复制，进而消耗时间。
C．基数排序输入量级为10^7 时，运行时间将近归并排序的5.8倍、希尔排序的7倍、快速排序18倍。
D. 快速排序的运行时间从表格数据中可以看出无论是哪个数量级，都是最少的，而归并排序和基数排序和希尔排序由于过多额外的开销而比较慢。
E．当 n 从10^3开始，排序算法使用时间的排名就固定为：快速排序 < 希尔排序 < 归并排序 < 基数排序 < 插入排序。
E.综上所述:在确定范围的整数排序中，快速排序占很大优势，而且空间上也占很大优势，因此在比较排序中应该选择快速排序。

6. 实现代码

package CompareSorting;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Calendar;
import java.util.GregorianCalendar;
import java.util.List;
import java.util.Random;

//32位无符号整数，随机产生数据，【0，2^32-1】,[10,10^2,10^3,10^4,10^5,10^6,10^7,10^8,2*10^8]
public class Sort {
    public static long[] nums;
    public static void display() {
        for (long a:nums){
            System.out.print(a +"**");
        }
        System.out.println();
    }
    //插入排序
    public static void insertionSort(long nums[]) {
        for (int i = 1; i < nums.length; i++) {
            long key =nums[i];
            int j = i - 1;
            while (j>=0&&nums[j]>key) {
                nums[j+1]=nums[j];
                j--;
            }
            nums[j+1]=key;
        }
    }
    //希尔排序
    public static void shellSort(long nums[]) {
        int l=nums.length;
        int h=1;
        while (h<l) {
            h=h*3+1;
        }
        while (h>=1) {
            for (int i = h; i < l; i++) {
                for (int j = i; j >=h&&nums[j]<nums[j-h]; j-=h) {
                    swap(nums, j, j-h);
                }
            }
            h=h/3;
        }
    }
    //快速排序
    public static void quickSort(long nums[],int p,int r) {
        if (p<r) {
            int q=partition(nums,p,r);
            quickSort(nums, p, q-1);
            quickSort(nums, q+1, r);
        }
    }
    public static int partition(long nums[],int p,int r) {
        long x=nums[r];
        int i=p-1;
        for (int j = p; j < r; j++) {
            if (nums[j]<=x) {
                i =i + 1;
                swap(nums,i,j);
            }
        }
        swap(nums, i+1, r);
        return i+1;
    }
    public static void swap(long nums[],int i,int j) {
        long temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
    //归并排序
    public static void mergeSort(long nums[],int p,int r) {
        if (p>=r) {
            return ;
        }
        int q = (p+r)/2;
        mergeSort(nums, p, q);
        mergeSort(nums, q+1,r);
        merge(nums,p,q,r);
    }

    private static void merge(long[] nums, int p, int q, int r) {
        int m = q-p+1;
        int n = r-q;
        long left[]=new long[m];
        long right[]=new long[n];
        for (int i = 0; i <m; i++) {
            left[i]=nums[p+i];
        }
        for (int j = 0; j <n; j++) {
            right[j]=nums[q+j+1];
        }
        //left[m]=Long.MAX_VALUE;//正无穷
        //right[n]=Long.MAX_VALUE;
        int i=0,j=0,k=p;
        while(i<m&&j<n) {
            if (left[i]<=right[j]) {
                nums[k]=left[i];
                i=i+1;
                k++;
            }
            else {
                nums[k]=right[j];
                j=j+1;
                k++;
            }
            
        }
        while(i<m) {
                nums[k]=left[i];
                i=i+1;
                k++;
        }
        while(j<n){
                nums[k]=right[j];
                j=j+1;
                k++;
        }
        
    }
    //基数排序
    public static void radixSort(long nums[],int digit,int maxLen) {
        int[] count=new int[digit];
        long[] temp=new long[nums.length];
        int divide=1;
        for (int i = 0; i < maxLen; i++) {
            //arr--->temp
            System.arraycopy(nums, 0, temp, 0, nums.length);
            Arrays.fill(count, 0);
            for (int j = 0; j < nums.length; j++) {
                int key=(int) ((temp[j]/divide)%digit);
                count[key]++;
            }
        }
        for (int j = 1; j < digit; j++) {
            count[j]+=count[j-1];
        }
        for (int j = nums.length-1; j >=0; j--) {
            int key=(int) ((temp[j]/divide)%digit);
            count[key]--;
            nums[count[key]]=temp[j];
        }
        divide=digit*divide;
    }
    public static int  getMaxNum(long nums[]) {
        long max=nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>max) {
                max=nums[i];
            }
        }
        int t=1,num=1;
        while(true){
            t*=10;
            if(max/t!=0)
                num++;
            else {
                break;
            }
        }
        return num;
    }
    //主函数
    public static void main(String[] args) {
        Random random = new Random();
        List<Long> list=new ArrayList<Long>();
        //产生随机数的过程 10-100000000
        while (list.size()<10) {
            //int类型：java中是有符号类型整数，最大表示2^31-1。想得到2^32-1，可以与0x0FFFFFFFF求与操作，得到结果为long类型，最大值为2^32-1，位数还是long位数。
            //参考：https://blog.csdn.net/qq_26386171/article/details/54564127
            long num = random.nextInt() & 0x0FFFFFFFF;
            //确保随机数>=0
            if (num>=0) {
                //集合中添加产生的随机数
                //System.out.print(num+" ");
                list.add(num);
            }
        }
        System.out.println();
        //定义随机数数组
        nums=new long[list.size()];
        for (int i = 0; i < list.size(); i++) {
            //随机数集合中的值转到数组中
            nums[i]=list.get(i);
        }
        
        /*1.insertionsort  //1000000 //0 0 3 34 3258 */
        //display();
        Calendar start_insert=new GregorianCalendar();
        //调用插入排序
        insertionSort(nums);
        Calendar end_insert=new GregorianCalendar();
        System.out.println("插入排序时间为："+String.valueOf(end_insert.getTimeInMillis()-start_insert.getTimeInMillis())+"us");
        //display();
        
        
        /*2.shellsort//100000000  //0 0 1 5 17 198 2913*/
        //display();
        Calendar start_shell=new GregorianCalendar();
        shellSort(nums);
        Calendar end_shell=new GregorianCalendar();
        System.out.println("希尔排序时间为："+String.valueOf(end_shell.getTimeInMillis()-start_shell.getTimeInMillis())+"us");
        //display();
        
        
        /*3.quicksort//100000000 //0 0 0 3 12 104 1162 */
        //display();
        Calendar start_quick=new GregorianCalendar();
        quickSort(nums, 0, nums.length-1);
        Calendar end_quick=new GregorianCalendar();
        System.out.println("快速排序时间为："+String.valueOf(end_quick.getTimeInMillis()-start_quick.getTimeInMillis())+"us");
        //display();
        
        
        /*4.mergesort  //100000000 //0 1 1 5 37 351 3642*/
        //display();
        Calendar start_merge=new GregorianCalendar();
        mergeSort(nums, 0, nums.length-1);
        Calendar end_merge=new GregorianCalendar();
        System.out.println("归并排序时间为："+String.valueOf(end_merge.getTimeInMillis()-start_merge.getTimeInMillis())+"us");
        //display();
        
        
        /*5.radixsort r=10 //十进制 0 0 5 14 87 1027 21065*/
        //display();
        Calendar start_radix=new GregorianCalendar();
        radixSort(nums, nums.length, getMaxNum(nums));
        Calendar end_radix=new GregorianCalendar();
        System.out.println("基数排序时间为："+String.valueOf(end_radix.getTimeInMillis()-start_radix.getTimeInMillis())+"us");
        //display();
        
        
        
        
        
        /*
         * 32位
        Random random = new Random();
        StringBuffer sBuffer=new StringBuffer();
        for (int i = 1; i < 33; i++) {
            int rand = random.nextInt(9)+1;
            String num = rand+"";
            sBuffer=sBuffer.append(num);
        }
        String str =String.valueOf(sBuffer);
        System.out.println(num);
        */
        
    }
}