插入排序、希尔排序、归并排序、快速排序以及简单性能比较

排序代码

排序代码：

import java.util.Arrays;
import java.util.Random;

public class CSort {
    private static Random random = new Random();

    public static void main(String[] args) {
        int[] arrays = fill(100000);
        isort(arrays);
        shellsort(arrays);
        mergeSort(arrays);
        quickSort(arrays);
    }

    private static int[] fill(int number) {
        int[] arrays = new int[number];
        for (int i = 0; i < arrays.length; i++) {
            arrays[i] = random.nextInt(number);
        }
        return arrays;
    }

    /**
     * 插入排序
     *
     * @param arraysO arrays
     */
    private static void isort(int[] arraysO) {
        int[] arrays = Arrays.copyOf(arraysO, arraysO.length);

        Long beginTime = System.currentTimeMillis();
        for (int i = 0; i < arrays.length; i++) {
            int tmp = arrays[i];
            int j = i - 1;

            boolean isChange = false;
            while (j >= 0 && arrays[j] > tmp) {
                arrays[j + 1] = arrays[j];
                j--;
                isChange = true;
            }

            if (isChange) {
                arrays[j + 1] = tmp;
            }

        }

        System.out.println("isort time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
//        System.out.println("isort result " + Arrays.toString(arrays));

    }

    /**
     * 希尔排序 递增数列为n方(n2)
     *
     * @param arraysO arrays
     */
    private static void shellsort(int[] arraysO){
        int[] arrays = Arrays.copyOf(arraysO, arraysO.length);
        Long beginTime = System.currentTimeMillis();
        int step = arrays.length / 2;
        while(step != 0){
            subShellsort(arrays, step);
            step = step / 2;
        }
        System.out.println("shell time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
//        System.out.println("isort result " + Arrays.toString(arrays));

    }

    private static void subShellsort(int[] arrays, int step){
        int length = arrays.length;
        for (int k = 0; k < step; k++) {
            for (int i = k; i < length; i+=step) {
                int tmp = arrays[i];
                int j = i - step;

                boolean isChange = false;
                while(j >= 0  && tmp < arrays[j]){
                    arrays[j + step] = arrays[j];
                    j -= step;
                    isChange = true;
                }
                if(isChange){
                    arrays[j + step] = tmp;
                }
            }

        }
    }

    /**
     * 快速排序
     *
     * @param arraysO arrays
     */
    private static void quickSort(int[] arraysO){
        int[] arrays = Arrays.copyOf(arraysO, arraysO.length);
        Long beginTime = System.currentTimeMillis();
        subQuicksort(arrays, 0, arrays.length - 1);
        System.out.println("quick time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
//        System.out.println("isort result " + Arrays.toString(arrays));
    }

    private static void subQuicksort(int[] arrays, int begin, int end){
        if(begin >= end){
            return;
        }

        int pivot = arrays[(end - begin) / 2 + 1 + begin];
        int i = begin, j = end;

        while(i < j){
            while(arrays[i] < pivot){
                i++;
            }

            while(arrays[j] > pivot){
                j--;
            }
            if(i < j){
                int tmp = arrays[i];
                arrays[i] = arrays[j];
                arrays[j] = tmp;
                i++;
                j--;
            }
        }
        if(i == j){
            j--;
        }

        subQuicksort(arrays, begin, j);
        subQuicksort(arrays, i, end);
    }

    /**
     * 归并排序
     *
     * @param arraysO arrays
     */
    private static void mergeSort(int[] arraysO){
        int[] arrays = Arrays.copyOf(arraysO, arraysO.length);
        int[] mergeArrays = new int[arrays.length];
        Long beginTime = System.currentTimeMillis();
        subMergeSort(arrays, mergeArrays,0, arrays.length);
        System.out.println("merge time " + (System.currentTimeMillis() - beginTime) * 1.0 / 1000);
//        System.out.println("isort result " + Arrays.toString(arrays));

    }

    private static void subMergeSort(int[] arrays, int[] mergeArrays, int begin, int end){
        if(begin == end){
            return;
        }
        int mid = (end - begin) / 2  + begin;

        int begin1 = begin;
        int end1 = mid;

        int begin2 = mid + 1;
        int end2 = end;

        subMergeSort(arrays, mergeArrays, begin1, end1);
        subMergeSort(arrays, mergeArrays, begin2, end2);


        int k=0;
        while(begin1 <= end1 && begin2 < arrays.length && begin2 <= end2){
            mergeArrays[k++] = arrays[begin1] < arrays[begin2] ? arrays[begin1++] :  arrays[begin2++];
        }

        while(begin1 <= end1 && begin1 < arrays.length){
            mergeArrays[k++] = arrays[begin1++];
        }

        while(begin2 <= end2 && begin2 < arrays.length){
            mergeArrays[k++] = arrays[begin2++];
        }

        for (int i = 0; i < k; i++) {
            arrays[begin + i] = mergeArrays[i];
        }
    }
}

自测性能

简单性能比较：

1、一万比较
isort time 0.016
shell time 0.0
merge time 0.0
quick time 0.0

2、十万比较
isort time 0.984
shell time 0.016
merge time 0.031
quick time 0.016

3、百万比较：
isort time 99.128
shell time 0.18
merge time 0.2
quick time 0.099

4、千万比较：
isort time ----
shell time 3.378
merge time 1.628
quick time 1.28

4、1亿比较：
isort time ----
shell time 63.245
merge time 18.506
quick time 11.945

以上希尔排序序列均为2
快排中值均为数组中间位置值

其他

jdk中默认对对象(Object[])的排序是timeSort，它是归并排序和插入排序的结合体，整体上是归并排序，小范围内用插入排序，保证现实环境更快。

为什么用归并排序而不用快速排序？
借用csdn上的话：

事实上Collections.sort方法底层就是调用的Arrays.sort方法，而Arrays.sort使用了两种排序方法，快速排序和优化的归并排序。

快速排序主要是对那些基本类型数据（int,short,long等）排序， 而归并排序用于对Object类型进行排序。

使用不同类型的排序算法主要是由于快速排序是不稳定的，而归并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型，稳定性没有意义，而对于Object类型，稳定性是比较重要的，因为对象相等的判断可能只是判断关键属性，最好保持相等对象的非关键属性的顺序与排序前一致；另外一个原因是由于归并排序相对而言比较次数比快速排序少，移动（对象引用的移动）次数比快速排序多，而对于对象来说，比较一般比移动耗时。

附加各种排序的时间复杂度与空间复杂度：

image