什么是桶排序，它和希尔排序的区别是什么？

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

区别就是桶排序要求数据的长度必须完全一样，而希尔排序是非稳定排序算法。

废话不说了，我把代码以及说明贴给你

#ifndef Bucket_Sort_H
#define Bucket_Sort_H
#include
#include"Quick_Sort.h"
#define Multi 10
/***************************************************************************
函数说明：桶排序
参数说明：A(输入的无序数组)，Size(数组A的长度)
说明：桶排序假设输入是由一个随机过程产生，该过程将元素均匀而独立的分布在[0,1)中；
	  以线性时间运行，即算法的时间复杂度为Theta(n)，当然空间复杂度将是Theta(square(n))
****************************************************************************/
template  void  Bucket_Sort(T *A, int Size)
{
	T * Bucket_array[10];
	for (int i = 0; i < Size; i++)
		Bucket_array[i] = new T[sizeof(T)*(Size+1)];//生成一个（Size+1）*（Size+1）的矩阵

	for (int i = 0; i < Size; i++)
		Bucket_array[i][0] = 0;//首位用来放置元素个数

	for (int j = 0; j < Size; j++)
	{
		int Num = (int)(Multi*A[j]);
		int index = ((int)(Bucket_array[Num][0]))+1;
		Bucket_array[Num][index] = A[j];
		Bucket_array[Num][0]++;
	}

	for (int k = 0; k < Size; k++)
	{
		Quick_Sort(Bucket_array[k], 1, Bucket_array[k][0]);
	}

	for (int i = 0, j = 0; i < Size; i++)     
	{
		for (int k = 1; k <= Bucket_array[i][0]; k++)
			A[j++] = Bucket_array[i][k];
		Bucket_array[i][0] = 0;//归零
	}

	for (int i = 0; i <10; i++)//十个连续的数组空间，0~9
	{
		delete[] Bucket_array[i];

	}
	
}
#endif

#ifndef Shell_Sort_H

#define Shell_Sort_H

/*

平均时间复杂度：希尔排序的时间复杂度和其增量序列有关系，这涉及到数学上尚未解决的难题；不过在某些序列中复杂度可以为O(n1.3);

空间复杂度：O(1)

稳定性：不稳定

*/

templatevoid shellInsert(T *pArrayData, int Interval, int pArrayNum)

{

for (int i = Interval; i <= pArrayNum; i++)

{

int j = i - Interval;

T temp = pArrayData[i];    //记录要插入的数据

while (j >= 0 && pArrayData[j] > temp)    //从后向前，找到比其小的数的位置  

{

pArrayData[j + Interval] = pArrayData[j];    //向后挪动  

j -= Interval;

}

if (j != i - Interval)    //存在比其小的数  

pArrayData[j + Interval] = temp;

}

}

template void  Shell_Sort(T *pArrayData,int pArrayNum)

{

int Interval = pArrayNum;//跳跃的间隔

bool flag = 0;

while ((Interval >= 1)&&!flag)

{

if (Interval < 5)

{

Interval = 1;

flag=1;

}

else

Interval = (int)((Interval * 5 - 1) / 11);/* 间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。

这个约束条件使每一趟排序更有可能保持前一趟排序已排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。*/

shellInsert(pArrayData, Interval, pArrayNum);

}

}

#endif