排序算法总结—时间复杂度O(n)—基数排序
基数排序
分为最高位优先和最低位优先的算法。
找到最大值max，求出max的位数。在max位数max—length进行循环max-length趟。对于每一位进行排序，对于一个数字要会从低位一位一位取值，合理使用/10，%10。
（对于大于0的数据范围，通常是10位，如果数据中有负数，要取19位。
开辟一个计数数组count，对于出现几次就对应的数字count+1。
count对应的直接就是该数字对应的下标（后序放入数组），当后序放入数组时，我们将同样的数字对应的count值-1，便于存储下一个同样的数字，不会冲突或溢出。
下面有一个前序放入的计数排序代码，count值++操作；
以王道书为主：
时间复杂度 O（d（n+r）） d趟分配和收集，一趟分配O（n），一趟收集O（r）
空间复杂度（书中是采用了r个队列）O（r）
稳定 稳定！老稳了！🌸
void copy(int arr[],int nums[],int len) { for(int i = 0;i < len;i++) { nums[i] = arr[i]; } } void set_0(int arr[],int len) { for(int i = 0;i < len;i++) { arr[i] = 0; } } int maximumGap(int* nums, int numsSize){ if(numsSize < 2) return 0; int cha = 0; int max = 0,max_length = 0; int count[10]; int arr[numsSize]; int ten = 1; set_0(arr,numsSize); for(int i = 0;i < numsSize;i++) { if(max < nums[i]) { max = nums[i]; } } while(max > 0) { max = max / 10; max_length++; } set_0(count,10); while(max_length--) { for(int j = 0;j < numsSize;j++) { int r = nums[j] / ten % 10; count[r]++; } for(int k = 1;k < 10;k++) { count[k] += count[k-1]; } for(int m = numsSize-1;m >= 0;m--) { int r = nums[m] / ten % 10; arr[count[r]-1] = nums[m]; count[r]--; } copy(arr,nums,numsSize); ten *= 10; set_0(count,10); } for(int k = 0; k < numsSize-1;k++) { if(cha < nums[k+1]-nums[k]) { cha = nums[k+1] - nums[k]; } } return cha; }
我们可以了解一个计数排序的基础：
了解最大值 最小值作用 统计一个数出现n次，直接排位置。
也leetcode 排序数组例题为例。
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* sortArray(int* nums, int numsSize, int* returnSize){ *returnSize = numsSize; int max = nums[0]; int min = nums[0]; for(int i = 0;i < numsSize;i++) { if(max < nums[i]) max = nums[i]; if(min > nums[i]) min = nums[i]; } // printf("%d %d",min,max); int elemSize = max-min + 1; int count[elemSize]; //计数数组 for(int i = 0;i < elemSize;i++) { count[i] = 0; } for(int j = 0;j < numsSize;j++) { count[nums[j]-min]++; //计数 有几个相同的数字 } int precount = 0; for(int i = 0;i < elemSize;i++) { precount += count[i]; count[i] = precount - count[i]; // printf("%d ",count[i]); } int *returns = (int*)malloc(sizeof(int )* numsSize); for(int k = 0;k < numsSize;k++) { returns[count[nums[k]-min]] = nums[k]; count[nums[k]-min]++; } return returns; }
撒花，再撒，嘿嘿
