首页 > 代码库 > 谢尔排序(缩小增量排序)
谢尔排序(缩小增量排序)
核心思想:首先确定一个元素间隔数gap,然后将参加排序的序列按此间隔数从第1个元素开始依次分成若干个子序列,即分别将所有位置间隔为gap的元素视为一个子序列,在各个子序列中采用某种排序方法进行排序;然后减小间隔数,并重新将整个序列按新的间隔数分成若干个子序列,再分别对各个子序列进行排序,如此下去,直到间隔数gap=1;
var arr = [38,49,65,97,76,13,27,49];
shellSort(arr);
console.log(arr);
var shellSort = function(arr){ var i, j,temp; var n = arr.length; var gap = n; while(gap>1){ gap = gap/2; do{ flag = 0; for(i=0;i<n-gap;i++){ j = i+gap; if(arr[i]>arr[j]){ temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; flag = 1; } } }while(flag!=0); }}
算法分析:谢尔排序的时间复杂度稍大于O(nlog2n)接近于O(n1.23),不稳定排序,不适合用于链表。
谢尔排序(缩小增量排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。