基数排序-526互联

基于比较的排序，不需要数据具有特征，只需要告诉比较的规则，那么便可以排序，非常的通用。

不基于比较的排序，需要数据具有特征，有局限性，不是通用的。

基数排序是一种不基于比较的排序, 一般排序的是十进制的非负整数。

代码实现

//基数排序 
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 100

void RadixSort(int a[], int size, int base);//以base进制排序 
void radixSort(int a[], int size, int bits, int base);//bits代表数组中最大数在base进制的位数 
int bits(int n, int base);//返回n在base进制下的位数 

int main(int argc, char* argv[])
{
	int a[N] = { 0 };

	srand(time(0));

	for (int i = 0; i < N; i++) {
		sc("%d", a + i);
	}
	for (int i = 0; i < N; i++) {
		pr("%d ", a[i]);
	}
	pr("\n");

	RadixSort(a, N, 10);

	for (int i = 0; i < N; i++) {
		pr("%d ", a[i]);
	}

	return 0;
}
void RadixSort(int a[], int size, int base)
{
	int min = a[0];

	//求数组中的最小值 
	for (int i = 1; i < size; i++)
	{
		if (min > a[i]) {
			min = a[i];
		}
	}

	int max = 1 << 31;

	//求数组中的最大值 
	for (int i = 0; i < size; i++) {
		a[i] -= min;//数组中的每个数减去数组中的最小值，那么数组中也就没有负数了 
		if (a[i] > max) {
			max = a[i];
		}
	}

	radixSort(a, size, bits(max, base), base);

	//之前减去所以要还原成原来的数组 
	for (int i = 0; i < size; i++) {
		a[i] += a[min];
	}
}
int bits(int n, int base)
{
	int cnt = 0;

	while (n) {
		n /= base;
		cnt++;
	}

	return cnt;
}
void radixSort(int a[], int size, int bits, int base)
{
	int* cnt = (int*)malloc(sizeof(int) * base);//进制数组用来存放出现的次数 
	int* help = (int*)malloc(sizeof(int) * size);//开辟一个辅助数组 

	for (int offset = 1; bits > 0; bits--, offset *= base)//offset用来取每一位 
	{
		//清空计数数组 
		for (int i = 0; i < base; i++) {
			cnt[i] = 0;
		}

		//用来存放每个数出现的次数 
		for (int i = 0; i < size; i++) {
			cnt[(a[i] / offset) % base]++;
		}
	
		//求一遍前缀和，很妙 
		for (int i = 1; i < base; i++) {
			cnt[i] = cnt[i] + cnt[i - 1];
		}

		//从后开始存放，保证它的稳定性 
		for (int i = size - 1; i >= 0; i--) {
			help[--cnt[(a[i] / offset) % base]] = a[i];
		}
	
		//在把排序好的结果放回数组 
		for (int i = 0; i < size; i++) {
			a[i] = help[i];
		}
	}

	free(help);//释放空间 
	free(cnt);//释放空间 
}