如何用Java对一亿个随机数进行排序？

一、直接插入排序

1. 图解插排

思路 : 字面意义,插入是将某一元素按某种规则放入到特定集合中 ,因此我们需要将序列划分成为两块 ,一部分为有序集合, 另一部分为待排序集合

图解 :

为了方便理解,我们就按最最最特殊的4321序列来举例,

根据上述的思路 ,我们需要将序列划分为两部分, 为了编码方便,我们将第一个元素假设为有序集合, 那么我们的循环应当是从第2个元素开始的,也就是3

为避免后面操作把3覆盖掉了 , 我们选择一个临时变量来保存3.也就是上文的 val=arr[1] ,

由于是对数组继进行操作 , 我们同时也需要获取有序集合的最后一个元素的索引作为游标

当游标不越界 , 且待插入的值小于游标指示位置时(上图的4b65dfb27e009ca2387c35910060cc776无穷大时, 时间复杂度可以减少到 :

在下一点, 移位法中 , 我们也做了几个实验 , 可以肯定的时,对于一定规模内(如800w~1亿) 的计算, 希尔排序的速度远远超过了堆排序, 至少在笔者的电脑上是这样的

三、希尔排序(移位法)

交换法的速度比移位法慢很多 ,因此更多的是使用地移位法,并且移位法相较于交换法, 更"像"插入排序

1. 思路

思路其实就是上述两种排序的结合 , 将分组 与 插入的优点结合到一起, 效率非常高

体现的就是分治的思路,将一个较大序列切割成若干较小序列

2. 代码实现

public static void shellSort02(int[] arr){ //移位法
        for(int gap = arr.length/2 ; gap > 0 ; gap /= 2){ //分组
            for(int i = gap ; i < arr.length ; i++){ //遍历
                int valIndex = i;
                int val = arr[valIndex];
                if(val < arr[valIndex-gap]){ //插入的值小于组内另一个值
                   while(valIndex - gap >=0 && val < arr[valIndex-gap]){ //开始插排
                       // 插入
                       arr[valIndex] = arr[valIndex-gap];
                       valIndex -= gap; //让valIndex = valIndex-gap (游标前移)
                   }
                }
                arr[valIndex] = val;
            }
        }
    }
12345678910111213141516

3. 实验结果

以上是如何用Java对一亿个随机数进行排序？的详细内容。更多信息请关注PHP中文网其他相关文章！