寫在前面
- 樓主整理經(jīng)典的排序算法
- 記錄學習
1. 桶排序(BucketSort)
1.1 概念
桶排序是計數(shù)排序的升級版。它利用了函數(shù)的映射關系熄赡，高效與否的關鍵就在于這個映射函數(shù)的確定躲撰。
桶排序 (Bucket sort)的工作的原理：假設輸入數(shù)據(jù)服從均勻分布丹弱，將數(shù)據(jù)分到有限數(shù)量的桶里昆禽，每個桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排
1.2 算法描述
- 設置一個定量的數(shù)組當作空桶子茬缩。
- 尋訪序列卿拴，并且把項目一個一個放到對應的桶子去衫仑。
- 對每個不是空的桶子進行排序。
- 從不是空的桶子里把項目再放回原來的序列中堕花。
==示意圖==
image
1.3 代碼演示
package com.zhuang.algorithm;
import java.util.ArrayList;
import java.util.*;
/**
* @Classname BucketSort
* @Description 桶排序
* @Date 2021/6/13 19:07
* @Created by dell
*/
public class BucketSort {
public static void main(String[] args) {
int[] arr = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
bucketSort(arr);
System.out.println("桶排序以后的序列為:");
System.out.println(Arrays.toString(arr));
}
public static void bucketSort(int[] arr) {
//最大最小值
int max = arr[0];
int min = arr[0];
int len = arr.length;
for (int i = 0; i < len; i++) {
if (arr[i] > max) {
max = arr[i];
} else if (arr[i] < min) {
max = arr[i];
}
}
//最大值和最小值得差
int diff = max - min;
//桶列表
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for (int i = 0; i < len; i++) {
list.add(new ArrayList<>());
}
//每個桶的存數(shù)區(qū)間
float section = (float) diff / (float) (len - 1);
//數(shù)據(jù)入桶
for (int i = 0; i < len; i++) {
//當前數(shù)除以區(qū)間得出存放桶的位置文狱，減1得出桶的下標
int num = (int) ((arr[i] / section) - 1);
if (num < 0) {
num = 0;
}
list.get(num).add(arr[i]);
}
//桶內(nèi)排序
for (int i = 0; i < list.size(); i++) {
Collections.sort(list.get(i));
}
//寫入原數(shù)組
int index = 0;
for (ArrayList<Integer> arrayList : list) {
for (Integer integer : arrayList) {
arr[index] = integer;
index++;
}
}
}
}
或者下列方法也可以
package com.zhuang.algorithm;
import java.util.ArrayList;
import java.util.*;
/**
* @Classname BucketSort
* @Description 桶排序
* @Date 2021/6/13 19:07
* @Created by dell
*/
public class BucketSort {
public static void main(String[] args) {
int[] arr = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
bucketSort(arr);
}
public static void bucketSort(int[] arr) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//桶數(shù)
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<Integer>());
}
//將每個元素放入桶
for (int i = 0; i < arr.length; 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());
}
}
1.4 算法分析
桶排序最好情況下使用線性時間O(n)，桶排序的時間復雜度缘挽，取決與對各個桶之間數(shù)據(jù)進行排序的時間復雜度瞄崇，因為其它部分的時間復雜度都為O(n)呻粹。桶劃分的越小，各個桶之間的數(shù)據(jù)越少苏研，排序所用的時間也會越少等浊。但相應的空間消耗就會增大
1.5 適用場景
桶排序可用于最大最小值相差較大的數(shù)據(jù)情況，但桶排序要求數(shù)據(jù)的分布必須均勻摹蘑，否則可能導致數(shù)據(jù)都集中到一個桶中
寫在最后
- 學習階段筹燕，描述不當?shù)胤剑€請大家在評論區(qū)指出
- 繼續(xù)加油衅鹿！
