c/c++语言开发共享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);  	}  }