C語言中如何實現桶排序

C語言實現桶排序

1.原理

由映射函數分配初始元素的鍵值,然後將這些元素放入對應鍵值的桶中,並對桶中的數據進行排序。然後依次將每個桶中的元素分出得到排好序的序列。

在這裡插入圖片描述

2.桶排序不是基於比較的排序

將N個待排序的元素放入桶中隻需要O(n)時間。後續則是對桶中元素的排序,所以當桶越多的時候,桶中的元素會越少,所采取的基於比較的排序算法的時間則會大大減少。

所以,這裡我們就可確定瞭一個重點,即是桶的數量必須是有限個的,可以經過一系列運算得到具體數目的。

3.桶的實現形式

我們以結構體數組存儲單鏈表實現。以結構體數組的數組單元來春初鏈表的頭節點,頭節點含有兩個變量,為指針變量(指向下一個鏈表節點),和整形變量key(就是如下圖裡面頭節點的值),key表示鏈表的節點個數。

在這裡插入圖片描述

4.桶中元素的排序

因為桶是采取單鏈表來實現的,所以桶中元素的插入就是鏈表中的元素插入。這裡要註意分桶為空和非空兩種情況來插入。

	if(p->key == 0){
			bucket_table[index]->next = node_branch;
			(bucket_table[index]->key)++;
		} 
		//鏈表的插入形式,按照大小從後到大。 
		else{
			while(p->next!=NULL && p->next->key <= node_branch->key){
			p=p->next;				
			}	
			node_branch->next = p->next;
			p->next = node_branch;
			(bucket_table[j]->key)++;
		}

4.最後就是將桶中的元素依次輸出

或存放到數組原始序列的數組中。

5完整代碼如下

#include<stdio.h>
#include<stdlib.h>
//整體思想大致為用數組單元內存放的為結構體式的鏈表,每個鏈表稱為一個桶。通裡面容納的都是鍵值相同的元素。 
// 之後便是查看對應元素的鍵值,然後放進與之對應的桶,還需註意桶為空和不空的時的放入方式
//桶元素的插入就是看桶以什麼方式的實現。這裡桶以鏈表的形式表現,所以桶中元素的插入即為鏈表中數組的插入。
/*隻要桶的數量夠多,那麼之前的放入操作隻需花費O(n)的時間,而後面的對每個桶裡面的元素進行排序則需要基於比較的排序算法。因此後面算法的選擇也是
關乎桶排序速度的重要因素。 
 */ 
//桶排序的特點是要有界限分明的桶,而不能是無限個桶,也就是說桶排序的個數應該是可以確定的,有限個的。 
//這裡鏈表實現桶排序的還有要註意的點,就是數組的首地址其實鏈表的頭節點,有這裡的值確定該桶的元素個數,並由這裡出發尋找其他元素。 
typedef struct node *Snode;
typedef struct node{
	int key;
	Snode next;
}BBc;

void sort(int keys[],int keys_size,int bucket_size)
{
	Snode *bucket_table = (Snode *)malloc(bucket_size*sizeof(Snode));//為結構體數組分配空間。 
	for(int i=0;i<bucket_size;i++)//對每個數組單元賦予內存空間時,初始化每個結構體數組單元。 
	{
		bucket_table[i] = (Snode)malloc(sizeof(Snode));//這一步是必要的,因為之前隻是給數組分配瞭一連串的存儲空間,但是每個單元的存儲地址都是 
	    //不確定,也不確定該方式是否會自動地分配內存空間給每個數組單元。 
	    //那麼這樣準確的給數組單眼分配的空間是占用之前的分配給數組的空間,還是重新分撥其他的空間給數組單元。
		//其實應該是分配之前給整個數組單元分配的一段存儲空間。 
		bucket_table[i]->key = 0;
		bucket_table[i]->next = NULL;
	}//其實創建數組這部分應該放在主函數那裡,否則某些功能隻能在這個函數中使用。 
	for(int j=0;j<keys_size;j++)
	{
		Snode node_branch = (Snode)malloc(sizeof(Snode));//定義一個節點,滿足條件時鏈入以鏈表為表現形式的桶。 
		node_branch->key = keys[j];
		node_branch->next = NULL;
		int index = keys[j]/10;
		Snode p = bucket_table[index];//p用來充當指向循環的變量。 
		//桶為空和非空時的兩種插入形式 
		if(p->key == 0){
			bucket_table[index]->next = node_branch;
			(bucket_table[index]->key)++;
		} 
		//鏈表的插入形式,按照大小從後到大。 
		else{
			while(p->next!=NULL && p->next->key <= node_branch->key){
			p=p->next;				
			}	
			node_branch->next = p->next;
			p->next = node_branch;
			(bucket_table[j]->key)++;
		}
	}
	//以此輸出每個桶中的所有元素。 
	for(int i=0;i<bucket_size;i++){
		for(Snode k = bucket_table[i]->next;k!=NULL;k = k->next){
			printf(" %d ",k->key);
		}
	}
	
}

int main()
{
	int keys[] = {49,26,53,47,89,31,72,11,33};
	int keys_size = sizeof(keys)/sizeof(int);
	int bucket_size = keys_size+2;
	sort(keys,keys_size,bucket_size);
}

7.桶排序的時間復雜度和空間復雜度

前面的將n個待排序元素分到對應鍵值的桶中隻需要O(n)時間,後面則是基於比較的排序算法,基於比較的排序算法最快可以達到:O(nlogn)時間。

所以桶裡面的排序算法的選擇也會影響到桶排序的速度。至於空間復雜度,一般都是占用空間比較大,以便每個桶中盡可能的達到一個元素,這樣桶裡面的排序也是O(n)時間,可以說是非常快速的。所以桶排序也是一種空間換時間的排序。 

另外桶排序的元素鍵值應該相差不大,以免照成空間的浪費。另外,劃分的桶也應該是有限個的。

【排序】圖解桶排序

思想

一句話總結:劃分多個范圍相同的區間,每個子區間自排序,最後合並

桶排序是計數排序的擴展版本,計數排序可以看成每個桶隻存儲相同元素,而桶排序每個桶存儲一定范圍的元素,通過映射函數,將待排序數組中的元素映射到各個對應的桶中,對每個桶中的元素進行排序,最後將非空桶中的元素逐個放入原序列中。

桶排序需要盡量保證元素分散均勻,否則當所有數據集中在同一個桶中時,桶排序失效。

圖解過程

核心代碼

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]);
    }
    
    // 計算桶的數量
    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));
    }
    
    // 將桶中的元素賦值到原序列
	int index = 0;
	for(int i = 0; i < bucketArr.size(); i++){
		for(int j = 0; j < bucketArr.get(i).size(); j++){
			arr[index++] = bucketArr.get(i).get(j);
		}
	}  
}

復雜度分析

1. 時間復雜度:O(N + C)

對於待排序序列大小為 N,共分為 M 個桶,主要步驟有:

  • N 次循環,將每個元素裝入對應的桶中
  • M 次循環,對每個桶中的數據進行排序(平均每個桶有 N/M 個元素)

一般使用較為快速的排序算法,時間復雜度為O(NlogN),實際的桶排序過程是以鏈表形式插入的。

整個桶排序的時間復雜度為:

O(N)+O(M*(N/M*log(N/M)))=O(N*(log(N/M)+1))

當 N = M 時,復雜度為 O(N)

2. 額外空間復雜度:O(N + M)

穩定性分析

桶排序的穩定性取決於桶內排序使用的算法。

以上為個人經驗,希望能給大傢一個參考,也希望大傢多多支持WalkonNet。

推薦閱讀: