0

我正在研究 Objective-C 中合并排序的实现（下面的代码）我很难理解为什么我的递归调用是一个无限循环，当我不将变量 ' middle' 加一时。

所以 [self sort:array fromLow:middle+1 toHigh:high]; 工作正常

但是[self sort:array fromLow:middle toHigh:high];把我的程序变成了一个无限循环。谁能解释我为什么会这样？在这两种情况下，if 语句

 if(high<=low)
    {
        return;
    }

已到达并执行，所以我认为我的程序将继续执行第三条语句（mergeLow：andHigh：andMiddle：inArray：andHelperArray :)，但事实并非如此。

排序方法： 

-(void)sort:(NSMutableArray *)array fromLow:(unsigned long)low toHigh:(unsigned long) high{


    if(high<=low) //recursive condition fullfilled
    {
        return;
    }
    unsigned long middle = low + (high - low)/2; //calculating middle element

    [self sort:array fromLow:low toHigh:middle]; //(1)sort left

    [self sort:array fromLow:middle+1 toHigh:high];//(2)sort right

    [self mergeLow:low andHigh:high andMiddle:middle inArray:array andHelperArray:[array mutableCopy]];//(3) merge left and right 

}

调试 我试图调试它。为此，我注释掉了对 merge 方法的调用 (3)，并添加了 nslog 语句记录高变量和低变量的值。

 MergeSort *is = [MergeSort new];
 NSArray * a1 = @[@10,@9,@22,@5];
 [is sort:a1.mutableCopy fromLow:0 toHigh:a1.count];

更新排序方法

-(void)sort:(NSMutableArray *)array fromLow:(unsigned long)low toHigh:(unsigned long) high{
    //recursive condition fullfilled

    NSLog(@"High: %lu Low %lu ",high, low);
    if(high<=low)
    {

        return;
    }
    unsigned long middle = low + (high - low)/2;

    [self sort:array fromLow:low toHigh:middle];

    [self sort:array fromLow:middle + 1 toHigh:high];

  // [self mergeLow:low andHigh:high andMiddle:middle inArray:array andHelperArray:[array mutableCopy]];

}

调试输出：middle+1

2013-10-28 11:37:21.484 Algorithms[52598:303] High: 4 Low 0 
2013-10-28 11:37:21.486 Algorithms[52598:303] High: 2 Low 0 
2013-10-28 11:37:21.486 Algorithms[52598:303] High: 1 Low 0 
2013-10-28 11:37:21.487 Algorithms[52598:303] High: 0 Low 0 
2013-10-28 11:37:21.487 Algorithms[52598:303] High: 1 Low 1 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 2 Low 2 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 4 Low 3 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 3 Low 3 
2013-10-28 11:37:21.489 Algorithms[52598:303] High: 4 Low 4

现在以同样的方法，我在[self sort:array fromLow:middle toHigh:high];不增加middle变量的情况下执行并获得以下输出：

调试输出：中

2013-10-28 11:45:55.689 Algorithms[52674:303] High: 4 Low 0 
2013-10-28 11:45:55.691 Algorithms[52674:303] High: 2 Low 0 
2013-10-28 11:45:55.691 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.692 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.692 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.695 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.695 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.697 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.697 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.698 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.698 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.701 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.701 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 1 Low 0
4

1 回答 1

3

您在两个调用中都包含中间元素（“左”和“右”）。

如果您只有 2 个元素，即 0 和 1，则中间元素为 0.5，即 0 为 int，您将“左”定义为 [0]，将“右”定义为 [0,1] ，所以“正确”最终成为你一开始所拥有的。

这就是为什么如果您将“正确”定义为从中间 + 1 开始，您就不会明白这一点。因为“左”会上升到中间，“右”会在之后开始。他们不会有任何共同点。

编辑（更多信息）：

使用递归算法时您应该始终牢记的一个概念是，只有在每次调用递归函数时都以某种方式将问题简化为比以前更简单的实例时，才能保证终止。

通常所做的是定义某种可以与递归函数的每次调用相关的度量，然后证明每次调用都会减少这种度量。如果您知道在终止条件下该度量应该具有一定的值，那么您现在可以确定问题最终会归结为终止条件并结束。

在这种情况下，您可以用作度量的将是您订购的数组的大小。您必须保证对递归函数的每次调用都将采用比调用时更小的数组。当数组的右侧部分最终以与原始大小相同的大小被调用时，您失败了。

于 2013-10-28T17:09:56.743 回答