永发信息网

什么是桶排序,它和希尔排序的区别是什么?

答案:2  悬赏:20  手机版
解决时间 2021-03-22 07:39
什么是桶排序,它和希尔排序的区别是什么?
最佳答案
桶排序 (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

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

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);
shellInsert(pArrayData, Interval, pArrayNum);
}


}
#endif
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
电脑数据丢失和内存条有关系吗
我想问一下淘宝的运单模板是用来做什么的该怎
单选题决定你的眼睛是单眼皮还是双眼皮这一特
咸阳市秦都出租汽车客运服务部我想知道这个在
单选题中国近代史上一次开放通商口岸最多的不
阿里口号是什么意思,亲们孙孑开运动会需要加
自考大专工业经济管理,能否考一级建造师?
一次函数的K、b值分别表示什么意思,怎么理解
常温时,下列溶液的pH或微粒的物质的量浓度关
喜羊羊串吧在什么地方啊,我要过去处理事情
对佑荣告白的女艺人
明信片寄语文艺青春,给女生送明信片,可以写
10A 的插座,额定功率是多少
java.sql.SQLException: Access denied for u
单选题There'reafewapplesonthetree,_____
推荐资讯
北京试管婴儿的费用是多少
QQ 安全中心会提示异地登录 可是我都确认了都
地理信息系统 e00格式怎么转换为GIS支持的shp
描写竹子的优美段落,描写秋天中竹子坚强的优
4.8米等于多少公分
oppor7s为什么不能记步
Don’t women. They are as important as me
皮手套怎么清洗保存
柳州市走高速公路到海南三亚市需要多少过路费
什么牌子的竹席好,什么样的竹凉席才是好的凉
为什么有的教会光景好,有的光景不好?神为什么
如何加盟黛安芬内衣?黛安芬内衣加盟条件,黛安
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?