排序算法是《數(shù)據(jù)結構與算法》中最基本的算法之一。排序算法可以分為內部排序和外部排序,內部排序是數(shù)據(jù)記錄在內存中進行排序,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部的排序記錄,在排序過程中需要訪問外存。常見的內部排序算法有:插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。以下是桶排序算法:
桶排序是計數(shù)排序的升級版。它利用了函數(shù)的映射關系,高效與否的關鍵就在于這個映射函數(shù)的確定。為了使桶排序更加高效,我們需要做到這兩點:
在額外空間充足的情況下,盡量增大桶的數(shù)量使用的映射函數(shù)能夠將輸入的 N 個數(shù)據(jù)均勻的分配到 K 個桶中同時,對于桶中元素的排序,選擇何種比較排序算法對于性能的影響至關重要。
1. 什么時候最快當輸入的數(shù)據(jù)可以均勻的分配到每一個桶中。
2. 什么時候最慢當輸入的數(shù)據(jù)被分配到了同一個桶中。
3. 示意圖元素分布在桶中:
然后,元素在每個桶中排序:
代碼實現(xiàn)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]; ? ? ? ? ? ? ? ?// 輸入數(shù)據(jù)的最小值? ? ? } else if (arr[i] > maxValue) {? ? ? ? ? maxValue = arr[i]; ? ? ? ? ? ? ? ?// 輸入數(shù)據(jù)的最大值? ? ? }? ? }? ? //桶的初始化? ? var DEFAULT_BUCKET_SIZE = 5; ? ? ? ? ? ?// 設置桶的默認數(shù)量為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] = [];? ? }? ? //利用映射函數(shù)將數(shù)據(jù)分配到各個桶中? ? 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 進行拷貝,不改變參數(shù)內容? ? ? ? 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];? ? ? ? // 利用映射函數(shù)將數(shù)據(jù)分配到各個桶中? ? ? ? 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;? ? }? ? /**? ? ?* 自動擴容,并保存數(shù)據(jù)? ? ?*? ? ?* @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參考地址:
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)在額外空間充足的情況下,盡量增大桶的數(shù)量 2)使用的映射函數(shù)能夠將輸入的 N 個數(shù)據(jù)均勻的分配到 K 個桶中 個人理解,如果都是整數(shù)還可以用計數(shù)排序來計數(shù)統(tǒng)計然后排序,但是如果是一個連續(xù)空間內的排序,即統(tǒng)計的是一個浮點類型的數(shù)組成 的數(shù)組,那么,就無法開辟一個對應的空間使其一一對應的存儲。此時,我們需要新建一個帶有存儲范圍的空間,來存儲一定范圍內的元素 空間復雜度:O(n) 時間復雜度: O(n) 穩(wě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) # 將相應范圍內的數(shù)據(jù)加入到[]中 arr = [] for i in range(len(buf)): if buf[i]: arr.extend(sorted(buf[i])) # 這里還需要對一個范圍內的數(shù)據(jù)進行排序,然后再進行輸出 return arr if __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(Listlist, int bucketCount, int maxBucketCount) { List > buckets = new List
>(bucketCount);//二維列表 for (int i = 0; i < bucketCount; i++) { buckets.Add(new List
()); } 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;//如果不發(fā)生交換直接退出,因為前面的之前就排序好了 } } } list.Clear();//輸出 for (int i = 0; i < buckets.Count; i++) { list.AddRange(buckets[i]); } }
熱心網友提供的補充3:
C 語言實現(xiàn)桶排序,桶內采用插入排序:
#include#include #include #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; }
下載測試代碼
以上為桶排序算法詳細介紹,插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等排序算法各有優(yōu)缺點,用一張圖概括:關于時間復雜度
平方階 (O(n2)) 排序 各類簡單排序:直接插入、直接選擇和冒泡排序。
線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序;
O(n1+§)) 排序,§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序,此外還有桶、箱排序。
關于穩(wěn)定性
穩(wěn)定的排序算法:冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法:選擇排序、快速排序、希爾排序、堆排序。
名詞解釋:
n:數(shù)據(jù)規(guī)模
k:"桶"的個數(shù)
In-place:占用常數(shù)內存,不占用額外內存
Out-place:占用額外內存
穩(wěn)定性:排序后 2 個相等鍵值的順序和排序之前它們的順序相同