A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 束玉杰 中级黑马   /  2020-1-16 15:03  /  1513 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

希尔排序:将无序数组分割成若干子序列,子序列不是逐段分割的,而是相隔特定增量的子序列,对各个子序列进行插入排序,然后再选择一个更小的增量,再将之前排序后的数组按这个增量分割成多个子序列,...,不断选择更小增量,直到增量为1时,再对序列进行一次插入排序,使序列最终成为有序序列,排序完成。
以下实例展示希尔排序的过程:
这里的首选增量为n/2,每次增量为原先的1/2,直到增量为1
30 80 49 70 65 20 44 33 56 96
第一趟:增量为5
30------------------20
     80------------------44
           49------------------33
                70-------------------56
                      65-------------------96
对每个子序列进行插入排序后序列为:
20 44 33 56 65 30 80 49 70 96
第二趟:增量为2
20-----33-----65-----80-----70
     44-----56-----30-----49-----96
对每个子序列进行插入排序后序列为:
20 30 33 44 65 49 70 56 80 96
第三趟:增量为1
直接对序列进行插入排序:
20 30 33 44 49 56 65 70 80 96
[JavaScript] 纯文本查看 复制代码
function ShellSort(arr){
		var len=arr.length;
		var gap,i;
		for(gap=Math.floor(len/2);gap>0;gap=Math.floor(gap/2)){
			for(i=gap;i<len;i++){
				var temp=arr[i];
				var j=i-gap;
				while(j>=0 && arr[j]>temp){
					arr[j+gap]=arr[j];
					j=j-gap;
				}
				if(j!=i-gap){
					arr[j+gap]=temp;
				}
			}
			
		}
	}
	var arr=[30,80,49,70,65,20,44,33,56,96];
	ShellSort(arr);
	document.write(arr);



原文链接:https://blog.csdn.net/fendou_dexiaoniao/article/details/46591915

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马