java常用算法，常用排序算法(八)桶排序

桶排序

概要

本章介紹排序算法中的桶排序。內容包括：
1.?桶排序介紹
2.?桶排序圖文說明
3.?桶排序實現
3.1 ?桶排序C實現
3.2 ?桶排序C++實現
3.3 ?桶排序Java實現

轉載請注明出處：http://www.cnblogs.com/skywang12345/p/3602737.html

---

更多排序和算法請參考：數據結構與算法系列 目錄

java常用算法，?

桶排序介紹

桶排序(Bucket Sort)的原理很簡單，它是將數組分到有限數量的桶子里。

假設待排序的數組a中共有N個整數，并且已知數組a中數據的范圍[0, MAX)。在桶排序時，創建容量為MAX的桶數組r，并將桶數組元素都初始化為0；將容量為MAX的桶數組中的每一個單元都看作一個"桶"。
在排序時，逐個遍歷數組a，將數組a的值，作為"桶數組r"的下標。當a中數據被讀取時，就將桶的值加1。例如，讀取到數組a[3]=5，則將r[5]的值+1。

?

桶排序圖文說明

桶排序代碼

/** 桶排序** 參數說明：*     a -- 待排序數組*     n -- 數組a的長度*     max -- 數組a中最大值的范圍*/
void bucketSort(int a[], int n, int max) { int i,j; int buckets[max]; // 將buckets中的所有數據都初始化為0。 memset(buckets, 0, max*sizeof(int)); // 1. 計數 for(i = 0; i < n; i++) buckets[a[i]]++; // 2. 排序 for (i = 0, j = 0; i < max; i++) { while( (buckets[i]--) >0 ) a[j++] = i; } }

桶排序圖解。bucketSort(a, n, max)是作用是對數組a進行桶排序，n是數組a的長度，max是數組中最大元素所屬的范圍[0,max)。

假設a={8,2,3,4,3,6,6,3,9}, max=10。此時，將數組a的所有數據都放到需要為0-9的桶中。如下圖：

在將數據放到桶中之后，再通過一定的算法，將桶中的數據提出出來并轉換成有序數組。就得到我們想要的結果了。

?

桶排序實現

桶排序java，桶排序C實現
實現代碼(bucket_sort.c)

 1 /**
 2  * 桶排序：C 語言
 3  *  4  * @author skywang  5  * @date 2014/03/13  6 */  7  8 #include <stdio.h>  9 #include <stdlib.h> 10 #include <string.h> 11 12 // 數組長度 13 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) ) 14 15 /* 16  * 桶排序 17  * 18  * 參數說明： 19  * a -- 待排序數組 20  * n -- 數組a的長度 21  * max -- 數組a中最大值的范圍 22 */ 23 void bucket_sort(int a[], int n, int max) 24 { 25 int i, j; 26 int *buckets; 27 28 if (a==NULL || n<1 || max<1) 29 return ; 30 31 // 創建一個容量為max的數組buckets，并且將buckets中的所有數據都初始化為0。 32 if ((buckets=(int *)malloc(max*sizeof(int)))==NULL) 33 return ; 34 memset(buckets, 0, max*sizeof(int)); 35 36 // 1. 計數 37 for(i = 0; i < n; i++) 38 buckets[a[i]]++; 39 40 // 2. 排序 41 for (i = 0, j = 0; i < max; i++) 42 while( (buckets[i]--) >0 ) 43 a[j++] = i; 44 45  free(buckets); 46 } 47 48 void main() 49 { 50 int i; 51 int a[] = {8,2,3,4,3,6,6,3,9}; 52 int ilen = LENGTH(a); 53 54 printf("before sort:"); 55 for (i=0; i<ilen; i++) 56 printf("%d ", a[i]); 57 printf("\n"); 58 59 bucket_sort(a, ilen, 10); // 桶排序 60 61 printf("after sort:"); 62 for (i=0; i<ilen; i++) 63 printf("%d ", a[i]); 64 printf("\n"); 65 }

桶排序C++實現
實現代碼(BucketSort.cpp)

 1 /**
 2  * 桶排序：C++
 3  *  4  * @author skywang  5  * @date 2014/03/13  6 */  7  8 #include <iostream>  9 #include <cstring> 10 using namespace std; 11 12 /* 13  * 桶排序 14  * 15  * 參數說明： 16  * a -- 待排序數組 17  * n -- 數組a的長度 18  * max -- 數組a中最大值的范圍 19 */ 20 void bucketSort(int* a, int n, int max) 21 { 22 int i, j; 23 int *buckets; 24 25 if (a==NULL || n<1 || max<1) 26 return ; 27 28 // 創建一個容量為max的數組buckets，并且將buckets中的所有數據都初始化為0。 29 if ((buckets = new int[max])==NULL) 30 return ; 31 memset(buckets, 0, max*sizeof(int)); 32 33 // 1. 計數 34 for(i = 0; i < n; i++) 35 buckets[a[i]]++; 36 37 // 2. 排序 38 for (i = 0, j = 0; i < max; i++) 39 while( (buckets[i]--) >0 ) 40 a[j++] = i; 41 42  delete[] buckets; 43 } 44 45 46 int main() 47 { 48 int i; 49 int a[] = {8,2,3,4,3,6,6,3,9}; 50 int ilen = (sizeof(a)) / (sizeof(a[0])); 51 52 cout << "before sort:"; 53 for (i=0; i<ilen; i++) 54 cout << a[i] << " "; 55 cout << endl; 56 57 bucketSort(a, ilen, 10); // 桶排序 58 59 cout << "after sort:"; 60 for (i=0; i<ilen; i++) 61 cout << a[i] << " "; 62 cout << endl; 63 64 return 0; 65 }

桶排序Java實現
實現代碼(BucketSort.java)

 1 /**
 2  * 桶排序：Java
 3  *  4  * @author skywang  5  * @date 2014/03/13  6 */  7  8 public class BucketSort {  9 10 /* 11  * 桶排序 12  * 13  * 參數說明： 14  * a -- 待排序數組 15  * max -- 數組a中最大值的范圍 16 */ 17 public static void bucketSort(int[] a, int max) { 18 int[] buckets; 19 20 if (a==null || max<1) 21 return ; 22 23 // 創建一個容量為max的數組buckets，并且將buckets中的所有數據都初始化為0。 24 buckets = new int[max]; 25 26 // 1. 計數 27 for(int i = 0; i < a.length; i++) 28 buckets[a[i]]++; 29 30 // 2. 排序 31 for (int i = 0, j = 0; i < max; i++) { 32 while( (buckets[i]--) >0 ) { 33 a[j++] = i; 34  } 35  } 36 37 buckets = null; 38  } 39 40 public static void main(String[] args) { 41 int i; 42 int a[] = {8,2,3,4,3,6,6,3,9}; 43 44 System.out.printf("before sort:"); 45 for (i=0; i<a.length; i++) 46 System.out.printf("%d ", a[i]); 47 System.out.printf("\n"); 48 49 bucketSort(a, 10); // 桶排序 50 51 System.out.printf("after sort:"); 52 for (i=0; i<a.length; i++) 53 System.out.printf("%d ", a[i]); 54 System.out.printf("\n"); 55  } 56 }

上面3種實現的原理和輸出結果都是一樣的。下面是它們的輸出結果：

before sort:8 2 3 4 3 6 6 3 9 
after  sort:2 3 3 3 4 6 6 8 9