算法导论 学习问题

《算法导论》里的COUNTING_SORT，用C++实现有问题：

#include<iostream>
#include<vector>
using namespace std;

void COUNTING_SORT(vector<int>&A, vector<int>&B, const int& k)
{
	int* C = new int[k + 1]();
	for (unsigned j = 0; j < A.size(); ++j)
		++C[A[j]];
	for (int i = 1; i <= k; ++i)
		C[i] += C[i - 1];
	for (int j = A.size() - 1; j >= 0; --j)                  
	{
		B[C[A[j]]] = A[j];              //问题在这里
		--C[A[j]];
	}
	delete[] C;
}

int main()
{
	vector<int>coll{ 1, 2, 4, 3, 8, 7, 9, 10, 14, 16 };
	for (auto index : coll)
		cout << index << "   ";
	cout << endl;
	vector<int>coll2(coll.size()+1,0);                //B的size要比A大1，因为前面有1个0，如果不加1的话，vector就会Out of range
	COUNTING_SORT(coll, coll2, 16);                   //至于如何解决这个加1的问题我还不知道。
	for (auto index : coll2)
		cout << index << "   ";
	cout << endl;
	return 0;
}

A的编号：  0   1   2   3   4   5   6   7   8   9

A（coll）：1   2   4   3   8   7   9   10  14  16

C的编号：  0   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16
C        ：0   1   1   1   1   0   0   1   1   1    1    0    0    0    1    0    1
C[i] += C[i - 1];之后：
C的编号：  0   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16
C        ：0   1   2   3   4   4   4   5   6   7    8    8    8    8    9    9    10

B的编号：   0   1   2   3   4   5   6   7   8   9    10

B（coll2):  0   1   2   3   4   7   8   9   10  14   16

如上所示，B的0位多了1个0，而多了一个B[10]位，所以如果B与A一样大的话，则out of range。

至于如何解决问题我不知道。

算法导论 学习问题,布布扣,bubuko.com

算法导论 学习问题

原文：http://blog.csdn.net/u014120684/article/details/25132711