MT5(C++)软件编程-桶排序算法

1. MT5(C++)软件编程十大排序算法 - 冒泡排序算法 (bubble Sort)
2. MT5(C++)软件编程十大排序算法 - 选择排序算法 (select Sort)
3. MT5(C++)软件编程十大排序算法 - 插入排序算法 (insert Sort)
4. MT5(C++)软件编程十大排序算法 - 快速排序算法 (quick Sort)
5. MT5(C++)软件编程十大排序算法 - 希尔排序算法 (shell Sort)
6. MT5(C++)软件编程十大排序算法 - 堆排序算法 (heap Sort)
7. MT5(C++)软件编程十大排序算法 - 归并排序算法 (merge Sort)
8. MT5(C++)软件编程十大排序算法 - 计数排序算法 (counting Sort)
9. MT5(C++)软件编程十大排序算法 - 桶排序算法 (bucket Sort)
10. MT5(C++)软件编程十大排序算法 - 基数排序算法 (radix Sort)

桶排序算法
最大和最小数之间分割出指定的桶数
arr: 需要排序的数组
bucket_size:桶的分割数量 最高不能超过20个桶
seq: 排序的方向, true 为升序, false为降序

template < typename T>
void bucketSort(T &arr[], const int bucket_size = 10)
{
  int len = ArraySize(arr);
  int max_num = max(arr);
  int min_num = min(arr);
  int def = -1;
  // printf("最小数: %d, 最大数: %d", min_num, max_num);
  // 默认最高上限20个桶
  int buckets[][10]; // 桶长度
  int bucket_len[]; // 每个桶里面数据的长度
  int bucket_nums[][2]; // 每个桶的范围
  //扩展数组
  ArrayResize(buckets,len *10);
  ArrayResize(bucket_len,bucket_size);
  ArrayResize(bucket_nums,bucket_size*2);
  ArrayInitialize(buckets, def);
  int gap =  (max_num - min_num + 1) / bucket_size;
  if(gap < min_num)gap = min_num;
  // printf("当前范围: %d, 最大数: %d",bucket_size);
  for(int i = 0; i < bucket_size;i++)
  {
    bucket_nums[i][0] =min_num + gap * i;
    bucket_nums[i][1] =min_num + gap * (i + 1);
    printf("当前范围: %d, 最大数: %d",bucket_nums[i][0],bucket_nums[i][1]);
    
  }
  for(int i=0;i<len; i++)
  {
    // 放入桶中
    for(int j=bucket_size - 1;j >= 0;j--)
     {
      
        // 判断当前元素适合放入几号桶
        if(arr[i] >= bucket_nums[j][0])
        {
          // 将值放入到指定的桶中
          ArrayPrint(bucket_nums);
          for(int k=0;k < bucket_size;k++)
          {
            // 向后插入到不是默认值的位置
            if(buckets[k][j] == def)
            {
              buckets[k][j] = arr[i]; // 将数据放入到桶中
              bucket_len[j] = k; // 记录当前桶的长度
              int z = k;
              // 将已经插入的有序列表重新排列
              while(z>0)
              {
                if(buckets[z - 1][j] > buckets[z][j]) swap(buckets[z - 1][j],buckets[z][j]);
                z--;
              }
              break;
              
            }
            
          }
          break;
        }
     }
        
  }
  T copy_arr[];
     // 将所有桶的数据进行还原
     for(int i=0;i<bucket_size; i++)
     {
      for(int j = 0; j < len;j++)
      {
        if(buckets[j][i] != def)
        {
        
        ArrayResize(copy_arr,ArraySize(copy_arr) + 1);
        copy_arr[ArraySize(copy_arr) - 1] = buckets[j][i];
        }
        else break; // 每个没有值了就跳出当前子循环
      }
      
     }

}

template < typename T> 
void _buckle_sort(T &arr[], int len,int div)//div表示取位数的余数
{
	//要申请一个二维10*10的数组区保存数字
	int bucket[10][10];
	int def = -1; // 初始化数字
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			bucket[i][j] = def;
		}
	}
	int temp = 1;
	for (int i=1; i < div; i++)
	{
		temp = temp * 10;//求出第几位余数
	}
	for (int i = 0; i < len; i++)
	{		
		int k = (arr[i]/temp) % 10;//求第几位的余数
		for (int j = 0; j < 10; j++)
		{
			if (bucket[k][j] == def)
			{
				bucket[k][j] = arr[i];
				break;
			}
		}
	}
	//出桶
	int k = 0;
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < len; j++)
		{
		  int len1 = ArrayRange(bucket,0);
		  int len2 = ArrayRange(bucket,1);
		  printf("一维长度: %d, 二维长度: %d",len1,len2);
		  printf("一维数字: %d, 二维数字: %d",i,j);
			if (bucket[i][j] != def)
			{
				arr[k] = bucket[i][j];
				k++;//去遍历桶 让桶的所有数字都出来
				bucket[i][j] = def;
			}
		}
	}
}

//求最大位数的函数
template < typename T>
int _getmaxweisu(T &arr[],int len)//
{
	int max = arr[0];
	for (int i = 0; i < len; i++)
	{
		if (max < arr[i])
		{
			max = arr[i];
		}
	}
	int count = 1;
	while (bool(max/10))
	{
		count++;
		max /= 10;
	}
	return  count;
}