Basic idea of counting and sorting

The so-called counting sort , Also known as hash table . It is also a simple hash bucket .

today , Xiaobian takes you to understand the basic idea of counting and sorting .

One . The basic idea

Take ascending order , Generally speaking, counting and sorting , There are three steps .

First make a bucket containing all the numbers to be sorted （ Make a bucket with the same number ）.

With 2,3,6,1,4,1,2,3,7,6,8,9,5,4,3 give an example , It's making 9 A barrel , Represent the 1,2,3,4,5,6,7,8,9.

The second step , Put all the numbers into the bucket in turn , The number in the bucket represents the number .

 

The third step , Take out all the numbers in the bucket from small to large .

Sort complete .

Xiaobian hopes that you can independently implement the code , Difficulty is not great , Believe in yourself ！

ps: Buckets can be replaced by array subscripts .

  Two . Code implementation

void CountSort(int* a, int n)
{
	if (n <= 0) return;
	assert(a);
	int min = a[0], max = a[0];
	for (int i = 0; i < n; i++)// Find the sorting range , Reduce space waste 
	{
		if (min > a[i]) min = a[i];
		if (max < a[i]) max = a[i];
	}
	int* tmp = (int*)new int[max - min + 1], range = max - min + 1;
	memset(tmp, 0, sizeof(int) * range);
	for (int i = 0; i < n; i++)// Into the barrel 
	{
		tmp[a[i] - min]++;
	}
	int sub = 0;
	for (int i = 0; i < range; i++)// Out of the barrel 
	{
		while (tmp[i]--)
		{
			a[sub++] = i + min;
		}
	}
}

3、 ... and . problem

Time complexity ：O（n)

Spatial complexity ：O（n)

The scope of counting and sorting is narrow , Floating point numbers 、 Structures and the like are not applicable , And the larger the scope, the more obvious the space complexity and space waste .

---

Let's support San Lian   If there is a mistake , Please correct