摘要：实际上，桶排序的应用场景十分的有限，对数据的要求比较苛刻。极端情况下，如果数据全部划分到一个桶内，就变成了非线性排序了。
1. 回顾
前面已经说完了几种非线性排序，它们分别是时间复杂度为 O(n2) 、适合小规模数据的冒泡排序、选择排序、插入排序，和应用较广泛的时间复杂度为 O(nlogn) 的希尔排序、归并排序、快速排序。其实这几种排序都有一个特性，那就是它们都是基于数据的比较和移动，而今天介绍的这几种线性排序，他们的时间复杂度都是 O(n) ，因为不涉及到数据的比较和移动。
2. 桶排序
桶排序的思路是：将要排序的数据按照一定的范围划分到有序的桶内，在桶内进行排序，然后依次从桶中将数据取出来，这样整个数据就有序了。
例如我们要排序一组大小在 [0 - 50] 的数据，可以划分 5 个桶，每个桶存放的数据范围为：[1 - 10]、[11-20]、[21 - 30] 以此类推，就像下图这样：
然后在将桶内的数据排序，依次取出来，整个数据就有序了。
实际上，桶排序的应用场景十分的有限，对数据的要求比较苛刻。首先，它要求每个桶的数据范围是有序的，就像上面那样依次排列，这样才能够保证从桶中取出的数据仍然保持有序，其次，要保证数据较为均匀的划分到各个桶中，如果出现数据集中到某个或几个桶内，那么时间复杂度就会下降。极端情况下，如果数据全部划分到一个桶内，就变成了非线性排序了。
下面我模拟了一个简单的桶排序：
public class BucketSort {
//测试场景：数组中有10000个数据，范围在0-100000之间
//使用100个桶，每个桶存放的数据范围为：0-999, 1000-1999, 2000-2999，依次类推
public static void bucketSort(int[] data){
//新建100个桶，使用ArrayList作为桶
ArrayList> buckets = new ArrayList<>(100);
for (int i = 0; i < 100; i++) {
buckets.add(new ArrayList<>());
}
//遍历数组，将数据放置到桶中
for (int i = 0; i < data.length; i++) {
buckets.get(data[i] / 1000).add(data[i]);
}
//在桶内部进行排序
int k = 0;
for (int i = 0; i < buckets.size(); i++) {
ArrayList list = buckets.get(i);
Integer[] integers = list.toArray(new Integer[10]);
Arrays.sort(integers);
//拷贝到data中
for (int j = 0; j < integers.length; j++) {
data[k ++] = integers[j];
}
}
}
}
2. 计数排序
计数排序其实是桶排序的一种特殊情况，假如要排序的数据范围不大，例如为 n ，那么我们可以划分 n 个桶，每个桶内存放数值相同的数据，然后再遍历取出来，这样整个数据就有序了。
例如我们需要根据年龄给 10 万人排序，年龄的范围其实不大，我们可以假设年龄最小为 0，最大为 120，那么我们直接划分 121 个桶，遍历数组，将年龄相同的数据存放到同一个桶中，然后取出来，就完成了排序。是不是很简单呢？
这里我就不代码演示了，和上面的桶排序非常的类似，就是没有了桶内排序的这个部分，你可以自己尝试写一下。
3. 基数排序
再来看看基数排序，假如我们要对 10 万个手机号码进行排序，应该怎么做呢？手机号码有 11 位，太长，不适合用桶排序或是计数排序。借助于稳定排序，我们可以从号码的最后一位开始比较，比较 11 次。因为借助的是稳定排序，所以前面的排序顺序不会被打乱，我用了一个简单的字符数组来模拟这个过程：
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/73822.html
摘要：数据结构程序数据结构算法数据结构基本概念数据的逻辑结构反映数据元素之间的关系的数据元素集合的表示。这两部分信息组成数据元素的存储映象，称为结点。 本文涉及更多的是概念，代码部分请参考之前写过的 2 篇博客 基于 Javascript 的排序算法 基于 javascript 的基本数据结构和查找算法 本文主要是基础的数据结构和算法概念，可能部分地方会涉及更高级的算法和算法，具体内容以...
摘要：归并排序归并排序，或，是创建在归并操作上的一种有效的排序算法，效率为大符号。以此类推，直到所有元素均排序完毕。与快速排序一样都由托尼霍尔提出的，因而也被称为霍尔选择算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);编译：周素云、蒋宝尚 学会了Python基础知识，想进阶一下，那就来点算法吧！毕竟编程语言只...
摘要：数据结构试题前言这里是数据结构系列文章，主要介绍计算机二级考试中的涉及到数据结构的知识点数据结构在计算机科学中处处都有存在，例如编译系统要使用栈散列表语法树等操作系统要使用队列存储管理表目录树等等。 数据结构 试题前言这里是 数据结构 系列文章，主要介绍计算机二级考试中的涉及到数据结构的知识点 /数据结构在计算...
摘要：之所以把计数排序桶排序基数排序放在一起比较，是因为它们的平均时间复杂度都为。动画计数排序思想找出待排序的数组中最大和最小的元素。桶排序计数排序能派上用场吗手机号码有位，范围太大，显然不适合用这两种排序算法。 showImg(https://segmentfault.com/img/bVbuF9e?w=900&h=500); 1. 前言 算法为王。 想学好前端，先练好内功，只有内功深厚者...
摘要：我们现在来看二分搜索算法的两种变形插值搜索和指数搜索。插值搜索是对二分搜索算法的改进，插值搜索可以基于搜索的值选择到达不同的位置。 预警 在本篇文章中，将为各位老铁介绍不同的搜索算法以及它们的复杂度。因为力求通俗易懂，所以篇幅可能较长，大伙可以先Mark下来，每天抽时间看一点理解一点。本文配套的Github Repo，欢迎各位老铁star，会一直更新的。 开篇 和排序类似，搜索或者叫做...
阅读 3330·2021-11-23 10:13
阅读 657·2021-09-22 16:01
阅读 814·2021-09-09 09:33
阅读 482·2021-08-05 09:58
阅读 1621·2019-08-30 11:14
阅读 1760·2019-08-30 11:02
阅读 3152·2019-08-29 16:28
阅读 1370·2019-08-29 16:09
