Objective-C 中的合并排序 [英] Merge sort in Objective-C

问题描述

我正在尝试弄清楚这个合并排序实现有什么问题.我已经将范围缩小到连接左右数组剩余部分的时间.在递归的第三个循环中，出了点问题.

I'm trying to figure out what's wrong with this merge sort implementation. I've narrowed it down to when I concatenate what remains of the left and right arrays. In the third loop of the recursion, something goes wrong.

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

BTW, this is not homework. I'm a self-taught programmer trying to learn a little CS. Thanks everyone.

推荐答案

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

You can't use the < (less than) operator to compare two objects. Use the compare: method:

替换:

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

与:

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

正如rob"所指出的那样，使用会更好:

As "rob" points out, it would be even better to use:

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

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

BTW - using < with two objects is causing problems because you are comparing the pointer addresses of the two objects. So you end up sorting the objects based on their location in memory and not by their value.

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

And of course using the compare: method assumes the objects in the array actually implement the compare: method. This is true for things like NSString, NSNumber, and NSDate. If these are custom objects you need to implement an equivalent method.

这篇关于Objective-C 中的合并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！