排序算法
我们前面已经介绍了 3 种最常见的排序算法&＃xff1a;
java 实现冒泡排序讲解
QuickSort 快速排序到底快在哪里&＃xff1f;
SelectionSort 选择排序算法详解(java 实现)
然而天下排序千千万&＃xff0c;今天老马就和大家一起把最常见的几种都学习一遍。
堆排序(英语&＃xff1a;Heapsort)是指利用堆这种数据结构所设计的一种排序算法。
堆是一个近似完全二叉树的结构&＃xff0c;并同时满足堆的性质&＃xff1a;即子节点的键值或索引总是小于(或者大于)它的父节点。
基础知识 JCIP-11-二叉堆
若以升序排序说明&＃xff0c;把数组转换成最大堆(Max-Heap Heap)&＃xff0c;这是一种满足最大堆性质(Max-Heap Property)的二叉树&＃xff1a;对于除了根之外的每个节点i, A[parent(i)] ≥ A[i]。
堆是具有以下性质的完全二叉树&＃xff1a;每个结点的值都大于或等于其左右孩子结点的值&＃xff0c;称为大顶堆&＃xff1b;或者每个结点的值都小于或等于其左右孩子结点的值&＃xff0c;称为小顶堆。如下图&＃xff1a;
重复从最大堆取出数值最大的结点(把根结点和最后一个结点交换&＃xff0c;把交换后的最后一个结点移出堆)&＃xff0c;并让残余的堆维持最大堆性质。
输入图片说明
同时&＃xff0c;我们对堆中的结点按层进行编号&＃xff0c;将这种逻辑结构映射到数组中就是下面这个样子:
输入图片说明
通常堆是通过一维数组来实现的。
在数组起始位置为0的情形中&＃xff1a;
则父节点和子节点的位置关系如下&＃xff1a;
(01) 索引为i的左孩子的索引是 (2*i&＃43;1);
(02) 索引为i的左孩子的索引是 (2*i&＃43;2);
(03) 索引为i的父结点的索引是 floor((i-1)/2);
堆节点的访问
在堆的数据结构中&＃xff0c;堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。
堆中定义以下几种操作&＃xff1a;
最大堆调整(Max Heapify)&＃xff1a;将堆的末端子节点作调整&＃xff0c;使得子节点永远小于父节点
创建最大堆(Build Max Heap)&＃xff1a;将堆中的所有数据重新排序
堆排序(HeapSort)&＃xff1a;移除位在第一个数据的根节点&＃xff0c;并做最大堆调整的递归运算
这个图解来自 图解排序算法(三)之堆排序&＃xff0c;画的非常漂亮。
将待排序序列构造成一个大顶堆&＃xff0c;此时&＃xff0c;整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换&＃xff0c;此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆&＃xff0c;这样会得到n个元素的次小值。如此反复执行&＃xff0c;便能得到一个有序序列了。
将给定无序序列构造成一个大顶堆(一般升序采用大顶堆&＃xff0c;降序采用小顶堆)。
a. 假设给定无序序列结构如下
输入图片说明
b. 此时我们从最后一个非叶子结点开始(叶子结点自然不用调整&＃xff0c;第一个非叶子结点 arr.length/2-1&＃61;5/2-1&＃61;1&＃xff0c;也就是下面的6结点)&＃xff0c;从左至右&＃xff0c;从下至上进行调整。
输入图片说明
c. 找到第二个非叶节点4&＃xff0c;由于[4,9,8]中9元素最大&＃xff0c;4和9交换。
输入图片说明
d. 这时&＃xff0c;交换导致了子根[4,5,6]结构混乱&＃xff0c;继续调整&＃xff0c;[4,5,6]中6最大&＃xff0c;交换4和6。
输入图片说明
此时&＃xff0c;我们就将一个无序的序列构造成了一个大顶堆。
将堆顶元素与末尾元素进行交换&＃xff0c;使末尾元素最大。
然后继续调整堆&＃xff0c;再将堆顶元素与末尾元素交换&＃xff0c;得到第二大元素。如此反复进行交换、重建、交换。
a. 将堆顶元素9和末尾元素4进行交换
输入图片说明
b. 重新调整结构&＃xff0c;使其继续满足堆定义
输入图片说明
c. 再将堆顶元素8与末尾元素5进行交换&＃xff0c;得到第二大元素8.
输入图片说明
后续过程&＃xff0c;继续进行调整&＃xff0c;交换&＃xff0c;如此反复进行&＃xff0c;最终使得整个序列有序
输入图片说明
再简单总结下堆排序的基本思路&＃xff1a;
a. 将无需序列构建成一个堆&＃xff0c;根据升序降序需求选择大顶堆或小顶堆;
b. 将堆顶元素与末尾元素交换&＃xff0c;将最大元素"沉"到数组末端;
c. 重新调整结构&＃xff0c;使其满足堆定义&＃xff0c;然后继续交换堆顶元素与当前末尾元素&＃xff0c;反复执行调整&＃43;交换步骤&＃xff0c;直到整个序列有序。
为了和前面的逻辑保持一致&＃xff0c;我们暂时依然使用 list 去实现这个堆排序。
package com.github.houbb.sort.core.api;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import com.github.houbb.sort.core.util.InnerSortUtil;import java.util.List;/** * 堆排序 * * &＃64;author binbin.hou * &＃64;since 0.0.4 */public class HeapSort extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(HeapSort.class); &＃64;Override &＃64;SuppressWarnings("all") protected void doSort(List> original) { final int maxIndex &＃61; original.size() - 1; /* * 第一步&＃xff1a;将数组堆化 * beginIndex &＃61; 第一个非叶子节点。 * 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。 * 叶子节点可以看作已符合堆要求的节点&＃xff0c;根节点就是它自己且自己以下值为最大。 */ int beginIndex &＃61; original.size() / 2 - 1; for (int i &＃61; beginIndex; i >&＃61; 0; i--) { maxHeapify(original, i, maxIndex); } /* * 第二步&＃xff1a;对堆化数据排序 * 每次都是移出最顶层的根节点A[0]&＃xff0c;与最尾部节点位置调换&＃xff0c;同时遍历长度 - 1。 * 然后从新整理被换到根节点的末尾元素&＃xff0c;使其符合堆的特性。 * 直至未排序的堆长度为 0。 */ for (int i &＃61; maxIndex; i > 0; i--) { InnerSortUtil.swap(original, 0, i); maxHeapify(original, 0, i - 1); } } /** * 调整索引为 index 处的数据&＃xff0c;使其符合堆的特性。 * * &＃64;param list 列表 * &＃64;param index 需要堆化处理的数据的索引 * &＃64;param len 未排序的堆(数组)的长度 * &＃64;since 0.0.4 */ &＃64;SuppressWarnings("all") private void maxHeapify(final List list, int index, int len) { int li &＃61; (index * 2) &＃43; 1; // 左子节点索引 int ri &＃61; li &＃43; 1; // 右子节点索引 int cMax &＃61; li; // 子节点值最大索引&＃xff0c;默认左子节点。 // 左子节点索引超出计算范围&＃xff0c;直接返回。 if (li > len) { return; } // 先判断左右子节点&＃xff0c;哪个较大。 if (ri <&＃61; len && InnerSortUtil.gt(list, ri, li)) { cMax &＃61; ri; } if (InnerSortUtil.gt(list, cMax, index)) { InnerSortUtil.swap(list, cMax, index); // 如果父节点被子节点调换&＃xff0c; maxHeapify(list, cMax, len); // 则需要继续判断换下后的父节点是否符合堆的特性。 } }}
插入排序(英语&＃xff1a;Insertion Sort)是一种简单直观的排序算法。
它的工作原理是通过构建有序序列&＃xff0c;对于未排序数据&＃xff0c;在已排序序列中从后向前扫描&＃xff0c;找到相应位置并插入。
插入排序在实现上&＃xff0c;通常采用in-place排序(即只需用到 O(1) 的额外空间的排序)&＃xff0c;因而在从后向前扫描过程中&＃xff0c;需要反复把已排序元素逐步向后挪位&＃xff0c;为最新元素提供插入空间。
一般来说&＃xff0c;插入排序都采用in-place在数组上实现。具体算法描述如下&＃xff1a;
排序
package com.github.houbb.sort.core.api;import com.github.houbb.heaven.annotation.ThreadSafe;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import com.github.houbb.sort.core.util.InnerSortUtil;import java.util.List;/** * 冒泡排序 * &＃64;author binbin.hou * &＃64;since 0.0.5 */&＃64;ThreadSafepublic class InsertSort extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(InsertSort.class); &＃64;Override &＃64;SuppressWarnings("all") public void doSort(List original) { for(int i &＃61; 1; i &＃61; 0 && InnerSortUtil.gt(original, j, current)) { // 元素向后移动一位 original.set(j&＃43;1, original.get(j)); j--; } // 将元素插入到对应的位置 original.set(j&＃43;1, current); } }}
也称递减增量排序算法&＃xff0c;是插入排序的一种更高效的改进版本。
希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的&＃xff1a;
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。
这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序&＃xff0c;算法的最后一步就是普通的插入排序&＃xff0c;但是到了这步&＃xff0c;需排序的数据几乎是已排好的了(此时插入排序较快)。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序(冒泡排序或插入排序)&＃xff0c;可能会进行n次的比较和交换才能将该数据移至正确位置。
而希尔排序会用较大的步长移动数据&＃xff0c;所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现&＃xff1a;将数组列在一个表中并对列排序(用插入排序)。重复这过程&＃xff0c;不过每次用更长的列来进行。最后整个表就只有一列了。
将数组转换至表是为了更好地理解这算法&＃xff0c;算法本身仅仅对原数组进行排序(通过增加索引的步长&＃xff0c;例如是用i &＃43;&＃61; step_size而不是i&＃43;&＃43;)。
例如&＃xff0c;假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]&＃xff0c;如果我们以步长为5开始进行排序&＃xff0c;我们可以通过将这列表放在有5列的表中来更好地描述算法&＃xff0c;这样他们就应该看起来是这样&＃xff1a;
13 14 94 33 8225 59 94 65 2345 27 73 25 3910
然后我们对每列进行排序&＃xff1a;
10 14 73 25 2313 27 94 33 3925 59 94 65 8245
将上述四行数字&＃xff0c;依序接在一起时我们得到&＃xff1a;[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。
这时10已经移至正确位置了&＃xff0c;然后再以3为步长进行排序&＃xff1a;
10 14 7325 23 1327 94 3339 25 5994 65 8245
排序之后变为&＃xff1a;
10 14 1325 23 3327 25 5939 65 7345 94 8294
最后以1步长进行排序(此时就是简单的插入排序了)。
Donald Shell 最初建议步长选择为 n/2 并且对步长取半直到步长达到1。
虽然这样取可以比 O(n^2) 类的算法(插入排序)更好&＃xff0c;但这样仍然有减少平均时间和最差时间的余地。
已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,…)&＃xff0c;
另一个在大数组中表现优异的步长序列是(斐波那契数列除去0和1将剩余的数以黄金分割比的两倍的幂进行运算得到的数列)&＃xff1a;
(1, 9, 34, 182, 836, 4025, 19001, 90358, 428481, 2034035, 9651787, 45806244, 217378076, 1031612713,…)
这里为了简单&＃xff0c;我们步长直接选择列表长度的一半&＃xff0c;并且依次折半。
import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import com.github.houbb.sort.core.util.InnerSortUtil;import java.util.List;/** * 希尔排序 * * &＃64;author binbin.hou * &＃64;since 0.0.6 */public class ShellSort extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(ShellSort.class); &＃64;Override &＃64;SuppressWarnings("all") protected void doSort(List> original) { // 步长从大到小 for(int step &＃61; original.size()/2; step > 0; step /&＃61; 2) { // 从第 step 个元素&＃xff0c;逐个执行插入排序 for(int i &＃61; step; i &＃61; 0) && InnerSortUtil.lt(original, j, j-step)) { // 执行交换 InnerSortUtil.swap(original, j, j-step); if(log.isDebugEnabled()) { log.debug("step: {}, j: {}, j-step: {}, list: {}", step, j, j-step, original); } // 更新步长 j -&＃61; step; } } } }}
整体实现也不难&＃xff0c;大家可以回顾下 插入排序
这里为了便于大家理解&＃xff0c;我们特意添加了日志。
是创建在归并操作上的一种有效的排序算法&＃xff0c;效率为 O(nlogn)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。
该算法是采用分治法(Divide and Conquer)的一个非常典型的应用&＃xff0c;且各层分治递归可以同时进行。
采用分治法:
分割&＃xff1a;递归地把当前序列平均分割成两半。
集成&＃xff1a;在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)。
实际上代码实现也不难&＃xff0c;不过递归多多少少让人看起来不太习惯。
我们后面会结合测试日志&＃xff0c;再进行讲解。
package com.github.houbb.sort.core.api;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import java.util.ArrayList;import java.util.List;/** * 归并排序-递归实现 * * &＃64;author binbin.hou * &＃64;since 0.0.7 */public class MergeRecursiveSort extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(MergeRecursiveSort.class); &＃64;Override &＃64;SuppressWarnings("all") protected void doSort(List> original) { // 存放归并的结果 // 直接将数组填满&＃xff0c;避免 set 出现越界 List> resultList &＃61; new ArrayList<>(original); sortRecursive(original, resultList, 0, original.size()-1); } /** * 递归排序 * &＃64;param originalList 原始列表 * &＃64;param resultList 存放结果的列表 * &＃64;param startIx 开始 * &＃64;param endIx 结果 * &＃64;since 0.0.7 */ &＃64;SuppressWarnings("all") private void sortRecursive(List originalList, List resultList, int startIx, int endIx) { // 循环结束 if(startIx >&＃61; endIx) { return; } // 找到中间位置&＃xff0c;将列表一分为二 int midIx &＃61; (startIx&＃43;endIx) / 2; int leftStart &＃61; startIx; int leftEnd &＃61; midIx; int rightStart &＃61; midIx&＃43;1; int rightEnd &＃61; endIx; if(log.isDebugEnabled()) { log.debug("拆分&＃xff1a;ls: {}, le: {}, rs: {}, re: {}", leftStart, leftEnd, rightStart, rightEnd); } // 递归调用 sortRecursive(originalList, resultList, leftStart, leftEnd); sortRecursive(originalList, resultList, rightStart, rightEnd); if(log.isDebugEnabled()) { log.debug("操作&＃xff1a;ls: {}, le: {}, rs: {}, re: {}", leftStart, leftEnd, rightStart, rightEnd); } // 这里需要通过 k 记录一下开始的位置 int k &＃61; startIx; while (leftStart <&＃61; leftEnd && rightStart <&＃61; rightEnd) { //相对小的元素放入到合并空间&＃xff0c;并移动指针到下一位置 Comparable left &＃61; (Comparable) originalList.get(leftStart); Comparable right &＃61; (Comparable) originalList.get(rightStart); // 左边较小&＃xff0c;则放入合并空间 if(left.compareTo(right)
相信很多小伙伴都知道迭代可以使得代码变得简洁&＃xff0c;但是会让调试和理解变得复杂。
我们来一起学习一下迭代的实现方式。
原理如下(假设序列共有 n 个元素)&＃xff1a;
相对递归&＃xff0c;这个代码就要显得复杂很多。
不过这种迭代的方式性能更好&＃xff0c;实现如下。
package com.github.houbb.sort.core.api;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import com.github.houbb.sort.core.util.InnerSortUtil;import java.util.ArrayList;import java.util.List;/** * 归并排序-迭代实现 * * &＃64;author binbin.hou * &＃64;since 0.0.7 */public class MergeSort extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(MergeSort.class); &＃64;Override protected void doSort(List> original) { // 存放归并的结果 // 直接将数组填满&＃xff0c;避免 set 出现越界 List> resultList &＃61; new ArrayList<>(original); //起始&＃xff0c;子序列长度为1。对长度为1的序列进行两两合并 int k &＃61; 1; final int length &＃61; original.size(); while (k (len-2*k&＃43;1),所以根本没有进入while循环 while (i
计数排序(Counting sort)是一种稳定的线性时间排序算法。
该算法于1954年由 Harold H. Seward 提出。
通过计数将时间复杂度降到了 O(N)。
package com.github.houbb.sort.core.api;import com.github.houbb.heaven.annotation.ThreadSafe;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import com.github.houbb.sort.core.util.InnerSortUtil;import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * 计数排序 * * &＃64;author binbin.hou * &＃64;since 0.0.8 */&＃64;ThreadSafepublic class CountingSortBasic extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(CountingSortBasic.class); &＃64;Override &＃64;SuppressWarnings("all") public void doSort(List original) { //1. 获取最大的元素 int max &＃61; Integer.MIN_VALUE; for (Object object : original) { Integer integer &＃61; (Integer) object; max &＃61; Math.max(max, integer); } //2. 构建 count 列表 int[] counts &＃61; new int[max &＃43; 1]; //3.遍历原数组中的元素&＃xff0c;以原数组中的元素作为count数组的索引&＃xff0c;以原数组中的元素出现次数作为count数组的元素值。 for (Object object : original) { Integer integer &＃61; (Integer) object; counts[integer]&＃43;&＃43;; } //4. 结果构建 int index &＃61; 0; // 遍历计数数组&＃xff0c;将计数数组的索引填充到结果数组中 for (int i &＃61; 0; i 0) { // i 实际上就是元素的值 // 从左到右遍历&＃xff0c;元素自然也就排序好了。 // 相同的元素会出现多次&＃xff0c;所以才需要循环。 original.set(index&＃43;&＃43;, i); counts[i]--; if(log.isDebugEnabled()) { log.debug("结果数组&＃xff1a;{}", original); } } } }}
实际上我们创建一个比最大元素还要大1的数组&＃xff0c;只是为了放下所有的元素而已。
但是它有一个缺陷&＃xff0c;那就是存在空间浪费的问题。
比如一组数据{101,109,102,110}&＃xff0c;其中最大值为110&＃xff0c;按照基础版的思路&＃xff0c;我们需要创建一个长度为111的计数数组&＃xff0c;但是我们可以发现&＃xff0c;它前面的[0,100]的空间完全浪费了&＃xff0c;那怎样优化呢&＃xff1f;
将数组长度定为 max-min&＃43;1&＃xff0c;即不仅要找出最大值&＃xff0c;还要找出最小值&＃xff0c;根据两者的差来确定计数数组的长度。
import com.github.houbb.heaven.annotation.ThreadSafe;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import java.util.Arrays;import java.util.List;/** * 计数排序 * * &＃64;author binbin.hou * &＃64;since 0.0.8 */&＃64;ThreadSafepublic class CountingSort extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(CountingSort.class); &＃64;Override &＃64;SuppressWarnings("all") public void doSort(List original) { //1. 获取最大、最小的元素 int max &＃61; Integer.MIN_VALUE; int min &＃61; Integer.MAX_VALUE; for (Object object : original) { Integer integer &＃61; (Integer) object; max &＃61; Math.max(max, integer); min &＃61; Math.min(min, integer); } //2. 构建 count 列表 int[] counts &＃61; new int[max-min &＃43; 1]; //3.遍历原数组中的元素&＃xff0c;以原数组中的元素作为count数组的索引&＃xff0c;以原数组中的元素出现次数作为count数组的元素值。 for (Object object : original) { Integer integer &＃61; (Integer) object; // 元素要减去最小值&＃xff0c;再作为新索引 counts[integer-min]&＃43;&＃43;; } if(log.isDebugEnabled()) { log.debug("counts.length: {}", counts.length); } //4. 结果构建 int index &＃61; 0; // 遍历计数数组&＃xff0c;将计数数组的索引填充到结果数组中 for (int i &＃61; 0; i 0) { // i 实际上就是元素的值 // 从左到右遍历&＃xff0c;元素自然也就排序好了。 // 相同的元素会出现多次&＃xff0c;所以才需要循环。 // 这里将减去的最小值统一加上 original.set(index&＃43;&＃43;, i&＃43;min); counts[i]--; if(log.isDebugEnabled()) { log.debug("结果数组&＃xff1a;{}", original); } } } }}
这个算法的本质是什么呢&＃xff1f;
个人理解只需要保证两点&＃xff1a;
(1)每一个元素&＃xff0c;都有自己的一个元素位置
(2)相同的元素&＃xff0c;次数会增加。
算法的巧妙之处在于直接利用数值本身所谓索引&＃xff0c;直接跳过了排序比较&＃xff1b;利用技数&＃xff0c;解决了重复数值的问题。
这个算法的巧妙之处&＃xff0c;同时也是对应的限制&＃xff1a;那就是只能直接比较数字。如果是字符串呢&＃xff1f;
我最初的想法就是可以使用类似于 HashMap 的数据结构。这样可以解决元素过滤&＃xff0c;次数统计的问题。
但是无法解决排序问题。
当然了&＃xff0c;如果使用 TreeMap 就太赖皮了&＃xff0c;因为本身就是利用了树进行排序。
我们这里使用 TreeMap 主要有下面的目的&＃xff1a;
(1)让排序不局限于数字。
(2)大幅度降低内存的浪费&＃xff0c;不多一个元素&＃xff0c;也不少一个元素。
思想实际上依然是技术排序的思想。
package com.github.houbb.sort.core.api;import com.github.houbb.heaven.annotation.ThreadSafe;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import java.util.List;import java.util.Map;import java.util.TreeMap;/** * 计数排序-TreeMap * * &＃64;author binbin.hou * &＃64;since 0.0.8 */&＃64;ThreadSafepublic class CountingSortTreeMap extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(CountingSortTreeMap.class); &＃64;Override &＃64;SuppressWarnings("all") public void doSort(List original) { TreeMap countMap &＃61; new TreeMap<>(); // 初始化次数 for (Object object : original) { Comparable comparable &＃61; (Comparable) object; Integer count &＃61; countMap.get(comparable); if(count &＃61;&＃61; null) { count &＃61; 0; } count&＃43;&＃43;; countMap.put(comparable, count); } //4. 结果构建 int index &＃61; 0; // 遍历计数数组&＃xff0c;将计数数组的索引填充到结果数组中 for (Map.Entry entry : countMap.entrySet()) { int count &＃61; entry.getValue(); Comparable key &＃61; entry.getKey(); while (count > 0) { // i 实际上就是元素的值 // 从左到右遍历&＃xff0c;元素自然也就排序好了。 // 相同的元素会出现多次&＃xff0c;所以才需要循环。 original.set(index&＃43;&＃43;, key); count--; } } }}
或所谓的箱排序&＃xff0c;是一个排序算法&＃xff0c;工作的原理是将数组分到有限数量的桶里。
每个桶再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。
桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候&＃xff0c;桶排序使用线性时间 O(n)。
桶排序是计数排序的扩展版本&＃xff0c;计数排序可以看成每个桶只存储相同元素&＃xff0c;而桶排序每个桶存储一定范围的元素&＃xff0c;通过映射函数&＃xff0c;将待排序数组中的元素映射到各个对应的桶中&＃xff0c;对每个桶中的元素进行排序&＃xff0c;最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀&＃xff0c;否则当所有数据集中在同一个桶中时&＃xff0c;桶排序失效。
桶排序以下列程序进行&＃xff1a;
算法
package com.github.houbb.sort.core.api;import com.github.houbb.heaven.annotation.ThreadSafe;import com.github.houbb.log.integration.core.Log;import com.github.houbb.log.integration.core.LogFactory;import java.util.ArrayList;import java.util.Collections;import java.util.List;/** * 桶排序 * * &＃64;author binbin.hou * &＃64;since 0.0.9 */&＃64;ThreadSafepublic class BucketSort extends AbstractSort { private static final Log log &＃61; LogFactory.getLog(BucketSort.class); &＃64;Override &＃64;SuppressWarnings("all") public void doSort(List original) { final int step &＃61; 10; // 计算最小值 int min &＃61; Integer.MAX_VALUE; int max &＃61; Integer.MIN_VALUE; for(Object object : original) { Integer integer &＃61; (Integer) object; min &＃61; Math.min(min, integer); max &＃61; Math.max(max, integer); } //2. 计算桶的个数 int bucketNum &＃61; (max-min) / step &＃43; 1;; //2.1 初始化临时列表 List> tempList &＃61; new ArrayList<>(bucketNum); for(int i &＃61; 0; i ()); } //3. 将元素放入桶中 // 这里有一个限制&＃xff1a;要求元素必须一个左边的桶元素&＃xff0c;要小于右边的桶。 // 这就限制了只能是数字类的比较&＃xff0c;不然没有范围的概念 for(Object o : original) { Integer integer &＃61; (Integer) o; int index &＃61; (integer-min) / step; tempList.get(index).add(integer); } // 4. 针对单个桶进行排序 // 可以选择任意你喜欢的算法 for(int i &＃61; 0; i integers &＃61; tempList.get(i); for(Integer val : integers) { original.set(index&＃43;&＃43;, val); } } }}
为了便于大家学习&＃xff0c;上面的排序已经开源&＃xff0c;开源地址&＃xff1a;
https://github.com/houbb/sort
欢迎大家 fork/star&＃xff0c;鼓励一下作者~~
希望本文对你有帮助&＃xff0c;如果有其他想法的话&＃xff0c;也可以评论区和大家分享哦。
各位极客的点赞收藏转发&＃xff0c;是老马持续写作的最大动力&＃xff01;
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 