常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
桶排序概念
桶排序 （Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间
o(n)
。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。
排序步骤：
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来
动图展示：
静图展示：
代码实现
package sort;
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public static void main(String[] args) {
int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
bucketSort(arr);
//分桶后结果为:[[3, 9], [], [21, 25], [29], [37], [43, 49]]
}
public static void bucketSort(int[] arr) {
// 大的当小的，小的当大的
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
// 找出最小最大值
for (int i=0, len=arr.length; i<len; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
// 创建初始的桶
int bucketNum = (max - min)/arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
// 这一步是不可缺少的，上面的初始化只初始化了一维列表。二维列表需额外初始化
for (int i=0; i<bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
for (int i=0, len=arr.length; i<len; i++) {
int num = (arr[i] - min)/arr.length; //相同的商在同一个桶中
bucketArr.get(num).add(arr[i]); //根据商的不同，放入不同的桶
}
for (int i=0; i<bucketArr.size(); i++) { //同一桶内，自己排序
Collections.sort(bucketArr.get(i));
}
System.out.println("分桶后结果为:"+bucketArr.toString());
}
}
时间复杂度
- 最优时间复杂度：o(n)
- 最坏时间复杂度：o(n^2)
- 稳定性：稳定
对于桶排序来说，分配过程的时间是O(n)；收集过程的时间为O(k) （采用链表来存储输入的待排序记录）。因此，桶排序的时间为
O(n+k)
。若桶个数m的数量级为O(n)，则桶排序的时间是线性的，最优即O(n)。
前面说的几大排序算法 ，大部分时间复杂度都是O(n2)，也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是：首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。其次待排序的元素都要在一定的范围内等等。