合併排序Objective-C

我想弄清楚這個合併排序實現有什麼問題。當我將左右數組的剩餘部分連接在一起時，我縮小了範圍。在遞歸的第三個循環中，出現了一些錯誤。合併排序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。感謝大家。

來源

2013-08-17 Michael Leveton

你是什麼意思「出現問題」？什麼是錯誤的行爲？ – Fred

對於給定數組，輸出不是升序。 –

您不能使用<（小於）運算符來比較兩個對象。使用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這樣的事情，情況確實如此。如果這些是自定義對象，則需要實現等效方法。

來源

2013-08-17 03:32:27 rmaddy

檢查'result！= NSOrderedDescending'而不是使其穩定。 –

肯定的問題是比較：

更換：

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

爲：

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

也會起作用。

來源

2014-04-22 23:13:41

合併排序Objective-C

回答

相關問題