Select sort / cardinality sort

Selection sort ： Find the minimum value subscript and the first value subscript of the sequence to be sorted in each pass , Then exchange the two , Until there is only one value left in the sequence to be sorted

Code ：

// Selection sort    Time complexity O（n^2）   Spatial complexity O（1）  stability ： unstable 
void SelectSort(int arr[], int len)
{
	for(int i=0; i<len-1; i++)// Number of trips 
	{
		int min_index = i;
		for(int j=i+1; j<len; j++)// Control to find the minimum value 
		{
			if(arr[j] < arr[min_index])
			{
				min_index = j;
			}
		}

		// When the inner layer for Finish the cycle , here min_index Save is the subscript of the minimum value in the current sequence to be sorted 
		if(min_index != i)// If you find the lowest subscript    It's not equal to   The subscript of the first value of the sequence to be sorted    Then there is the necessity of exchange 
		{
			int tmp = arr[i];
			arr[i] = arr[min_index];
			arr[min_index] = tmp;
		}


	}
}

Radix sorting （ Bucket sort ）

 

 

  Chain type is not used here , Use arrays , But the basic idea is the same

Code ：

// Gets the number of digits of the maximum value in the array 
int Get_figure(int *arr, int len)
{
	int max = 0;
	for(int i=0; i<len; i++)
	{
		if(arr[i] > max)
		{
			max = arr[i];
		}
	}

	int count = 0;
	while(max != 0)
	{
		count++;
		max /= 10;
	}

	return count;
}
// This function tells me the parameters passed in n Of , Corresponding fin What is the number of bits 
//1234,2 -> 2    345,1 ->4    0078,3 -> 0     56789,4 -> 5
int Get_Num(int n, int fin)
{
	for(int i=0; i<fin; i++)// This represents the need for n  Throw a few lowest positions first 
	{
		//n = n/10;
		n /= 10;
	}

	return n%10;// At this point, you can get the lowest bit of the remaining 
}
// One bucket sort     fin Represents which bit is sorted according to this trip （ individual , Ten , hundred ......）   0-> bits   1-> ten ...
void Radix(int *arr, int len, int fin)// Time complexity O(n)
{
	// First the 10 Apply for a bucket 
	int bucket[10][100] = {0};
	int num[10] = {0};  //num[1]  representative 1 How many valid values are there in bucket No 

	// Store all data from left to right in the corresponding bucket 
	for(int i=0; i<len; i++)
	{
		int index = Get_Num(arr[i], fin);
		bucket[index][num[index]] = arr[i];
		num[index]++;
	}


	// according to 0->9 The order of barrels , Follow the first in first out rule in turn to get all values 
	int k = 0;
	for(int i=0; i<=9; i++)//0->9 Take the No. barrel in turn 
	{
		for(int j=0; j<num[i]; j++)// Corresponding barrel , Take values from top to bottom 
		{
			arr[k++] = bucket[i][j];// The value taken out   Put... From front to back arr in 
		}
	}
}
// Radix sorting （ Bucket sort ）   Time complexity (d*n)（ Suppose the number of digits of the maximum value is d）  Spatial complexity O（d*n）  stability ： Stable 
void RadixSort(int *arr, int len)
{
	//assert
	//1. The first thing you need to know is   How many digits is the maximum value in the data 
	int count = Get_figure(arr, len);

	for(int i=0; i<count; i++) //D
	{
		Radix(arr, len, i); 
	}
}