在Objective-C中合并排序

迈克尔·莱夫顿

我正在尝试找出此合并排序实现的问题。我将其范围缩小到连接左数组和右数组的其余内容时。在递归的第三个循环中,出现了问题。

-(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。谢谢大家。

rmaddy

您不能使用<(小于)运算符来比较两个对象。使用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这是正确的如果这些是自定义对象,则需要实现等效的方法。NSNumberNSDate

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章