C語言深入探究選擇排序與基數排序使用案例講解

void SelectSort(int arr[], int len)
{
	for (int i = 0; i < len - 1; i++)//趟數
	{
		int min_index = i;
		for (int j = i + 1; j < len; j++)//控制找最小值
		{
			if (arr[j] < arr[min_index])
			{
				min_index = j;
			}
		}
		//當內層for循環跑完，此時min_index保存是就是當前待排序序列中最小值的下標
		if (min_index != i)//如果找到的最小值下標  不等於 待排序序列的第一個值的下標  則才有交換的必要性
		{
			int tmp = arr[i];
			arr[i] = arr[min_index];
			arr[min_index] = tmp;
		}
	}
}

//獲取數組中最大值的位數
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;
}
//這個函數告訴我傳進來的參數n的，對應fin位是多少
//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++)//這裡代表需要n 先丟幾位最低位
	{
		//n = n/10;
		n /= 10;
	}
	return n % 10;//此時獲取剩餘屬於的最低位即可
}
//一趟桶排序    fin代表這一趟是根據哪個位進行排序（個，十，百......）   0->個位  1->十位...
void Radix(int* arr, int len, int fin)//時間復雜度O(n)
{
	//先將10個桶申請好
	int bucket[10][100] = { 0 };
	int num[10] = { 0 };  //num[1] 代表1號桶中有多少個有效值
	//將所有數據從左向右向對應的桶中存放
	for (int i = 0; i < len; i++)
	{
		int index = Get_Num(arr[i], fin);
		bucket[index][num[index]] = arr[i];
		num[index]++;
	}
	//按照0->9號桶的順序，依次遵循先進先出的規則將所有值取出來
	int k = 0;
	for (int i = 0; i <= 9; i++)//0->9號桶依次取
	{
		for (int j = 0; j < num[i]; j++)//對應的桶內，從上到下依次取值
		{
			arr[k++] = bucket[i][j];//取出來的值 從前向後放到arr中
		}
	}
}
//基數排序（桶排序）  時間復雜度(d*n)（假設最大值的位數是d） 空間復雜度O（d*n） 穩定性：穩定
void RadixSort(int* arr, int len)
{
	//assert
	//1.首先需要知道 數據中最大值有多少位
	int count = Get_figure(arr, len);

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