谢尔排序(缩小增量排序)

核心思想:首先确定一个元素间隔数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),不稳定排序,不适合用于链表。

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。