桶排序java
排序算法是《數據結構與算法》中最基本的算法之一。排序算法可以分爲內部排序和外部排序,內部排序是數據記錄在內存中進行排序,而外部排序是因排序的數據很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等。以下是桶排序算法:
桶排序是計數排序的升級版。它利用了函數的映射關係,高效與否的關鍵就在於這個映射函數的確定。爲了使桶排序更加高效,我們需要做到這兩點:
在額外空間充足的情況下,儘量增大桶的數量使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中同時,對於桶中元素的排序,選擇何種比較排序算法對於性能的影響至關重要。
1. 什麼時候最快
當輸入的數據可以均勻的分配到每一個桶中。
2. 什麼時候最慢
當輸入的數據被分配到了同一個桶中。
3. 示意圖
元素分佈在桶中:
然後,元素在每個桶中排序:
代碼實現
JavaScript
實例
function bucketSort(arr, bucketSize) {if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // 輸入數據的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // 輸入數據的最大值
}
}
//桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 設置桶的默認數量爲5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
//利用映射函數將數據分配到各個桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 對每個桶進行排序,這裏使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}
Java
實例
public class BucketSort implements IArraySort {private static final InsertSort insertSort = new InsertSort();
@Override
public int[] sort(int[] sourceArray) throws Exception {
// 對 arr 進行拷貝,不改變參數內容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
return bucketSort(arr, 5);
}
private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
if (arr.length == 0) {
return arr;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函數將數據分配到各個桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 對每個桶進行排序,這裏使用了插入排序
bucket = insertSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
/**
* 自動擴容,並保存數據
*
* @param arr
* @param value
*/
private int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
PHP
實例
function bucketSort($arr, $bucketSize = 5){
if (count($arr) === 0) {
return $arr;
}
$minValue = $arr[0];
$maxValue = $arr[0];
for ($i = 1; $i < count($arr); $i++) {
if ($arr[$i] < $minValue) {
$minValue = $arr[$i];
} else if ($arr[$i] > $maxValue) {
$maxValue = $arr[$i];
}
}
$bucketCount = floor(($maxValue - $minValue) / $bucketSize) + 1;
$buckets = array();
for ($i = 0; $i < $bucketCount; $i++) {
$buckets[$i] = [];
}
for ($i = 0; $i < count($arr); $i++) {
$buckets[floor(($arr[$i] - $minValue) / $bucketSize)][] = $arr[$i];
}
$arr = array();
for ($i = 0; $i < count($buckets); $i++) {
$bucketTmp = $buckets[$i];
sort($bucketTmp);
for ($j = 0; $j < count($bucketTmp); $j++) {
$arr[] = $bucketTmp[$j];
}
}
return $arr;
}
C++
實例
#include<iterator>#include<iostream>
#include<vector>
using namespace std;
const int BUCKET_NUM = 10;
struct ListNode{
explicit ListNode(int i=0):mData(i),mNext(NULL){}
ListNode* mNext;
int mData;
};
ListNode* insert(ListNode* head,int val){
ListNode dummyNode;
ListNode *newNode = new ListNode(val);
ListNode *pre,*curr;
dummyNode.mNext = head;
pre = &dummyNode;
curr = head;
while(NULL!=curr && curr->mData<=val){
pre = curr;
curr = curr->mNext;
}
newNode->mNext = curr;
pre->mNext = newNode;
return dummyNode.mNext;
}
ListNode* Merge(ListNode *head1,ListNode *head2){
ListNode dummyNode;
ListNode *dummy = &dummyNode;
while(NULL!=head1 && NULL!=head2){
if(head1->mData <= head2->mData){
dummy->mNext = head1;
head1 = head1->mNext;
}else{
dummy->mNext = head2;
head2 = head2->mNext;
}
dummy = dummy->mNext;
}
if(NULL!=head1) dummy->mNext = head1;
if(NULL!=head2) dummy->mNext = head2;
return dummyNode.mNext;
}
void BucketSort(int n,int arr[]){
vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
for(int i=0;i<n;++i){
int index = arr[i]/BUCKET_NUM;
ListNode *head = buckets.at(index);
buckets.at(index) = insert(head,arr[i]);
}
ListNode *head = buckets.at(0);
for(int i=1;i<BUCKET_NUM;++i){
head = Merge(head,buckets.at(i));
}
for(int i=0;i<n;++i){
arr[i] = head->mData;
head = head->mNext;
}
}
參考地址:
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/9.bucketSort.md
https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F
以下是熱心網友對桶排序算法的補充,僅供參考:
熱心網友提供的補充1:
# coding=utf-8# author: [email protected]# datetime:2020/7/28 18:37"""程序說明: 桶排序 1)在額外空間充足的情況下,儘量增大桶的數量 2)使用的映射函數能夠將輸入的 N 個數據均勻的分配到 K 個桶中 個人理解,如果都是整數還可以用計數排序來計數統計然後排序,但是如果是一個連續空間內的排序,即統計的是一個浮點類型的數組成 的數組,那麼,就無法開闢一個對應的空間使其一一對應的存儲。此時,我們需要新建一個帶有存儲範圍的空間,來存儲一定範圍內的元素 空間複雜度:O(n) 時間複雜度: O(n) 穩定"""def bucket_sort_simplify(arr, max_num): """ 簡化版 """ buf = {i: [] for i in range(int(max_num)+1)} # 不能使用[[]]*(max+1),這樣新建的空間中各個[]是共享內存的 arr_len = len(arr) for i in range(arr_len): num = arr[i] buf[int(num)].append(num) # 將相應範圍內的數據加入到[]中 arr = [] for i in range(len(buf)): if buf[i]: arr.extend(sorted(buf[i])) # 這裏還需要對一個範圍內的數據進行排序,然後再進行輸出 return arrif __name__ == "__main__": lis = [3.1, 4.2, 3.3, 3.5, 2.2, 2.7, 2.9, 2.1, 1.55, 4.456, 6.12, 5.2, 5.33, 6.0, 2.12] print(bucket_sort_simplify(lis, max(lis)))
熱心網友提供的補充2:
又沒把C#的寫進來,我來寫掉吧,代碼如下:
static void BucketSort(List<int> list, int bucketCount, int maxBucketCount){ List<List<int>> buckets = new List<List<int>>(bucketCount);//二維列表 for (int i = 0; i < bucketCount; i++) { buckets.Add(new List<int>()); } for (int i = 0; i < list.Count; i++) { // int j = Mathf.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪個桶,不能大於n-1 int j = Math.Min(list[i] / (maxBucketCount / bucketCount), bucketCount - 1);//j表示改放的哪個桶,不能大於n-1 buckets[j].Add(list[i]);//放入對應桶 for (int x = buckets[j].Count - 1; x > 0; x--)//放一個排序一次,兩兩對比就可以 { if (buckets[j][x] < buckets[j][x - 1])//升序 { int tmp = buckets[j][x];//交換 buckets[j][x] = buckets[j][x - 1]; buckets[j][x - 1] = tmp; } else { break;//如果不發生交換直接退出,因爲前面的之前就排序好了 } } } list.Clear();//輸出 for (int i = 0; i < buckets.Count; i++) { list.AddRange(buckets[i]); }}
熱心網友提供的補充3:
C 語言實現桶排序,桶內採用插入排序:
#include <stdio.h>#include <stdlib.h>#include <string.h>#define BUCKET_SIZE (5) /**< 假定均勻分佈的情況下平均每個桶放幾個元素*/typedef struct Node{ int elem; struct Node* list_next;} Node;typedef struct BucketManager{ int nums; Node** buckets; } BucketManager;typedef struct BucketSpaceManager{ int index; Node* nodes_space;} BucketSpaceManager;BucketSpaceManager* init_bucket_space(int size){ BucketSpaceManager* space_mgr = (BucketSpaceManager*)malloc(sizeof(BucketSpaceManager)); if (!space_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d", __FILE__, __func__, __LINE__); goto exit_1; } space_mgr->index = 0; space_mgr->nodes_space = (Node*)malloc(size * sizeof(Node)); if (!space_mgr->nodes_space) { printf("out of memory,File:%s, Func:%s, Line:%d", __FILE__, __func__, __LINE__); goto exit_2; } return space_mgr;exit_2: free(space_mgr);exit_1: return NULL;}BucketManager* init_buckets(int bucket_nums){ BucketManager* bucket_mgr = (BucketManager*)malloc(sizeof(BucketManager)); if (!bucket_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d", __FILE__, __func__, __LINE__); goto exit_1; } bucket_mgr->nums = bucket_nums; bucket_mgr->buckets = (Node**)calloc(bucket_mgr->nums, sizeof(Node*)); if (!bucket_mgr->buckets) { printf("out of memory,File:%s, Func:%s, Line:%d", __FILE__, __func__, __LINE__); goto exit_2; } return bucket_mgr;exit_2: free(bucket_mgr);exit_1: return NULL;}Node* get_bucket_space(BucketSpaceManager* space_mgr){ if (space_mgr) { return &space_mgr->nodes_space[space_mgr->index++]; } else { return NULL; }}void release_bucket_space(BucketSpaceManager* space_mgr){ if (space_mgr) { if (space_mgr->nodes_space) { free(space_mgr->nodes_space); } free(space_mgr); }}void release_buckets(BucketManager* buckets_mgr){ if (buckets_mgr) { if (buckets_mgr->buckets) { free(buckets_mgr->buckets); } free(buckets_mgr); }}int find_max_min(int* arr, int size, int* p_max, int* p_min){ if (size <= 0) { return -1; } *p_max = arr[0]; *p_min = arr[0]; int i; for (i = 1; i < size; ++i) { if (arr[i] > *p_max) { *p_max = arr[i]; } if (arr[i] < *p_min) { *p_min = arr[i]; } } return 0;}int insert_bucket(BucketManager* bucket_mgr, int index, Node* new_node){ Node* cur, *pre; if (!bucket_mgr->buckets[index]) { bucket_mgr->buckets[index] = new_node; } else { /** 桶內使用插入排序 */ cur = bucket_mgr->buckets[index]; pre = cur; while (cur->list_next && new_node->elem > cur->elem) { pre = cur; cur = cur->list_next; } if (new_node->elem <= cur->elem) { if (pre == cur) { new_node->list_next = cur; bucket_mgr->buckets[index] = new_node; } else { new_node->list_next = cur; pre->list_next = new_node; } } else { cur->list_next = new_node; } } return 0;}void bucket_sort(int* arr, int size){ int max, min; int ret = find_max_min(arr, size, &max, &min); if (ret < 0) { return; } BucketSpaceManager* space_mgr = init_bucket_space(size); if (!space_mgr) { printf("out of memory,File:%s, Func:%s, Line:%d", __FILE__, __func__, __LINE__); goto exit_1; } int bucket_nums = (max - min) / BUCKET_SIZE + 1; BucketManager* bucket_mgr = init_buckets(bucket_nums); if (!bucket_mgr) { goto exit_2; } int i; for (i = 0; i < size; ++i) { int index = (arr[i] - min) / BUCKET_SIZE; Node* new_node = get_bucket_space(space_mgr); if (!new_node) { goto exit_3; } new_node->elem = arr[i]; new_node->list_next = NULL; insert_bucket(bucket_mgr, index, new_node); } for (i = 0; i < bucket_mgr->nums; ++i) { Node* node = bucket_mgr->buckets[i]; while(node) { printf("%d ", node->elem); node = node->list_next; } } printf("");exit_3: release_buckets(bucket_mgr);exit_2: release_bucket_space(space_mgr);exit_1: return;}
下載測試代碼
以上爲桶排序算法詳細介紹,插入排序、希爾排序、選擇排序、冒泡排序、歸併排序、快速排序、堆排序、基數排序等排序算法各有優缺點,用一張圖概括:關於時間複雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和冒泡排序。
線性對數階 (O(nlog2n)) 排序 快速排序、堆排序和歸併排序;
O(n1+§)) 排序,§ 是介於 0 和 1 之間的常數。 希爾排序
線性階 (O(n)) 排序 基數排序,此外還有桶、箱排序。
關於穩定性
穩定的排序算法:冒泡排序、插入排序、歸併排序和基數排序。
不是穩定的排序算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:數據規模
k:"桶"的個數
In-place:佔用常數內存,不佔用額外內存
Out-place:佔用額外內存
穩定性:排序後 2 個相等鍵值的順序和排序之前它們的順序相同
-
蘋果手機長圖怎麼截圖,蘋果手機截長圖的兩種方法
1、長截圖辦法一iOS13上新之後自帶的長截圖方法,是在我們瀏覽網頁的時候使用的。操作方法:上音量鍵+開關鍵一起按下,然後點開截好的圖片,選擇“整頁”截圖即可。2、長截圖方法二利用QQ實現長截圖。操作方法:首先就是需要我們打開QQ,然後試着上音量鍵+開關鍵一起按下...
-
省內移動數據流量是指什麼
省內移動數據流量是指你的SIM卡所屬省份的可用GPRS流量,如果出了你的卡所屬的省份,去別的省,那省內移動數據流量就不可以使用,只能使用全國通用流量。移動數據流量有省內流量和全國通用流量,國內流量和省內流量是有所區別的。首先優先度不同:正常情況下,如果用戶在自...
-
關於底噪的意思介紹
1、底噪亦稱背景噪聲,基本所有的好耳機都有底噪,耳機底噪一般都是因爲前端的問題,耳機的靈敏度越高對於底噪就越敏感,一些高靈敏度和低阻抗的耳機會把底噪放大,如果加大音量的情況下,底噪會更加的明顯。2、檢測MP3底噪,一般方法是在夜晚等比較安靜的環境中戴上耳機,播...
-
黑色背景拍照竅門詳解
1、調整拍攝角度,尋找背景:既然是拍攝黑背景,在拍攝前我們儘量選擇深色的背景,這樣也就更加容易達到效果。不過深色不一定要是純黑色,只要顏色較爲深沉,偏向暗色調的均可。拍攝前多多觀察,尋找不同的拍攝角度,以找到有反差的深色作爲背景。要多嘗試不同的角度,直至主體...