【桶排序】十大排序算法之桶排序,是属于【稳定】的排序算法。
目录
一、桶排序基本思想
二、桶排序代码实现
2.1、序列长度分桶
2.2、简单分桶
2.3、规约化分桶
一、桶排序基本思想
- 桶排序,是属于【非比较类】排序(其实我感觉也可以认为是半比较类排序,因为再对每个桶里面的元素排序时候,就可能采用比较类排序方式)。
- 桶排序,是属于【稳定】的排序算法。
- 桶排序的思想其实非常简单的:将数据均分为【k】个桶,然后将对于元素放入相应的桶里面,接着在单独对每一个桶里面的元素进行排序操作,所有桶排序完成之后,按照桶的顺序将所有元素输出,最终得到的序列就是排序完成的。
- 桶排序,其实很少会使用,但是这种思想需要理解,因为由桶排序的思想,衍生出了两个其他的排序方式:【计数排序】和【基数排序】。
- 桶排序,时间复杂度:【O(n+k)】,空间复杂度:【O(n+k)】。
- 桶排序的时间复杂度、空间复杂度不是绝对的,而是要根据采取哪种数据结构来判断。
- 桶排序有个特点,就是要想保证【时间复杂度】最好,就没有办法保证【空间复杂度】最好;相反地,要想保证【空间复杂度】最好,就没办法保证【时间复杂度】最好。
桶排序的使用场景
桶排序,针对那种海量数据,也就是数据量特别大的情况下,并且这些数据都满足某个特殊条件,那么这个时候,就可以考虑采用桶排序。
引用百度百科一个案例:
- 一年的全国高考考生人数为500 万,分数使用标准分,最低100 ,最高900 ,没有小数,要求对这500 万元素的数组进行排序。
- 这种情况其他就可以使桶排序,为什么呢???
- 因为数据量虽然有500万条,但是这些数据最终都是只会分布在【100到900】之间,也就是每个考生的分数只会在【100到900】之间,那么我们就可以按照【100到900】进行分桶,然后将500万条数据分别放入桶里面,即可排序完成。
什么是稳定的排序???
稳定排序:
- 如果排序数组中,存在相同的元素,假设存在两个元素【3】。
- 为了标识两个元素【3】的先后顺序,我们假设给它命名为:【3(1)】、【3(2)】。
- 其中括号里面的表示元素3出现的先后顺序。
- 如果结果排序之后,两个元素还是保持相同的顺序,即:【3(1)、3(2)】,那么我们就称这个排序是稳定的,否则就是不稳定的排序。
桶排序的基本思想
桶排序,最关键的就是将数据分桶,然后对每个桶里面的数据进行单独的排序操作,所有的桶排序完成之后,按照桶的顺序,依次从桶中取处所有的数据,此时形成的序列就是有序的序列。
桶排序基本思路:
- 待排序数组【arr】,求出数组中最大值【max】、最小值【mid】。
- 计算差值【diff = max - min】,设置分桶数量【bucketNum】(具体分多少个桶,视情况而定,如何保证分桶合理???)。
- 通过1,2两个步骤,可以计算出每个桶中的数据区间:【diff / bucketNum】。
- 初始化桶的数据结构,可以利用二维数组,可以利用链表等等。
- 遍历待排序数组【arr】,将其中每个数据元素按照某个映射规则,找到其对应哪个桶,然后放入这个桶里面即可。
- 遍历结束后,按照桶的顺序,依次取出桶里面的数据元素,那么此时形成的序列,就是排序完成的。
桶排序为什么属于稳定的排序???
看了上面桶排序的基本思想,可以知道桶排序在【分桶】操作过程后,我们需要单独对每个桶进行一次排序,那么这个排序我们就可以选择一个稳定的排序算法来实现,也就可以保证桶排序的最终排序是稳定的。
可以从这个网站查看桶排序的过程【数据结构和算法动态可视化 (Chinese) - VisuAlgo】。
二、桶排序代码实现
2.1、序列长度分桶
前面介绍完了桶排序的思想了,这里编写代码实现桶排序。
- 桶排序,如何分桶是关键,分多少个桶,以及如何确定分多少个桶???
- 这些都是需要考虑的问题,不同的分桶方式,可能会影响算法的效率,最直接的分桶就是直接通过【序列长度】作为桶的数量【bucketNum】,然后通过【max - min】除以【bucketNum】将数据放入不同的桶里面。
- 这种方式的缺点,如果数据有【n】个,那就需要分【n】个桶,显然空间复杂度太高了。
public class BucketSort {
public static void bucketSort(int[] nums) {
// 1、求最大值和最小值
int max = nums[0], min = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
// 计算差值: 最大值 - 最小值
int diff = max - min;
// 2、初始化桶: 按照序列长度分桶
int bucketNum = nums.length;
// 创建桶: 链表方式
List> bucket = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>()); // 初始化桶
}
// 3、遍历数组,将每个数据分桶存放
for (int i = 0; i < nums.length; i++) {
// 计算当前元素应该放入哪个桶里面
// diff / (bucketNum - 1): 表示每个桶保存多少数据的范围
// nums[i] - min: 因为第一个桶从[min,mid+k]开始,所以后面的元素都要减去min开始计算区间,相等于将min看作原点0
int index = (nums[i] - min) / (diff / (bucketNum - 1));
// 当前元素放入 index 桶里面
bucket.get(index).add(nums[i]);
}
// 4、对每个桶中元素单独进行排序操作
for (int i = 0; i < bucket.size(); i++) {
// 每个桶进行一次冒泡排序
bubbleSort(bucket.get(i));
}
// 5、按照桶的顺序,依次输出桶中元素
int index = 0;
for (int i = 0; i < bucket.size(); i++) {
List temp = bucket.get(i);
for (int j = 0; j < temp.size(); j++) {
nums[index++] = temp.get(j);
}
}
}
public static void bubbleSort(List nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums.get(j) > nums.get(j + 1)) {
// 交换元素
int temp = nums.get(j);
nums.set(j, nums.get(j + 1));
nums.set(j + 1, temp);
}
}
}
}
public static void main(String[] args) {
int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
System.out.println(Arrays.toString(nums));
bucketSort(nums);
System.out.println(Arrays.toString(nums));
}
}
2.2、简单分桶
第二种分桶方式:
- 按照【max - min】差值除以【10】再【加1】作为最终分桶的数量【bucketNum】。
- 公式:【bucketNum = (max - min) / 10 + 1;】
- 这种方式,相比较于2.1的方式,在某些情况下,可以很大程度上减少桶的数量。
- 例如:
- 100个待排序元素,并且假设最大值等于99,最小值等于2;
- 按照2.1的方式,直接分【100】个桶;
- 按照2.2的方式,【bucketNUm =(99-2)/ 10 + 1】直接分【10】个桶,减少了【10】倍。
- 当然了,这种分桶也不是绝对的,因为如果元素有100个,但是里面最大值等于10000,最小值是1,那么计算出来的分桶数量就是【1001】,显然还不如直接按照2.1方式进行分桶。
public class BucketSort {
// 简单分桶
public static void bucketSort(int[] nums) {
// 1、求最大值和最小值
int max = nums[0], min = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
// 计算差值: 最大值 - 最小值
int diff = max - min;
// 2、初始化桶: 按照简单分桶方式
int bucketNum = (max - min) / 10 + 1;
// 创建桶: 链表方式
List> bucket = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>()); // 初始化桶
}
// 3、遍历数组,将每个数据分桶存放
for (int i = 0; i < nums.length; i++) {
// 计算当前元素应该放入哪个桶里面
// diff / (bucketNum - 1): 表示每个桶保存多少数据的范围
// nums[i] - min: 因为第一个桶从[min,min + d]开始,所以后面的元素都要减去min开始计算区间,相等于将min看作原点0
int index = (nums[i] - min) / (diff / (bucketNum - 1));
// 当前元素放入 index 桶里面
bucket.get(index).add(nums[i]);
}
// 4、对每个桶中元素单独进行排序操作
for (int i = 0; i < bucket.size(); i++) {
// 每个桶进行一次冒泡排序
bubbleSort(bucket.get(i));
}
// 5、按照桶的顺序,依次输出桶中元素
int index = 0;
for (int i = 0; i < bucket.size(); i++) {
List temp = bucket.get(i);
for (int j = 0; j < temp.size(); j++) {
nums[index++] = temp.get(j);
}
}
}
public static void bubbleSort(List nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums.get(j) > nums.get(j + 1)) {
// 交换元素
int temp = nums.get(j);
nums.set(j, nums.get(j + 1));
nums.set(j + 1, temp);
}
}
}
}
public static void main(String[] args) {
int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
System.out.println(Arrays.toString(nums));
bucketSort(nums);
System.out.println(Arrays.toString(nums));
}
}
2.3、规约化分桶
前面两个分桶的方式,都不太合理,因为有些桶从始至终都没有存放元素,显然还浪费了内存空间,有没有什么方式可以将那些没有元素的桶给去掉,只保留那些存放元素的桶呢???
- 根据这个思路,我们可以看到,2.1和2.2两种分桶方式都是一开始就确定多少个桶,有没有什么方式可以不事先确定桶呢,而是在扁你数组的过程中,动态的确定当前数据应该放入哪个桶里面。
- 如果当前数据没有对应的桶,则创建一个桶,保存当前数据。
- 我们可以采用【哈希表】来实现,哈希表的【key】作为桶,【value】保存每个数据元素。
前面介绍完了桶排序的思想了,这里编写代码实现桶排序。
- 桶排序,如何分桶是关键,分多少个桶,以及如何确定分多少个桶???
- 这些都是需要考虑的问题,不同的分桶方式,可能会影响算法的效率,最直接的分桶就是直接通过【序列长度】作为桶的数量【bucketNum】,然后通过【max - min】除以【bucketNum】将数据放入不同的桶里面。
- 这种方式的缺点,如果数据有【n】个,那就需要分【n】个桶,显然空间复杂度太高了。
public class BucketSort {
public static void bucketSort(int[] nums) {
// 1、求最大值和最小值
int max = nums[0], min = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
// 计算差值: 最大值 - 最小值
int diff = max - min;
// 2、初始化桶: 按照序列长度分桶
int bucketNum = nums.length;
// 创建桶: 链表方式
List> bucket = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>()); // 初始化桶
}
// 3、遍历数组,将每个数据分桶存放
for (int i = 0; i < nums.length; i++) {
// 计算当前元素应该放入哪个桶里面
// diff / (bucketNum - 1): 表示每个桶保存多少数据的范围
// nums[i] - min: 因为第一个桶从[min,mid+k]开始,所以后面的元素都要减去min开始计算区间,相等于将min看作原点0
int index = (nums[i] - min) / (diff / (bucketNum - 1));
// 当前元素放入 index 桶里面
bucket.get(index).add(nums[i]);
}
// 4、对每个桶中元素单独进行排序操作
for (int i = 0; i < bucket.size(); i++) {
// 每个桶进行一次冒泡排序
bubbleSort(bucket.get(i));
}
// 5、按照桶的顺序,依次输出桶中元素
int index = 0;
for (int i = 0; i < bucket.size(); i++) {
List temp = bucket.get(i);
for (int j = 0; j < temp.size(); j++) {
nums[index++] = temp.get(j);
}
}
}
public static void bubbleSort(List nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums.get(j) > nums.get(j + 1)) {
// 交换元素
int temp = nums.get(j);
nums.set(j, nums.get(j + 1));
nums.set(j + 1, temp);
}
}
}
}
public static void main(String[] args) {
int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
System.out.println(Arrays.toString(nums));
bucketSort(nums);
System.out.println(Arrays.toString(nums));
}
}
2.2、简单分桶
第二种分桶方式:
- 按照【max - min】差值除以【10】再【加1】作为最终分桶的数量【bucketNum】。
- 公式:【bucketNum = (max - min) / 10 + 1;】
- 这种方式,相比较于2.1的方式,在某些情况下,可以很大程度上减少桶的数量。
- 例如:
- 100个待排序元素,并且假设最大值等于99,最小值等于2;
- 按照2.1的方式,直接分【100】个桶;
- 按照2.2的方式,【bucketNUm =(99-2)/ 10 + 1】直接分【10】个桶,减少了【10】倍。
- 当然了,这种分桶也不是绝对的,因为如果元素有100个,但是里面最大值等于10000,最小值是1,那么计算出来的分桶数量就是【1001】,显然还不如直接按照2.1方式进行分桶。
public class BucketSort {
// 简单分桶
public static void bucketSort(int[] nums) {
// 1、求最大值和最小值
int max = nums[0], min = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
// 计算差值: 最大值 - 最小值
int diff = max - min;
// 2、初始化桶: 按照简单分桶方式
int bucketNum = (max - min) / 10 + 1;
// 创建桶: 链表方式
List> bucket = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>()); // 初始化桶
}
// 3、遍历数组,将每个数据分桶存放
for (int i = 0; i < nums.length; i++) {
// 计算当前元素应该放入哪个桶里面
// diff / (bucketNum - 1): 表示每个桶保存多少数据的范围
// nums[i] - min: 因为第一个桶从[min,min + d]开始,所以后面的元素都要减去min开始计算区间,相等于将min看作原点0
int index = (nums[i] - min) / (diff / (bucketNum - 1));
// 当前元素放入 index 桶里面
bucket.get(index).add(nums[i]);
}
// 4、对每个桶中元素单独进行排序操作
for (int i = 0; i < bucket.size(); i++) {
// 每个桶进行一次冒泡排序
bubbleSort(bucket.get(i));
}
// 5、按照桶的顺序,依次输出桶中元素
int index = 0;
for (int i = 0; i < bucket.size(); i++) {
List temp = bucket.get(i);
for (int j = 0; j < temp.size(); j++) {
nums[index++] = temp.get(j);
}
}
}
public static void bubbleSort(List nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums.get(j) > nums.get(j + 1)) {
// 交换元素
int temp = nums.get(j);
nums.set(j, nums.get(j + 1));
nums.set(j + 1, temp);
}
}
}
}
public static void main(String[] args) {
int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
System.out.println(Arrays.toString(nums));
bucketSort(nums);
System.out.println(Arrays.toString(nums));
}
}
2.3、规约化分桶
前面两个分桶的方式,都不太合理,因为有些桶从始至终都没有存放元素,显然还浪费了内存空间,有没有什么方式可以将那些没有元素的桶给去掉,只保留那些存放元素的桶呢???
- 根据这个思路,我们可以看到,2.1和2.2两种分桶方式都是一开始就确定多少个桶,有没有什么方式可以不事先确定桶呢,而是在扁你数组的过程中,动态的确定当前数据应该放入哪个桶里面。
- 如果当前数据没有对应的桶,则创建一个桶,保存当前数据。
- 我们可以采用【哈希表】来实现,哈希表的【key】作为桶,【value】保存每个数据元素。
第二种分桶方式:
- 按照【max - min】差值除以【10】再【加1】作为最终分桶的数量【bucketNum】。
- 公式:【bucketNum = (max - min) / 10 + 1;】
- 这种方式,相比较于2.1的方式,在某些情况下,可以很大程度上减少桶的数量。
- 例如:
- 100个待排序元素,并且假设最大值等于99,最小值等于2;
- 按照2.1的方式,直接分【100】个桶;
- 按照2.2的方式,【bucketNUm =(99-2)/ 10 + 1】直接分【10】个桶,减少了【10】倍。
- 当然了,这种分桶也不是绝对的,因为如果元素有100个,但是里面最大值等于10000,最小值是1,那么计算出来的分桶数量就是【1001】,显然还不如直接按照2.1方式进行分桶。
- > bucket = new ArrayList<>();
for (int i = 0; i < bucketNum; i++) {
bucket.add(new ArrayList<>()); // 初始化桶
}
// 3、遍历数组,将每个数据分桶存放
for (int i = 0; i < nums.length; i++) {
// 计算当前元素应该放入哪个桶里面
// diff / (bucketNum - 1): 表示每个桶保存多少数据的范围
// nums[i] - min: 因为第一个桶从[min,min + d]开始,所以后面的元素都要减去min开始计算区间,相等于将min看作原点0
int index = (nums[i] - min) / (diff / (bucketNum - 1));
// 当前元素放入 index 桶里面
bucket.get(index).add(nums[i]);
}
// 4、对每个桶中元素单独进行排序操作
for (int i = 0; i < bucket.size(); i++) {
// 每个桶进行一次冒泡排序
bubbleSort(bucket.get(i));
}
// 5、按照桶的顺序,依次输出桶中元素
int index = 0;
for (int i = 0; i < bucket.size(); i++) {
List
前面两个分桶的方式,都不太合理,因为有些桶从始至终都没有存放元素,显然还浪费了内存空间,有没有什么方式可以将那些没有元素的桶给去掉,只保留那些存放元素的桶呢???
- 根据这个思路,我们可以看到,2.1和2.2两种分桶方式都是一开始就确定多少个桶,有没有什么方式可以不事先确定桶呢,而是在扁你数组的过程中,动态的确定当前数据应该放入哪个桶里面。
- 如果当前数据没有对应的桶,则创建一个桶,保存当前数据。
- 我们可以采用【哈希表】来实现,哈希表的【key】作为桶,【value】保存每个数据元素。
如何确定当前数据元素应该放入哪个桶里面???
给出计算数据所属于的桶公式:
- index = (nums[i] - min) / (max - min) * len;
- index:表示属于哪个桶。
- max:表示最大值。
- min:表示最小值。
- len:表示数组长度,元素个数。
- nums[i]:表示当前元素值。
- 采用这种方式,可以确保,每个数据元素都一定在某个桶里面,并且不会存在空桶。
public class BucketSort {
public static void bucketSort(int[] nums) {
// 1、求最大值和最小值
int max = nums[0], min = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
// 计算差值: 最大值 - 最小值
int diff = max - min;
// 2、初始化桶: 按照规约化分桶
Map> bucket = new HashMap<>();
// 3、遍历数组,将每个数据分桶存放
int len = nums.length;
for (int i = 0; i < len; i++) {
// 计算当前元素应该放入哪个桶里面
int index = (nums[i] - min) / (max - min) * len;
// 判断是否已经存在当前 index 桶
if (bucket.containsKey(index)) {
// 存在桶,则元素直接放入桶里面
bucket.get(index).add(nums[i]);
} else {
// 不存在桶,则创建新桶保存元素
List temp = new ArrayList<>();
temp.add(nums[i]);
bucket.put(index, temp);
}
}
// 4、对每个桶中元素单独进行排序操作
List keyList = new ArrayList<>(bucket.keySet());
Collections.sort(keyList);
// 对 key 进行排序, 从最小的桶开始排序, 然后取出元素
int index = 0; // 数组下标
List bucketList = null;
for (int key : keyList) {
bucketList = bucket.get(key);
// 对每个桶进行冒泡排序
bubbleSort(bucketList);
// 5、按照桶的顺序,依次输出桶中元素
for (int i = 0; i < bucketList.size(); i++) {
nums[index++] = bucketList.get(i);
}
}
}
public static void bubbleSort(List nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (nums.get(j) > nums.get(j + 1)) {
// 交换元素
int temp = nums.get(j);
nums.set(j, nums.get(j + 1));
nums.set(j + 1, temp);
}
}
}
}
public static void main(String[] args) {
int[] nums = {4, 21, 9, 38, 74, 21, 18, 44, 120, 99};
System.out.println(Arrays.toString(nums));
bucketSort(nums);
System.out.println(Arrays.toString(nums));
}
}
桶排序,这里其实我个人还有点不太理解的地方是:
- 问题一:规约化分桶的时候,采用【index = (nums[i] - min) / (max - min) * len;】找到哪个桶,具体含义是什么意思???为什么通过这种方式,就可以获取到某个数据对应哪个桶里面???
以上程序运行结果:
综上,就是桶排序相关思想,以及代码实现。



