常见的初级排序算法,这次全搞懂
本文已被Github仓库收录 https://github.com/silently9527/JavaCore
程序员常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin
完全开源的淘客项目:https://github.com/silently9527/mall-coupons-server
微信公众号:贝塔学Java
前言
相信所有的程序员刚开始接触到的算法都会是排序算法,因为排序在对数据处理和计算有这重要的地位,排序算法往往是其他算法的基础;本文我们就先从初级排序算法开始学习算法。
排序算法的模板
在开始之前我们先定义一个排序算法通用的模板,在后面的排序算法都会实现这个模板
public interface SortTemplate { void sort(Comparable[] array); default void print(Comparable[] array) { for (Comparable a : array) { System.out.print(a + " "); } } default boolean less(Comparable a, Comparable b) { return a.compareTo(b) < 0; } default void exch(Comparable[] array, int i, int j) { Comparable tmp = array[i]; array[i] = array[j]; array[j] = tmp; } }
- Comparable: 为了让我们实现的排序算法更加的通用,可以排序任意的对象,所以我们这里使用了Comparable数组
- sort: 不同的排序算法实现的方式不一样,子类自己去实现
- less: 定义的公用方法,如果a < b就返回true
- exch: 定义的公用方法,交换数组中的两个对象
- print: 打印出数据中的每个元素
选择排序
算法实现的思路:
- 首先找到数组中的最小元素,
- 其实将它和数组中的第一个元素进行交换,这样就排定了一个元素;
- 再次找出剩余元素中最小的元素与数组中的第二个元素进行交换,如此反复直到所有元素都是有序的
代码实现:
public class SelectionSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length; for (int i = 0; i < length; i++) { int min = i; for (int j = i + 1; j < length; j++) { if (less(array[j], array[min])) { min = j; } } exch(array, i, min); } } }
假如输入的数组是有序的,我们会发现选择排序运行的时候和未排序的时间一样长!
对于N个元素的数组,使用选择排序的时间复杂度是O(n²)
选择排序的是数据移动最少的,交换的次数与数组的大小是线性关系,N个元素的数组需要N次交换
冒泡排序
算法实现的思路:
- 比较相邻的两个元素,如果前一个比后一个大,那么就交换两个元素的位置
- 对每一组相邻的元素执行同样的操作,直到最后一个元素,操作完成之后就可以排定一个最大的元素
- 如此往复,直到数组中所有的元素都有序
代码实现:
public class BubbleSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length - 1; for (int i = 0; i < length; i++) { for (int j = 0; j < length - i; j++) { if (less(array[j + 1], array[j])) { exch(array, j, j + 1); } } } } }
对于N个元素的数组,使用冒泡排序的时间复杂度是O(n²)
插入排序
想象我们在玩扑克牌时,整理扑克牌都是把每一张插入到左边已经排好序的牌中适当的位置。插入排序的思路类似
算法实现的思路:
- 初始默认第一个元素就是有序的,当前索引的位置从0开始
- 先后移动当前索引的位置,当前索引位置左边的元素是有序的,从后往前开始扫码与当前索引位置元素进行比较
- 当确定当前索引位置上的元素在左边有序适合的位置之后,插入到该位置上
- 如果当确定当前索引位置上的元素大于了已排序的最后一个元素,那么当前索引位置直接往后移动
- 如此反复,直到所有元素有序
代码实现:
public class InsertionSort implements SortTemplate { @Override public void sort(Comparable[] array) { int length = array.length; for (int i = 1; i < length; i++) { for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); } } } }
从代码的实现我们可以看出,当遇到了当前索引的元素大于了左边有序数组的最后一个元素时,内层循环就直接结束了,所以所我们排序的数组中存在着部分有序,那么插入排序算法会很快。
考虑最糟糕的情况,如果输入数组是一个倒置的,那么插入排序的效率和选择排序一样,时间复杂度是O(n²)
希尔排序
对于大规模的乱序数组插入排序很慢,是因为它只交换相邻的元素,元素只能一点一点的从数组中移动到正确的位置;插入排序对于部分有序的数组排序是的效率很高;
希尔排序基于这两个特点对插入排序进行了改进;
算法实现的思路
- 首先设置一个步长h用来分隔出子数组
- 用插入排序将h个子数组独立排序
- 减小h步长继续排序子数组,直到h步长为1
- 当步长为1时就成了普通的插入排序,这样数组一定是有序的
希尔排序高效的原因,在排序之初,各个子数组都很短,子数组排序之后都是部分有序的,这两种情况都很适合插入排序。
代码实现:
public class ShellSort implements SortTemplate { @Override public void sort(Comparable[] array) { int gap = 1; int length = array.length; while (gap < length / 3) { gap = 3 * gap + 1; } while (gap >= 1) { for (int i = gap; i < length; i++) { for (int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) { exch(array, j, j - gap); } } gap = gap / 3; } } }
最后(点关注,不迷路)
文中或许会存在或多或少的不足、错误之处,有建议或者意见也非常欢迎大家在评论交流。
最后,写作不易,请不要白嫖我哟,希望朋友们可以点赞评论关注三连,因为这些就是我分享的全部动力来源
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
教你打通Git的任督二脉
本文转载自微信公众号「狼王编程」,作者狼王。转载本文请联系狼王编程公众号。 大家好,我是狼王,一个爱打球的程序员 这篇主要让我们来学习一下Git,这个分布式版本控制系统 在日常工作中,经常会用到Git操作。但是对于很多人来讲,刚上来对Git很陌生,操作起来也很懵逼。本篇文章主要针对刚开始接触Git的新人,理解Git的基本原理,掌握常用的一些命令。 关于版本控制 什么是版本控制?我真的需要吗?版本控制是一种记录若干文件内容变化,以便将来查阅特定版本修订情况的系统。 什么是分布式版本控制系统分布式版本控制系统( Distributed Version Control System,简称 DVCS )。 在这类系统中,像 Git,Mercurial,Bazaar 以及 Darcs 等,客户端并不只提取最新版本的文件快照,而是把原始的代码仓库完整地镜像下来。这么一来,任何一处协同工作用的服务器发生故障,事后都可以用任何一个镜 像出来的本地仓库恢复。因为每一次的提取操作,实际上都是一次对代码仓库的完整备份。 更进一步,许多这类系统都可以指定和若干不同的远端代码仓库进行交互。借此,你就可以在同一个...
- 下一篇
图解定时任务线程池
线程池概念 我们上篇文章分析了ThreadPoolExecutor,如果要用一句话说明它的主要优势,就是线程置换。还有Executors工具类,极大的简化了研发人员工作。 我用一个图重复描述下线程池概念。多生产-多消费模型。 生产者将线程任务丢进线程池中,生产者就就结束了。 线程池控制消费者消费元素,消费者可以是1个或者多个,取决于线程池参数corePoolSize和maxPoolSize设置。 阻塞队列是用来装生产者丢进去的线程任务,如ArrayBlockingQueue,LinkedBlockingQueue,DelayedQueue等。如果生产者生产能力超过消费者消费能力,如果阻塞队列有长度限制并且超过队列长度线程池会执行饱和策略,如果队列没有长度限制,可也能出现OOM哦,因为线程任务可能把内存都撑爆了,这也是面试常考点哦! 详细概念可以翻看我上一篇文章《线程池面试必考问题》。 定时任务延时原理 还记得我们上面说的阻塞队列吗?定时任务线程池底层使用DelayedQueue实现的,这种延迟队列有一个最大的特点:按时出队列,大家都考过驾照吧,科目三考试的时候都是车上坐的是4个人,假设...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,CentOS7官方镜像安装Oracle11G