【排序算法 C++和Python实现】分配排序——基数排序

分配排序——基数排序

C++python

#include 
#define N 10
using namespace std;
// 求待排序序列最大元素位数，例如124最大元素位数为3
int MaxBit(int A[], int n)
{
	// 初始化最大元素为A[0],最大位数为0
	int maxValue = A[0], digits = 0;
	// 求最大值
	for (int i = 1; i < n; i++)
	{
		if (A[i] > maxValue) maxValue = A[i];
	}
	// 分解得到最大元素的位数
	while (maxValue!=0)
	{
		digits++;
		maxValue /= 10;
	}
	return digits;
}
// 求x第bit位上的数字，如238第2位上的数字为3
int BitNumber(int x, int bit)
{
	int temp = 1;
	for (int i = 1; i < bit; i++)temp *= 10;
	return (x / temp) % 10;
}
void RadixSort(int A[], int n)
{
	int i, j, k, b, bMax;
	bMax = MaxBit(A, n); // 求最大元素位数
	// 分配空间
	int** B = new int* [10];  // 十个桶0,1...9
	// 为每个桶分配空间,B[i][0]统计第i个桶的元素个数
	for (i = 0; i < 10; i++) B[i] = new int[n + 1];
	for (i = 0; i < 10; i++)B[i][0] = 0;
	// 从个位到高位，对不同的位数进行桶排序
	for (b = 1; b <= bMax; b++)
	{
		for (j = 0; j < n; j++) // 分配
		{
			int num = BitNumber(A[j],b);// 取A[j]第b位上的数字
			int index = ++B[num][0]; // 桶内数字索引
			B[num][index] = A[j];
		}
		for (i = 0,j = 0; i < 10; i++) // 收集:先入先出
		{
			for (k = 1; k <= B[i][0]; k++) 
				A[j++] = B[i][k];   
			B[i][0] = 0;  // 收集后元素个数置零
		}
	}	
	//释放空间
	for (int i = 0; i < 10; i++)  delete[]B[i];
	delete []B;
}

int main()
{
	int numbers[N] = { 23,12,41,55,56,62,98,96,79,87 };
	RadixSort(numbers, N);
	for (int i = 0; i < N; i++)
		cout << numbers[i] << " ";
	cout << "n";
	return 0;
}

def maxBit(A):
    digits = 0
    maxValue = max(A)
    while maxValue != 0:
        digits += 1
        maxValue //= 10
    return digits


def bitNumber(x, bit):
    temp = 1
    for i in range(1, bit):
        temp *= 10
    return int((x / temp) % 10)


def radixSort(A, n):
    bit_max = maxBit(A)

    for b in range(1, bit_max + 1):
        buckets = [[] for _ in range(10)]  # 10个桶
        for j in range(n):  # 收集
            num = bitNumber(A[j], b)  # 取A[j]第b位上的数字
            buckets[num].append(A[j])
        j = 0
        for i in range(10):   #  分配
            length = len(buckets[i])
            A[j:j + length] = buckets[i]
            j += length


if __name__ == '__main__':
    r = [4, 23, 12, 41, 55, 56, 62, 98, 96, 79, 87]
    radixSort(r, len(r))
    print(r)