锐客网

  1. 首页 > 睿知 > it技术 > >

Go语言希尔排序 希尔排序 java( 四 )

IT技术算法


希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序 。
1. 算法步骤
选择一个增量序列 t1 ， t2，……，tk ， 其中 titj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序 ， 根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列 ， 分别对各子表进行直接插入排序 。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度 。
2. 动图演示
代码实现JavaScript实例functionshellSort ( arr ){
varlen=arr. length,
temp ,
gap=1;
while ( gap0;gap=Math . floor( gap /3)){
for(vari=gap ;i=0arr [ j ]temp ;j -= gap ){
arr [ j + gap ]=arr [ j ];
}
arr [ j + gap ]=temp ;
}
}
returnarr ;
}
Python实例defshellSort ( arr ) :
importmath
gap =1
while( gap0 :
foriinrange( gap ,len( arr )) :
temp=arr [ i ]
j=i-gap
whilej=0andarr [ j ]temp:
arr [ j+gap ]= arr [ j ]
j- = gap
arr [ j+gap ]=temp
gap=math . floor( gap/ 3)
returnarr
Go实例funcshellSort ( arr[]int)[]int{
length:=len( arr )
gap:=1
forgaplength /3{
gap=gap *3+1
}
forgap0{
fori:=gap ;ilength ;i++{
temp:=arr [i]
j:=i-gap
forj=0arr [ j ]temp{
arr [ j + gap ]=arr [ j ]
j-=gap
}
arr [ j + gap ]=temp
}
gap=gap/3
}
returnarr
}
Java实例publicstaticvoidshellSort (int[]arr ){
intlength=arr. length;
inttemp ;
for(intstep=length/2;step=1;step/=2){
for(inti=step ;i=0arr [ j ]temp ){
arr [ j+step ]=arr [ j ];
j-=step ;
}
arr [ j+step ]=temp ;
}
}
}
PHP实例functionshellSort ($arr)
{
$len=count($arr);
$temp=0;
$gap=1;
while($gap0;$gap=floor($gap/3)){
for($i=$gap;$i=0$arr[$j]$temp;$j-=$gap){
$arr[$j+$gap]=$arr[$j];
}
$arr[$j+$gap]=$temp;
}
}
return$arr;
}
C实例voidshell_sort (intarr [],intlen ){
intgap ,i ,j ;
inttemp ;
for( gap=len1;gap0;gap=1)
for( i=gap ;i=0arr [ j ]temp ;j-=gap )
arr [ j+gap ]=arr [ j ];
arr [ j+gap ]=temp ;
}
}
C++实例template
voidshell_sort ( T array [] ,intlength ){
inth=1;
while( h=1){
for(inti=h ;i=harray [ j ]0){for (int i = gap; iarr.Length; i++){int tmp = arr[i];int j = i - gap;while (j = 0arr[j]tmp){arr[j + gap] = arr[j];j -= gap;}arr[j + gap] = tmp;}gap /= 3;}} 以上为希尔排序算法详细介绍，插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等排序算法各有优缺点，用一张图概括：
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序 。
线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数 。希尔排序
线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序 。
关于稳定性
稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序 。
不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序 。
名词解释：
n：数据规模
k："桶"的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
【Go语言希尔排序 希尔排序 java】关于Go语言希尔排序和希尔排序 java的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息 ， 记得收藏关注本站 。

推荐阅读


上一篇：怎么初始电脑密码，电脑初始密码忘了怎么办

下一篇：单机快乐小游戏，单机游戏快玩