试图了解一个shell排序

-2

我想了解一个我在网上找到的shell排序。这是代码：试图了解一个shell排序

for(increment = size/2;increment > 0; increment /= 2) 
{ 
    for(i = increment; i<size; i++) 
    { 
     temp = array[i]; 
     for(j = i; j >= increment ;j-=increment) 
     { 
      //perform the insertion sort for this section 
      if(temp < array[j-increment]) 
      { 
       array[j] = array[j-increment]; 
      } 
      else 
      { 
       break; 
      } 
     } 
     array[j] = temp; 
    } 
}

我明白，第一个循环不断将数组中元素的个数由2直到它到达1。但我真的不理解的代码的其余部分。

来源

2014-12-03 Jack

把它放在调试器中，逐步执行代码，并使用watch观察各个变量的值，看它是如何工作的:-) – 2014-12-03 04:25:05

并使用一个非常小的文件5行？）与1个重复作为您的测试数据。 – shellter 2014-12-03 04:26:08

首先，请阅读insertion sort。

最内层的循环执行插入排序的一部分，将元素插入（可能）排序的子数组中“到起点的左边”，但只考虑元素的一个倍数interval。第二个循环（for(i=...）执行插入排序的另一半，前进通过数组;当这个循环结束时，整个数组是排序的，但仅限于没有按照interval的倍数分隔的顺序。也就是说，没有i和k这样array [i]> array [i + k * interval]。

最外层循环遍历越来越小的间隔，直到它对整个数组进行“完整”插入排序。

我想大间隔开始的想法是通过允许非常大或非常小的元素“跳过”数组的大部分而不是爬过每个位置来加速整个排序;这个工作如何不会立即明显...

来源

2014-12-03 05:05:51 Beta

试图了解一个shell排序

回答

相关问题