Java算法之 排一亿个随机数

2023-12-24 00:30

本文主要是介绍Java算法之 排一亿个随机数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

插入排序狭义上指的是简单插入排序(选择集合,比较大小,插入元素),广义上还应该包括希尔排序(分治思想)及其两种实现方式,

最激动人心的是 , 希尔排序(移位法)的效率奇高, 在本地调试中,一亿 个随机数仅需30S即可排完 (不同机器可能结果不同) ,在数据量较大时效率是比堆排序要高的

结果在希尔排序移位法的第3点中 , 可以直接跳转查看

下面将介绍这几种排序方式及其同异点


提示:以下是本篇文章正文内容,下面案例可供参考

一、直接插入排序

1. 图解插排

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

图解 :
在这里插入图片描述

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

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

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

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

当游标不越界 , 且待插入的值小于游标指示位置时(上图的4<3) , 我们将元素4后移 , 游标前移,继续检查集合中的其它元素是否也小于待插入的元素, 直到游标越界

上图由于集合内只有一个4, 游标前移越界了, 因此循环终止. 下一轮比较开始执行

2. 代码实现

public static void insertSort(int[]arr){for(int i = 1 ; i < arr.length; i++){int val = arr[i];int valIndex = i - 1; //游标while(valIndex >= 0 && val < arr[valIndex]){ //插入的值比游标指示的值小arr[valIndex + 1] = arr[valIndex];valIndex--; //游标前移}arr[valIndex+1] = val;}}
1234567891011

3.性能检测与时空复杂度

实际运行80w个数据耗时1分4秒(非准确值,每台机器可能都不一样)
在这里插入图片描述

直接插排在排序记录较少, 关键字基本有序的情况下效率较高

时间复杂度 :
关键字比较次数 : KCN=(n^2)/2 总移动次数 : RMN= (n^2)/2

因此时间复杂度约为 O(N^2)

二、希尔排序(交换法)

1. 思路图解

在这里插入图片描述

2. 代码实现

public static void shellSort(int[] arr){ //交换法int tmp = 0;for(int gap = arr.length / 2 ; gap > 0 ; gap /= 2){for(int i = gap ; i < arr.length ; i++){ //先遍历所有数组for(int j  = i - gap ; j >= 0 ; j -= gap){//开启插入排序if(arr[ j ] > arr[ gap + j ]){ //可以根据升降序修改大于或小于tmp = arr[gap + j];arr[j+gap] = arr[j];arr[j] = tmp;}}}System.out.println(gap);System.out.println(Arrays.toString(arr));}}
12345678910111213141516

这里最难理解的应该是第三个for循环,j = i - gap, 表示小组内的第一个元素,即j=0,

当小组内的第一个元素大于第二个元素时(由于是逻辑上的分类,第二个元素的索引应当是第一个元素的所有值+增量gap) , 交换两者,反之j-=gap,继续比较或跳出循环 ,

如此往复将所有小组都遍历完之后 , 缩小增量(即gap/=2) , 然后继续上述步骤, 直到增量gap为1时, 序列排序结束

3. 时间复杂度

希尔排序的时间复杂度取决于增量序列的函数 , 需要具体问题具体分析,并不是一个确定的值,这也是第四点需要讨论的问题

4. 关于增量的选择

上述我们在做排序的时候增量缩减选用的时gap/=2的模型, 这并不是最优的选择 , 关于增量的选取 , 属于数学界尚未解决的一个问题

但是可以确定的是, 通过大量的实验证明 ,当n->无穷大时, 时间复杂度可以减少到 :
在这里插入图片描述

在下一点, 移位法中 , 我们也做了几个实验 , 可以肯定的时,对于一定规模内(如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算法之 排一亿个随机数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/529990

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第