c++ - 了解C++ Shell排序

Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。












想改善这个问题吗？更新问题，以便将其作为on-topic用于堆栈溢出。

6年前关闭。



Improve this question




嗨，我正在尝试学习shell排序。我了解拆分成段并使用插入方法进行排序的基本原理。

但是，我只理解我发现的这段代码示例。如果有人能给我一个清楚的解释，每个for循环的作用等等，那将是很棒的。

int const size = 5;
int i, j, increment, temp;
int array[size]={4,5,2,3,6},i1=0;
//split the array into segments unil we reach beginning of array
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;
    }
}

最佳答案

for(increment = size/2;increment > 0; increment /= 2)

此for循环初始化您要比较的数组中元素之间的间隙。因此，增量最初设置为2。

for(i = increment; i<size; i++)
{
    temp = array[i];

这就是说，从元素3开始并继续前进，直到到达元素5，我们将很快知道为什么。

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;

好的，我们从上面指定的元素(在本例中为第二个索引)开始，然后将其与位于其后的“间隙”长度的元素进行比较。因此，它将采用第三个元素，并将其与第一个元素进行比较。如果第3个元素的比第1个元素小的，请交换它们，否则请退出循环。然后，我们将索引的大小减小缺口(从2减小到0)，并在新索引至少与缺口的大小一样大时继续操作(这样就不会出现数组越界问题)。

现在，我们回到中间进行循环，并增加开始的元素位置；所以我们比较

第4个元素与第2个元素相对。停止

第3个元素排在第3个，然后第3个元素排在第1个。停止

比较完“间隙”长度内的所有元素后，我们将间隙长度更改为以前的一半，冲洗并重复直到其达到0。

通常，您不希望仅将间隙分成两半-有一些用于间隙长度推荐的预定义功能(通常是素数)。 See wikipedia了解更多信息。

关于c++ - 了解C++ Shell排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20620013/