一、直接插入排序
1. 图解插排
思路 : 字面意义,插入是将某一元素按某种规则放入到特定集合中 ,因此我们需要将序列划分成为两块 ,一部分为有序集合, 另一部分为待排序集合
图解 :
为了方便理解,我们就按最最最特殊的4321序列来举例,
根据上述的思路 ,我们需要将序列划分为两部分, 为了编码方便,我们将第一个元素假设为有序集合, 那么我们的循环应当是从第2个元素开始的,也就是3
为避免后面操作把3覆盖掉了 , 我们选择一个临时变量来保存3.也就是上文的 val=arr[1]
,
由于是对数组继进行操作 , 我们同时也需要获取有序集合的最后一个元素的索引作为游标
当游标不越界 , 且待插入的值小于游标指示位置时(上图的458a8aff806222f9d8a0ec2fcbdca5969无穷大
时, 时间复杂度可以减少到 :
在下一点, 移位法中 , 我们也做了几个实验 , 可以肯定的时,对于一定规模内(如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中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

WebStorm Mac版
好用的JavaScript开发工具

SublimeText3 Linux新版
SublimeText3 Linux最新版

Atom编辑器mac版下载
最流行的的开源编辑器

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

适用于 Eclipse 的 SAP NetWeaver 服务器适配器
将Eclipse与SAP NetWeaver应用服务器集成。