數據結構—基數排序

原理：參考趣學數據結構

代碼：

#include<stdio.h> #include<stdlib.h> int getNumberBit(int number) {//獲取數字的位數int x = number,count=0;if (x == 0)return 1;while (x != 0) {count++;x /= 10;}return count; } int getlongBit(int a[],int length) {//獲取數組最長的位數int longBit = 0;for (int i = 0; i < length; i++) {int tempBit = getNumberBit(a[i]);if (tempBit> longBit) {longBit = tempBit;}}return longBit; } int getNumberNoValue(int number, int bit) {//獲取數字第bit位的值int value;while (bit) {value = number % 10;number /= 10;bit--;}return value; } void jiShuSort(int a[],int length){//基數排序int **b = (int **)malloc(10 * sizeof(int *));//二維數組10行int i;for (i = 0; i < 10; i++) {//默認十進制的每個數作為關鍵字進行比較b[i] = (int*)malloc((length + 1) * sizeof(int));b[i][0] = 0;//每行第一個數標記位數字是i的個數}int longBit = getlongBit(a, length);for (int bit = 1; bit <=longBit; bit++) {//分配for (int i = 0; i < length; i++) {int tempV = getNumberNoValue(a[i], bit);//第bit位的數值int index = ++b[tempV][0];b[tempV][index] = a[i];}int k = 0;for (int i = 0; i < 10; i++) {//收集，隊列的思想for (int j = 1; j <= b[i][0]; j++) {a[k++] = b[i][j];}b[i][0] = 0;//重新賦值為0，為下一次分配重新初始化}} } void print9(int a[], int length) {for (int i = 0; i < length; i++) {printf("%d ", a[i]);}printf("\n"); } int main() {int a[] = { 1,4,6,7,4,3,2,11,5,7,8,9,6,55 };int length = sizeof(a) / sizeof(a[0]);printf("排序前\n");print9(a, length);jiShuSort(a, length);printf("排序后\n");print9(a, length);system("pause");return 0; }

測試截圖：

時間復雜度O(n x n),空間復雜度O(n x n)

如果存在什么問題，歡迎批評指正！謝謝！

總結

以上是生活随笔為你收集整理的数据结构---基数排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。