桶排序,计数排序,基数排序都不是基于比较的排序,也就是说他们与样本的实际数据情况有很大关系,实际中不经常使用,其时间复杂度都为O(N),额外空间复杂度都为O(N),而且都是稳定的排序

桶排序

桶排序就是一个概念,不是具体的一种排序方法,其中的**基数排序和计数排序**才是桶排序的具体实现.举例: 现在有一个数组arr,里面存放着从0-60的共计61个元素,我们可以拿一个同样长度为61的新数组countArr,用来记录arr数组中每个数字出现的次数,最后遍历数组countArr就可以知道每个数出现了几次,就从0开始输出几次就好了,比如说1出现了3次,就输出111就可以了.

计数排序

计数排序就是有多少个数对应放多少个桶,然后统计对应数出现的个数,最后遍历输出,不过这个很不实用,要是数据量太大了,就贼慢,所以一般桶的数量不会很多,就是这么个意思,理解理解就好了.

基数排序(后面再说)

补充问题

1. 案例(很重要): 给定一个无序数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度为**O(N)**,且要求**不能用非基于比较**的排序. * 举例: 数组array: [3,1,6,2,7] 排序后: [1,2,3,6,7] 返回最大差值: 3 则本题解为 : 3 * 解法: 借用桶概念,但是没用桶排序 . * 代码: **[案例代码](https://github.com/fanfan999/AlgorithmsCodes/blob/master/SortingCodes/Max_Gap.java).** 2. 在这里要注意一个问题: int i = 0; int j = 0; i = i++; 此时的i是为0的. i = i + 1; j = ++j; 此时i和j都是等于1的,一定要想清楚啊!!! 3. 用数组实现固定大小的栈,越界就报错: 实现添加功能`push`,取出栈顶元素但是不删除功能`peek`,取出栈顶元素并删除`pop`这三个功能 * **[数组实现固定大小的栈代码](https://github.com/fanfan999/AlgorithmsCodes/blob/master/SortingCodes/MakeArrayAsStack.java).** 4. 用数组实现固定大小的队列,越界就报错: 实现添加功能`push`,取出队列首元素但是不删除功能`peek`,取出队列首元素并删除`poll`这三个功能 * **[数组实现固定大小的队列代码](https://github.com/fanfan999/AlgorithmsCodes/blob/master/SortingCodes/MakeArrayAsQueue.java).**