Sort 5-count sort

Preface

One 、 Count sorting

thought ： Counting sorting is also called pigeon nest principle , It is an application of the deformation of hash table direct addressing method . Operation steps ：

1. Count the number of identical elements
2. According to the statistical results, the sequence is recycled into the original sequence

Absolute mapping ：

details ：
（1）： When the maximum value in the array is large , And the minimum value in the array is also large , So we open up B Space , There will be a lot of waste .

So relative mapping comes ：

Code ：（ Several details should be handled carefully ）

void CountSort(int* a,int n)
{
    
	//  Select the maximum value , minimum value 
	int i = 0,min = a[0],max = a[0];
	for(i = 0;i < n;i++)
	{
    
		if(a[i] > max)
			max = a[i];
		if(a[i] < min)
			min = a[i];
	}
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count,0,sizeof(int) * range);
	// Count 
	for(i = 0;i < n;i++)
	{
    
		count[a[i] -min]++;
	}
	int j = 0;
	// Sort 
	for(i = 0;i < range;i++)
	{
    
		while(count[i]--)
		{
    
			a[j++] = i + min;
		}
	}
}

summary ：

1. Count sort can only be used for integer sort
2. The efficiency of counting sorting in data range set is high , Limited application scenarios
3. Time complexity ：O(N~range)
4. Spatial complexity ：O(range)
5. stability ： Stable

See you next time .