什么是哈希排序算法
答案:4 悬赏:10
解决时间 2021-10-13 18:08
- 提问者网友：情歌越听越心酸
- 2021-10-13 11:10
什么是哈希排序算法
最佳答案
- 二级知识专家网友：夜余生
- 2021-10-13 12:26
希尔排序(Shell Sort)是插入排序的一种。因D．L．Shell于1959年提出而得名。
希尔排序基本思想
基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt< dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
给定实例的shell排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，3，1
排序过程如【动画模拟演示】。
Shell排序的算法实现
1． 不设监视哨的算法描述
void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d为当前增量
for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区
if(R[ i ].key<R[i-d].key){
R[0]=R;j=i-d； //R[0]只是暂存单元，不是哨兵
do {//查找R的插入位置
R[j+d]=R[j]； //后移记录
j=j-d； //查找前一记录
}while(j>0&&R[0].key<R[j].key)；
R[j+d]=R[0]； //插入R到正确的位置上
} //endif
} //ShellPass
void ShellSort(SeqList R)
{
int increment=n； //增量初值，不妨设n>0
do {
increment=increment/3+1； //求下一增量
ShellPass(R，increment)； //一趟增量为increment的Shell插入排序
}while(increment>1)
} //ShellSort
注意：
当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。
2．设监视哨的shell排序算法
具体算法【参考书目[12] 】
算法分析
1．增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。
2．Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插人排序有较大的改进。
3．稳定性
希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。
选择排序
选择排序的基本思想是：
对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
例1:输入序列数据按非减顺序输出.
程序如下:
program xzpx;
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a);
writeln;
for i:=1 to n-1 do
begin
k:=i;
for j:=i+1 to n do
if a[j]<a[k] then k:=j;
if k<>i then
begin t:=a;a:=a[k];a[k]:=t;end;
end;
write('output data:');
for i:= 1 to n do write(a:6);
writeln;
end.
[编辑本段]
希尔排序的JAVA实现
public class Test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length;// 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
ShellSort(Index - 1); // 选择排序
// 排序后结果
System.out.print("排序后: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
}
public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
a[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}
}
希尔排序基本思想
基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt< dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
给定实例的shell排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，3，1
排序过程如【动画模拟演示】。
Shell排序的算法实现
1． 不设监视哨的算法描述
void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d为当前增量
for(i=d+1;i<=n；i++) //将R[d+1．．n]分别插入各组当前的有序区
if(R[ i ].key<R[i-d].key){
R[0]=R;j=i-d； //R[0]只是暂存单元，不是哨兵
do {//查找R的插入位置
R[j+d]=R[j]； //后移记录
j=j-d； //查找前一记录
}while(j>0&&R[0].key<R[j].key)；
R[j+d]=R[0]； //插入R到正确的位置上
} //endif
} //ShellPass
void ShellSort(SeqList R)
{
int increment=n； //增量初值，不妨设n>0
do {
increment=increment/3+1； //求下一增量
ShellPass(R，increment)； //一趟增量为increment的Shell插入排序
}while(increment>1)
} //ShellSort
注意：
当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越界。
2．设监视哨的shell排序算法
具体算法【参考书目[12] 】
算法分析
1．增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。
2．Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插人排序有较大的改进。
3．稳定性
希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。
选择排序
选择排序的基本思想是：
对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
例1:输入序列数据按非减顺序输出.
程序如下:
program xzpx;
const n=7;
var a:array[1..n] of integer;
i,j,k,t:integer;
begin
write('Enter date:');
for i:= 1 to n do read(a);
writeln;
for i:=1 to n-1 do
begin
k:=i;
for j:=i+1 to n do
if a[j]<a[k] then k:=j;
if k<>i then
begin t:=a;a:=a[k];a[k]:=t;end;
end;
write('output data:');
for i:= 1 to n do write(a:6);
writeln;
end.
[编辑本段]
希尔排序的JAVA实现
public class Test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length;// 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
ShellSort(Index - 1); // 选择排序
// 排序后结果
System.out.print("排序后: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
}
public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暂存Data[j]的值,待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
a[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}
}
全部回答
- 1楼网友：雪起风沙痕
- 2021-10-13 13:31
兄弟，给你英文版没意见吧。
Donald L. Shell was born on a farm near Croswell, Michigan, on March 1, 1924. Because of his aptitude for education, the day of his sixth birthday he started studying at the local school house. He progressed quickly and went to Michigan Technological University where he acquired a BS in Civil Engineering in three years.
After acquiring the BS, he went into the Army Corps of Engineers, and from there to Philippines to help repair damages during the World War II. When he returned after the war, he married Alice McCullough and returned to Michigan Technological University, where he taught mathematics. After, he moved to Cincinnati, Ohio, and worked for General Electric's engines division, where he developed a convergence algorithm and wrote a program to perform calculations for the performance cycle for aircraft jet engine. He also went to the University of Cincinnati, where in 1951 he acquired a M.S. in mathematics, and 8 years later, in 1959, he acquired his Ph.D. in Mathematics. In July the same year he published the shell sort algorithm[1] and "The Share 709 System: A Cooperative Effort". The year before, in 1958, he and A. Spitzbart published "A Chebycheff Fitting Criterion".
Although he is widely known mostly for his shell sort algorithm, his Ph.D. is also considered by some to be the first major investigation of the convergence of infinite exponentials, with some very deep results of the convergence into the complex plane. This area has grown considerably and research related to it is now investigated in what is more commonly called Tetration.
After acquiring his Ph.D., Dr. Shell moved to Schenectady, New York, to become Manager of Engineering for a new department of General Electric known as the Information Services Department, the first commercial enterprise to link computers together with the client-server architecture. In October, 1962 he wrote "On the Convergence of Infinite Exponentials" in the Proceedings of the American Mathematical Society. He worked with John George Kemeny and Thomas Eugene Kurtz to commercialize the Dartmouth Time-Sharing System in 1963.
In 1971 Dr. Shell wrote "Optimizing the Polyphase Sort" in the Communications of the ACM, and in 1972 he joined with Mr. Ralph Mosher, a close friend and colleague, to start a business called Robotics Inc. where he was the General Manager and chief software engineer. Four years later, in 1976, they sold the company and Dr. Shell returned to General Electric Information Services Corporation. In 1984 he retired and moved to North Carolina where he lives today.
中文翻出来了。(真累）
1924年，唐纳德.希尔出生在美国密歇根州克罗斯韦附近的一个农场。由于天资聪颖，6岁生日时他开始在当地的学校上学。他学习进步很快，考上密歇根大学并于3年后获得该校的理科学士学位。
   获得理科学士学位后，希尔成为军方的一名工程师，被调往菲律宾修理损坏的设备，当时正处于第二次世界大战时期。战后他回到美国，取了爱丽丝。Mc克劳为妻。他回到密歇根技术工程大学任数学教师。后来，他去过辛辛那提州、俄亥俄州，为通用电气公司工作。其间，他发明了一种收敛算法，写了一个程序为喷气式动力引擎的运转作计算。  他也去过辛辛那提大学就读，1951年他获得数学方面的理科硕士。8年后，即1959年，他成为数学博士生。同年7月，他发表了“希尔排序算法”和“The share 709 System: A Cooprative Effort”。而之前一年，。。。
待续。。。参考资料：www
- 2楼网友：逐風
- 2021-10-13 13:21
哈希算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。
哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。
哈希
通过将单向数学函数（有时称为“哈希算法”）应用到任意数量的数据所得到的固定大小的结果。如果输入数据中有变化，则哈希也会发生变化。哈希可用于许多操作，包括身份验证和数字签名。也称为“消息摘要”。
哈希算法
用来产生一些数据片段（例如消息或会话项）的哈希值的算法。使用好的哈希算法，在输入数据中所做的更改就可以更改结果哈希值中的所有位；因此，哈希对于检测数据对象（例如消息）中的修改很有用。此外，好的哈希算法使得构造两个相互独立且具有相同哈希的输入不能通过计算方法实现。典型的哈希算法包括 MD2、MD4、MD5 和 SHA-1。哈希算法也称为“哈希函数”。
另请参阅： 基于哈希的消息验证模式 (HMAC), MD2, MD4, MD5, 消息摘要, 安全哈希算法 (SHA-1)
MD5一种符合工业标准的单向 128 位哈希方案，由 RSA Data Security, Inc. 开发。 各种“点对点协议 (PPP)”供应商都将它用于加密的身份验证。哈希方案是一种以结果唯一并且不能返回到其原始格式的方式来转换数据（如密码）的方法。质询握手身份验证协议 (CHAP) 使用质询响应并在响应时使用单向 MD5 哈希法。按照此方式，您无须通过网络发送密码就可以向服务器证明您知道密码。
质询握手身份验证协议 (CHAP)“点对点协议 (PPP)”连接的一种质询响应验证协议，在 RFC 1994 中有所描述。 该协议使用业界标准 MD5 哈希算法来哈希质询串（由身份验证服务器所发布）和响应中的用户密码的组合。
点对点协议 (PPP)
用点对点链接来传送多协议数据报的行业标准协议套件。RFC 1661 中有关于 PPP 的文档。
另请参阅： 压缩控制协议 (CCP), 远程访问, 征求意见文档 (RFC), 传输控制协议/Internet 协议 (TCP/IP), 自主隧道
- 3楼网友：骨子里都是戏
- 2021-10-13 12:32
兄弟，给你英文版没意见吧。
Donald L. Shell was born on a farm near Croswell, Michigan, on March 1, 1924. Because of his aptitude for education, the day of his sixth birthday he started studying at the local school house. He progressed quickly and went to Michigan Technological University where he acquired a BS in Civil Engineering in three years.
After acquiring the BS, he went into the Army Corps of Engineers, and from there to Philippines to help repair damages during the World War II. When he returned after the war, he married Alice McCullough and returned to Michigan Technological University, where he taught mathematics. After, he moved to Cincinnati, Ohio, and worked for General Electric's engines division, where he developed a convergence algorithm and wrote a program to perform calculations for the performance cycle for aircraft jet engine. He also went to the University of Cincinnati, where in 1951 he acquired a M.S. in mathematics, and 8 years later, in 1959, he acquired his Ph.D. in Mathematics. In July the same year he published the shell sort algorithm[1] and "The Share 709 System: A Cooperative Effort". The year before, in 1958, he and A. Spitzbart published "A Chebycheff Fitting Criterion".
Although he is widely known mostly for his shell sort algorithm, his Ph.D. is also considered by some to be the first major investigation of the convergence of infinite exponentials, with some very deep results of the convergence into the complex plane. This area has grown considerably and research related to it is now investigated in what is more commonly called Tetration.
After acquiring his Ph.D., Dr. Shell moved to Schenectady, New York, to become Manager of Engineering for a new department of General Electric known as the Information Services Department, the first commercial enterprise to link computers together with the client-server architecture. In October, 1962 he wrote "On the Convergence of Infinite Exponentials" in the Proceedings of the American Mathematical Society. He worked with John George Kemeny and Thomas Eugene Kurtz to commercialize the Dartmouth Time-Sharing System in 1963.
In 1971 Dr. Shell wrote "Optimizing the Polyphase Sort" in the Communications of the ACM, and in 1972 he joined with Mr. Ralph Mosher, a close friend and colleague, to start a business called Robotics Inc. where he was the General Manager and chief software engineer. Four years later, in 1976, they sold the company and Dr. Shell returned to General Electric Information Services Corporation. In 1984 he retired and moved to North Carolina where he lives today.
中文翻出来了。(真累）
1924年，唐纳德.希尔出生在美国密歇根州克罗斯韦附近的一个农场。由于天资聪颖，6岁生日时他开始在当地的学校上学。他学习进步很快，考上密歇根大学并于3年后获得该校的理科学士学位。
   获得理科学士学位后，希尔成为军方的一名工程师，被调往菲律宾修理损坏的设备，当时正处于第二次世界大战时期。战后他回到美国，取了爱丽丝。Mc克劳为妻。他回到密歇根技术工程大学任数学教师。后来，他去过辛辛那提州、俄亥俄州，为通用电气公司工作。其间，他发明了一种收敛算法，写了一个程序为喷气式动力引擎的运转作计算。  他也去过辛辛那提大学就读，1951年他获得数学方面的理科硕士。8年后，即1959年，他成为数学博士生。同年7月，他发表了“希尔排序算法”和“The share 709 System: A Cooprative Effort”。而之前一年，。。。
待续。。。参考资料：www
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息！
大家都在看
推荐信息