非比较排序——基数排序

xiaoxiao2021-02-28  38

【基数排序】 又名桶排序 LSD(Least Significant Digit first ) MSD(Most Significant Digit first)

基本思想: 首先根据个位数的数值,在遍历数据时将它们各自分配到编号0-9的桶(个位数值与桶号一一对应)中。 分配结束后,接下来将所有桶中所盛数据按照桶号由小到大(桶中按先进先出)依次重新收集串起来,得到的仍是无序的数列; 同理,根据十位数据进行分配,依次类推

主要步骤: (1)统计每个桶的元素个数; (2)统计每个桶的起始地址; (3)将数据放到对应桶中; (4)进行数据回收(按桶编号从小到大,每个桶按先进先出的顺序)

**时间复杂度:O(mn)**m:代表数据的位数 空间复杂度:O(n)

代码如下:

void RadixCount(int* array, int size) { int bitCount = GetBitCount(array, size); int bitIdx = 0; int radix = 1; int* tmp = (int *)malloc(sizeof(array[0]) * size); for (bitIdx = 0; bitIdx < bitCount; bitIdx++) { int count[10] = { 0 }; int i = 0; int StartAddr[10] = { 0 }; //统计每个桶的元素个数 for (i = 0; i < size; i++) count[array[i] / radix % 10]++; //统计每个桶的起始地址 for (i = 1; i < size; i++) StartAddr[i] = StartAddr[i - 1] + count[i - 1]; //将数据放到对应桶中 for (i = 0; i < size; i++) { int bucketNo = (array[i] / radix) % 10; tmp[StartAddr[bucketNo]] = array[i]; StartAddr[bucketNo]++; } //回收数据(按桶编号从小到大,每个桶按先进先出) memcpy(array, tmp, sizeof(array[0]) * size); radix *= 10; } free(tmp); } int GetBitCount(int* array, int size) { int count = 1; int radix = 10; //设置的基数 int i = 0; for (i = 0; i < size; i++) { while (array[i] >= radix) { count++; radix *= 10; } } return count; }
转载请注明原文地址: https://www.6miu.com/read-2250032.html

最新回复(0)