设为首页 加入收藏

TOP

Java 中常见的排序算法
2019-08-13 05:39:21 】 浏览:11
Tags:Java 常见 排序 算法

好了,每次写博客都要废话一堆,自我检讨,但是不想改变,接下来小编介绍几种创建的排序算法以及他们的Java实现。


??原理:从第一个元素开始,和它相邻的比较,如果前面一个元素大于后面一个元素,就把他们互换位置。
??原理图:
Java  中常见的排序算法
?? 代码实现:


?? 增强版冒泡排序:


??原理:从第一个位置开始,将他与后面的所有元素比较,如果前面大于后面的,就交换位置。
??原理图:
Java  中常见的排序算法
??代码实现:


??原理:从第二个元素位置开始,将他与他之前的元素比较,如果比之前的元素小,就将他插入到,那个元素的前面。
??原理图:
Java  中常见的排序算法
??代码实现:


??原理:先选取一个基准点,作用:基准点左侧小于基准点的数据 基准点右侧放的数据都是大于基准点的数据。基准点:最常用的基准点选第一个,最终一个大数组不停的进行查分 拆分的最终结果每个数组只有一个元素。
??原理图:
Java  中常见的排序算法
解释:大循环中有两个循环,一个是从右往左,找比基准点小的,一个是从左往右找比基准点大的(找到之后,与基准点交换位置)。最终大循环,在left>=right时结束。
(2) 快排拆分:
Java  中常见的排序算法
解释:使用递归的方式,将数组左右两边一次次拆分,直到left>=right时,递归结束。
??代码实现:


注意:了解快速排序有助于了解MR的map-reduce过程,因为在MRmap阶段环形缓冲区满了之后,会将数据溢写到文件中,这个过程中就是使用了快速排序。


??原理:对一个已有数组进行排序,那么就新建一个数组,数组长度为数组中元素的最大值+1。并把已有数组中的元素,对应上新建数组的下标,放入里面,新建数组的元素为,已有数组中元素的出现次数。
??原理图:
Java  中常见的排序算法
解释:新创建一个数组,长度为需要排序的数组的最大值+1,遍历数组,将数组中的值分别找到新数组的索引,将索引处的元素+1,最后,遍历输出新数组的下标(只输出相应的值>0的下标,并且值为多少就输出几次)。
??代码实现:


注意:了解计数排序,有助于了解hbase的布隆过滤器,布隆过滤器的特点就是,我说没有就没有,我说有不一定有(有一定的误判率)。


原理:针对多个有序的数据集进行排序。(时间复杂度:n*logN)
归并排序有两个阶段:
一个是归:将一个数据集拆分到每一个小的数据集只有一个元素。
实现一个数据集的归


一个是并:将两个有序的数据集,合并成为一个有序的大数据集。
实现两个有序数据集的并:


完整代码实现:


注意:在MR程序中,其中有两个阶段使用到了归并,一个是在缓冲区溢写小文件时,最后会将多个小文件归并成一个大文件,另一个则是在reduce拉去map处理的数据到本地是会生成很多小文件,此时也会做一次归并。


??原理:在已经排好序的基础上,将数组元素折半查找。
??原理图:
Java  中常见的排序算法


??代码实现:


试试



编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C语言二维数组(解引用、指针数组.. 下一篇JPA的多表复杂查询