八大排序之选择排序和基数排序（桶排序） ---（3）

选择排序

排序规则代码实现测试算法复杂度分析 基数排序（桶排序）

算法思想排序规则代码实现测试算法复杂度分析

一种直观简单的排序算法，从头到尾扫描序列，找出最小的一个元素与第一个元素交换，接着从剩下的元素中继续这种交换方式，最终得到一个有序序列

每一趟从待排序系列中找到最小值（下标）和待排序序列的第一个值（下标），然后将两个交换，直到待排序序列只剩下一个值。（每一次都找到一个最小值放在前面，需要n-1趟）

//选择排序
void SelectSort(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		int min_index = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[j] < arr[min_index])
			{
				min_index = j;  //保存待排序序列最小值的下标
			}
		}
		if (min_index != i) //如果找到的最小值下标 不等于 待排序序列的第一个值的下标 则才有交换的必要
		{
			Swap(&arr[min_index], &arr[i]);
		}
	}
}

时间复杂度: O ( n 2 ) O(n^{^{2}}) O(n2) 代码中采取了双层for循环
空间复杂度： O ( 1 ) O(1) O(1) ，没有用到额外的空间

桶排序，其原理是将数组分到有限数量的桶子里面，然后每个桶在分别排序，然后在按照一定的顺序合并所有的桶，则排序完成。

将所有数据从前向后按照个位、十位、百位…（低位优先）依次全部存放到对应的桶内，然后再从桶内全部取出（放入和取出规则按照队列，先进先出）

原始数据：12 32 2 620 42 98 122 289 987 37 56 90
这些数据其中最大的是三位数，所以需要进行三次桶排序

先进行个位排序
以个位排序的最终结果： 620 90 12 32 2 42 122 56 987 27 98 289 （这些数据只看个位是有序的）

以十位进行排序：
以十位进行排序最终结果： 2 12 620 122 27 32 43 56 987 289 90 98
（这些数据只看个位和十位的话，是有序的）

以百位进行排序
以百位进行排序的最终结果： 2 12 27 32 43 56 90 98 122 289 620 987
                                               数据已经完全有序

首先，我们需要获取所有数据中最大的位数来确定需要采取几趟桶排序，并且需要获取每个数据对应的位数是几，然后，采用二维数组来模拟桶来存放数据，具体程序实现如下：

//获取数组中最大值的位数
int Get_figure(int* arr, int len)
{
	int max = 0;
	int count = 0;
	for (int i = 0; i < len; i++)
	{
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	for ( count = 0; max > 0; count++)
	{
		max = max / 10;
	}
	return count;
}
//获取传进来参数n的，对应的fin位是多少
int Get_num(int n, int fin)
{
	for (int i = 0; i < fin; i++) // 这里代表n 先丢几位最低位
	{
		n = n / 10;
	}
		return n % 10;   //此时获取剩余属于的最低位即可
}
 //一趟桶排序
void Radix(int* arr, int len, int fin)
{
	//先将所有桶申请好
	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中
		}
	}
}
//基数排序
void RadixSort(int* arr, int len)
{
	assert(arr != 0);
	if (arr == NULL)
	{
		return;
	}
	for (int i = 0; i < Get_figure(arr,len); i++)
	{
		Radix(arr, len, i);
	}
}

时间复杂度： O ( d ⋅ n ) O(dcdot n) O(d⋅n) 其中 d d d表示采用几趟桶排序，也就是数据最多会有几位数
空间复杂度： O ( d ⋅ n ) O(dcdot n) O(d⋅n) 因为，每采用一次桶排序将用到额外的 n n n个空间，根据数据的位数，我们会采用 d d d次，所以是 d ⋅ n dcdot n d⋅n

并且基数排序算法是一个稳定的排序算法