基数排序问题与解决

问题描述

因为引理中提到，

对于n位数，单位数的最大值为k，若稳定排序需要Θ(k+n)时间，则Radix sort需要Θ(d(k+n))时间。

因此一开始想用Counting sort来进行一位的排序。
代码如下：

Array stableSort(Array A, int n, int d){
	int k = 10;//因为排序的是位，最大值直接定为9 
	Array B = (ElemType*)malloc(k * sizeof(ElemType));
	Array C = (ElemType*)malloc(n * sizeof(ElemType));
	Array D = getSubArray(A, n, d); //第d位的数 
	for(int i = 0; i < k; i++){
		B[i] = 0;
	}
	for(i = 0; i < n; i++){
		B[D[i]]++;
	}
	for(i = 1; i < k; i++){
		B[i] += B[i - 1];
	}
	for(i = 0; i < n; i++){
		B[D[i]]--;
		C[B[D[i]]] = A[i];
	}
	return A;
}

Array RADIX_SORT(Array A, int n, int d){
	for(int i = 1; i <= d; i++){
		A = stableSort(A, n, i);
	}
	return A;
}

测试数据始终不对。后来意识到Counting sort中相同取值的数的输出顺序与输入顺序无关，因此不适用于Radix sort。
第二次还是没想放弃效率较高的算法，采用了Quicksort。
代码如下：

int PARTITION(Array &A, Array &D, int p, int r){
	int j = p;
	for(int i = p; i < r; i++){
		if(D[i] < D[r]){
			exchange(A, i, j);
			exchange(D, i, j);
			j++;
		}
	}
	exchange(A, j, r);
	exchange(D, j, r);
	return j;
}

void QUICKSORT(Array &A, Array &D, int p, int r){
	if(p >= r) return;
	int q = PARTITION(A, D, p, r);
	QUICKSORT(A, D, p, q - 1);
	QUICKSORT(A, D, q + 1, r);
}

Array RADIX_SORT(Array A, int n, int d){
	for(int i = 1; i <= d; i++){
		Array D = getSubArray(A, n, i); //第d位的数 
		QUICKSORT(A, D, 0, n - 1);
	}
	return A;
}

发现测试数据仍不对。又意识到Quicksort其实也没有让相同取值的数的输出顺序与输入顺序相同。
为了尽快完成任务，最后采用了效率低但是输出正确的冒泡排序。

void stableSort(Array &A, Array D, int n){
	for(int i = 0; i < n - 1; i++){
		for(int j = i; j < n - 1; j++){
			if(D[j] > D[j + 1]){
				exchange(A, j, j + 1);
				exchange(D, j, j + 1);
			}
		}
	}
}

Array RADIX_SORT(Array A, int n, int d){
	for(int i = 1; i <= d; i++){
		Array D = getSubArray(A, n, i); //第d位的数 
		stableSort(A, D, n);
	}
	return A;
}

分析

1. 对各个排序算法的适用性不太熟悉。
2. 对各个算法的书写也没完全掌握，在写不同算法时，仍会有很多小bug。

总结

因为对算法的不熟悉，导致耗费了大量时间在这一个简单的算法上。但从另一个角度说，也算是加深了对算法的理解，并且对vc++的调试更熟悉了。