桶排序與堆排序（計數排序桶排序）

2023-05-02 09:57:45

計數排序不是基於比較的排序算法，其核心在於將輸入的數據值轉化為鍵存儲在額外開闢的數組空間中。 作為一種線性時間複雜度的排序O（n），計數排序要求輸入的數據必須是有確定範圍的整數。（直方圖統計，再按照順序扔出來）

7.1 算法描述

找出待排序的數組中最大和最小的元素；

統計數組中每個值為i的元素出現的次數，存入數組C的第i項；

對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；

反向填充目標數組：將每個元素i放在新數組的第C(i)項，每放一個元素就將C(i)減去1。

7.2 動圖演示

代碼實現：

void countingSort(int a[], int len){ if (!a || len <= 0) return; //通過max和min計算出臨時數組所需要開闢的空間大小 int max = a[0], min = a[0]; for (int i = 0; i max) max = a[i]; if (a[i] < min) min = a[i]; } //分配臨時數組，使用calloc將數組都初始化為0 int range = max - min 1; int *b = (int *)calloc(range, sizeof(int)); //使用臨時數組記錄原始數組中每個數的個數 for (int i = 0; i < len; i ) b[a[i] - min] = 1; //注意：這裡在存儲上要在原始數組數值上減去min才不會出現越界問題 int j = 0; //根據統計結果，重新對元素進行回收 for (int i = 0; i = right) return; int l = left; int r = right; int key = arr[l]; while (l l && arr[r] > key) r--; arr[l] = arr[r]; while (l < r && arr[l] < key) l ; arr[r] = arr[l]; } arr[l] = key; quickSort(arr, left, l - 1); quickSort(arr, l 1, right);}//定義一個桶的結構體，也可以使用鍊表等其他實現方法struct bucket { int node[10]; int count; //數據個數};void bucketSort(int a[], int len){ if (!a || len <= 0) return; int max = a[0], min = a[0]; for (int i = 1; i max) max = a[i]; if (a[i] < min) min = a[i]; } int num = (max - min 1) / 10 1; struct bucket *pBucket = (struct bucket*)calloc(num, sizeof(struct bucket)); //將a[i]放進對應的桶中 for (int i = 0; i node[(pBucket k)->count] = a[i]; (pBucket k)->count ; } int pos = 0; for (int i = 0; i node, 0, (pBucket i)->count - 1);//使用快速排序對每個桶中的數進行排序，當然你可以使用任意一種排序 for (int j = 0; j count; j ) { a[pos ] = (pBucket i)->node[j]; } } free(pBucket);}

桶排序最好情況下使用線性時間O(n)，桶排序的時間複雜度，取決於對各個桶之間數據進行排序的時間複雜度，因為其它部分的時間複雜度都為O(n)。很顯然，桶劃分的越小，各個桶之間的數據越少，排序所用的時間也會越少。但相應的空間消耗就會增大。