1

我试图弄清楚这个合并排序实现有什么问题。我已经把它缩小到当我连接左右数组的剩余部分时。在递归的第三个循环中，出现了问题。

-(NSArray *)mergeSort:(NSArray *)unsortedArray
{
  //unsortedArray is 4,2,6,5,3,9
  if ([unsortedArray count] < 2)
 {
    return unsortedArray;
 }
   int middle = ([unsortedArray count]/2);
   NSRange left = NSMakeRange(0, middle);
   NSRange right = NSMakeRange(middle, ([unsortedArray count] - middle));
   NSArray *rightArr = [unsortedArray subarrayWithRange:right];
   NSArray *leftArr = [unsortedArray subarrayWithRange:left];
   return [self merge:[self mergeSort:leftArr] andRight:[self mergeSort:rightArr]];
}

-(NSArray *)merge:(NSArray *)leftArr andRight:(NSArray *)rightArr
{
  NSMutableArray *result = [[NSMutableArray alloc]init];
  int right = 0;
  int left = 0;

  while (left < [leftArr count] && right < [rightArr count])
  {
    if ([leftArr objectAtIndex:left] < [rightArr objectAtIndex:right])
    {
        [result addObject:[leftArr objectAtIndex:left++]];
    }
    else
    {
        [result addObject:[rightArr objectAtIndex:right++]];
    }
 }
  NSRange leftRange = NSMakeRange(left, ([leftArr count] - left));
  NSRange rightRange = NSMakeRange(right, ([rightArr count] - right));
  NSArray *newRight = [rightArr subarrayWithRange:rightRange];
  NSArray *newLeft = [leftArr subarrayWithRange:leftRange];
  newLeft = [result arrayByAddingObjectsFromArray:newLeft];
  return [newLeft arrayByAddingObjectsFromArray:newRight];
}

顺便说一句，这不是家庭作业。我是一名自学成才的程序员，试图学习一点 CS。感谢大家。

4

2 回答 2

8

您不能使用<（小于）运算符来比较两个对象。使用compare:方法：

代替：

if ([leftArr objectAtIndex:left] < [rightArr objectAtIndex:right])

和：

NSComparsionResult result = [leftArr[left] compare:rightArr[right]];
if (result == NSOrderedAscending) // equivalent to <

正如“rob”指出的那样，最好使用：

if (result != NSOrderedDescending) // equivalent to <=

顺便说一句 - 使用<两个对象会导致问题，因为您正在比较两个对象的指针地址。因此，您最终会根据它们在内存中的位置而不是它们的值对对象进行排序。

当然，使用该compare:方法假定数组中的对象实际实现了该compare:方法。这适用于 , 和 之类NSString的NSNumber东西NSDate。如果这些是自定义对象，您需要实现等效方法。

于 2013-08-17T03:32:27.063 回答
1

问题当然是比较：

更换：

if ([leftArr objectAtIndex:left] < [rightArr objectAtIndex:right])

为了：

 if ([[leftArr objectAtIndex:left] intValue] < [[rightArr objectAtIndex:right] intValue])

也将工作。

于 2014-04-22T23:13:41.117 回答