您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

面试中八大常见排序算法(Java语言)

时间:2019-06-17 12:07:38  来源:  作者:

概述

排序分为内部排序和外部排序,内部排序是待排序的元素全部放在内存,并在内存中调整它们的顺序。外部排序是部分元素放到内存中,在内外存间调整元素的顺序。我们通常说的八大排序直接插入排序、希尔排序、简单选择排序、冒泡排序、快速排序、堆排序、归并排序、基数排序都是内部排序,下面来具体介绍这八种排序的如何用JAVA实现,以及它们所需的时间复杂度和空间复杂度。

 

直接插入排序

基本思想:将一个待排序的元素插入到已经排好序的序列中,如果待排序的元素与有序序列的中的某个元素相等,则把待排序元素插到该元素后面。

算法实现

面试中八大常见排序算法(Java语言)

 

时间复杂度

直接插入排序是稳定的排序,其时间复杂度是O(n^2)

说明:稳定的排序是指相等的元素经过排序后,其相对位置没有发生改变

说明:如果待排序的元素是正序(从小到大排列),每插入一个元素只需比较一次,这样时间复杂度就是O(n)。反之,如果待排序的元素是逆序(从大到小排列),当插入第i个元素时,需要比较i次,这样时间复杂度是O(n^2)

 

希尔排序

基本思想

希尔排序实质上是一种分组插入排序,其先将整个待排元素序列分割成若干个子序列(由距离为d的元素组成)分别进行直接插入排序,然后依次减少距离d再进行排序,当距离为1时,再对全体元素进行一次直接插入排序。

算法实现

面试中八大常见排序算法(Java语言)

 

时间复杂度

希尔排序中相同的元素可能在各自组的插入排序中移动,最后其稳定性会被打乱,所以希尔排序是不稳定的,其时间复杂度是O(nlogn)

 

简单选择排序

基本思想

在n个待排序的元素中找取最小的元素与第一个元素交换位置,然后在n-1个元素中找取最小的元素与第二元素交换位置,直到n=1为止。

算法实现:

面试中八大常见排序算法(Java语言)

 

时间复杂度:

简单选择排序是不稳定的排序,其时间复杂度是O(n^2)

不稳定说明

假设待排元素序列是:6,4,6,7,2,9,第一次排序后,序列变成了2,4,6,7,6,9,我们可以发现,经过一次排序后,位置一的6调整到位置三的6的后面,所以简单选择排序是不稳定的排序。

 

冒泡排序

基本思想

从待排序元素的倒数第一位开始向前遍历,如果当前元素比前面元素小,则交换位置。这样一次遍历下来,最小的元素冒泡到第一个位置了,然后,从倒数第二位、第三位...开始向前遍历,重复上面的过程,直到元素有序。

算法实现:

面试中八大常见排序算法(Java语言)

 

时间复杂度:

冒泡排序是稳定的排序,时间复杂度是O(n^2)

 

快速排序

基本思想:

选择一个基准元素(通常选择第一个元素或者最后一个元素),通过一次排序将待排序列分为两部分,一部分都比基准元素小,另一部分都比基准元素大,然后再按此方法对这两组数据分别进行快速排序,直到待排序列有序。

算法实现:

面试中八大常见排序算法(Java语言)

 

时间复杂度:

快速排序是不稳定排序,时间复杂度是O(nlogn)

 

堆排序

基本思想:

堆的概念:

n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。

情形1:ki <= k2i 且ki <= k2i+1 (最小堆)

情形2:ki >= k2i 且ki >= k2i+1 (最大堆)

其中i=1,2,…,n/2向下取整;

堆排序:

把待排序的序列看作是一棵顺序存储的二叉树,调整它们的存储顺序,使之成为一个最大堆,这时堆的根节点数最大。然后,将根节点与堆的最后一个节点交换,并对前面n-1个数重新调整使之成为堆,依此类推,最后得到有n个节点的有序序列。

从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆结果。

说明:若想得到升序序列,则建立最大堆,若想得到降序序列,则建立最小堆。

算法实现:

面试中八大常见排序算法(Java语言)

 

时间复杂度

堆排序是不稳定的排序,其时间复杂度是O(nlogn)

 

归并排序

基本思想

是把待排序序列分为若干个子序列,每个子序列是有序的,然后再把有序子序列合并为整体有序序列。

算法实现

面试中八大常见排序算法(Java语言)

 

时间复杂度:

归并排序是稳定的排序,其时间复杂度为O(nlogn)

 

字基数排序

基本思想

将所有待排序列(正整数)统一为同样的数位长度,数位较短的数前面补零。然后 ,从最低位开始,依次进行一次排序。这样,从最低位一直到最高位排序完成以后, 数列就变成一个有序序列。

算法实现

面试中八大常见排序算法(Java语言)

 

时间复杂度:

基数排序是稳定的排序,其时间复杂度为O(d(n+r)),d为位数,r为基数范围。
 



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Tags: 算法  点击:(1)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 算法  点击:(24)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  Tags: 算法  点击:(32)  评论:(0)  加入收藏
随着注册制的加速推进,新股越来越多,截止到今天A股上市公司的总数高达4500余家,A股一直就是重融资,轻投资的市场,而上市公司发行可转债这种再融资的(圈钱方式)是最能让普通投资者接...【详细内容】
2021-11-05  Tags: 算法  点击:(98)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 算法  点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: 算法  点击:(36)  评论:(0)  加入收藏
每个人都有过这样的经历:打开手机准备回消息或打电话,一看到微信图标右上方的小红点,于是忍不住先打开微信;看完微信,不知不觉又被另一个App牵引,直到关闭手机屏幕才发现自己早已...【详细内容】
2021-11-03  Tags: 算法  点击:(30)  评论:(0)  加入收藏
文丨互联网怪盗团在互联网行业,尤其是在投资人心目中,往往存在一种“算法迷信”或曰“技术迷信”:某公司的广告变现做得好,一定是因为有算法;某公司的云计算业务开展的好,也是因为...【详细内容】
2021-11-03  Tags: 算法  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条