在Objective-C中合并排序

Question

我试图弄清楚这个合并排序实现有什么问题.当我连接剩下的左右数组时,我已经缩小了范围.在递归的第三个循环中,出现了问题.

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

Answer 1

您不能使用<(小于)运算符来比较两个对象.使用compare:方法:

更换:

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

有:

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

正如"抢劫"指出的那样,使用它会更好:

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

BTW - 使用<两个对象会导致问题,因为您正在比较两个对象的指针地址.因此,您最终会根据对象在内存中的位置而不是按值来对对象进行排序.

当然,使用该compare:方法假设数组中的对象实际上实现了该compare:方法.这对于像真正的NSString,NSNumber和NSDate.如果这些是自定义对象,则需要实现等效方法.