如我這幾天的風格一樣，概念不多說，直接正題： >: 桶排序不是基於比較的排序，最好的時間復雜度可以達到O(n)，例如：9個數 10,20,30,40,50,60,70,80,90( 這些數字的順序是任意的，任意多亂！ )，給9個桶，那麼每個元素都進一個桶，且桶內無需排序(因為只有一個元素)，所以進桶後，在一次出來就可以了，就是線性的！原因就是因為桶排序並不是基於比較排序的，比較排序的限制最好的其情況是 O(nlgn)。 >: 思想：很像分治( 我說的僅僅是劃為小塊的部分的思想 ，都是這種大化小)，對於海量數據而言，特別是當內存一次裝不下的時候，桶排序是很有效的~ 即：把[ a, b ]劃分為n個大小相同的子區間，每一子區間是一個桶。然後將n個記錄分配到各個桶中。因為關鍵字序列是均勻分布在[ n, m ]上的，所以一般不會有很多個記錄落入同一個桶中。由於同一桶中的記錄其關鍵字不盡相同，所以必須采用關鍵字比較的排序方法(通常用插入排序)對各個桶進行排 序，然後依次將各非空桶中的記錄連接(收集)起來即可。 >: 桶排序適用於什麼地方？我覺得桶排序雖然很強大，但是用錯了地方還是不行的，用錯地方其復雜度可以達到O(n^2)：我覺得對於數據量超級大，但是數據的范圍確實在一個不是很大的區間內，那麼用桶排序是非常有效的！特別是當均勻分布的時候，更高效。例如：考試成績0--100分，可以分成10個桶，那麼使用桶排序統計每個分數段的處理就是很優雅的！呵呵~！ 基於以上的想法，簡單實現一個桶排序的處理： CODE：（ 僅僅是個演示而已~ ） // 桶排序一般比較適合：數據量非常大，但數據的范圍在一個區間內的情況 // // 此處僅僅以1-100之間的數來處理，其他的數據類型，需要做相應的修改 // 思想都是一樣的！ // 桶內使用有序鏈表比較法 [cpp] #include <stdio.h> #include <stdlib.h> typedef struct node { intvalue; structnode * next; }node, *p_node; void bucket( node buc[], intelem[], int n ) { inti = 0; p_nodetmp, t; for(i = 0; i < n; i++ ) { tmp= &buc[elem[i]/10]; // 選擇桶 t= ( p_node )malloc( sizeof( node ) ); t->value= elem[i]; t->next= NULL; while(tmp!= NULL ) { if(tmp->next == NULL ) { t->next= tmp->next; tmp->next= t; break; } elseif( tmp->next->value > t->value ) { t->next= tmp->next; tmp->next= t; break; } else { tmp= tmp->next; } } } } int main() { inti, n, *elem; nodebuc[10]; // 我們准備十個桶 p_nodetmp; while(scanf("%d", &n) != EOF ) { elem= ( int * )malloc( sizeof( int ) * n ); for(i = 0; i < n; i++ ) { scanf("%d",&elem[i]); } for(i = 0; i < 10; i++ ) // 初始化桶 { //為了方便起見，數組節點只作為頭結點，不存值 buc[i].next= NULL; } bucket(buc, elem, n ); for(i = 0; i < 10; i++ ) { tmp= buc[i].next; while( tmp ) { www.2cto.com printf("%d", tmp->value); tmp= tmp->next; } } printf("\n"); free(elem ); } return0; }
