合併目標C

Question

排序我試圖實現的目標-C歸併排序。

這是一個類似的問題在下面的鏈接要求，沒有發現它回答說，因此創建一個新的問題。

Merge sort in Objective-C

這是我已經試過了，

-(NSArray *)mergeSort:(NSArray *)unsortedArray { 

    if ([unsortedArray count] < 2) 
     return unsortedArray; 

    long mid = [unsortedArray count]/2; 
    NSRange left = NSMakeRange(0, mid); 
    NSRange right = NSMakeRange(mid, [unsortedArray count] - mid); 

    NSArray *rightArray = [unsortedArray subarrayWithRange:right]; 
    NSArray *leftArray = [unsortedArray subarrayWithRange:left]; 

    NSArray *resultArray = [self merge:leftArray andRight:rightArray]; 
    return resultArray; 
} 

-(NSArray *)merge:(NSArray *)leftArray andRight:(NSArray *)rightArray { 

    NSMutableArray *result = [NSMutableArray array]; 
    int right = 0; 
    int left = 0; 

    while (left < [leftArray count] && right < [rightArray count]) { 

     NSComparisonResult comparisonResult = [leftArray[left] compare:rightArray[right]]; 

     if (comparisonResult != NSOrderedDescending) { 
      [result addObject:[leftArray objectAtIndex:left++]]; 
     } else { 
      [result addObject:[rightArray objectAtIndex:right++]]; 
     } 

     /*if ([[leftArray objectAtIndex:left] intValue] < [[rightArray objectAtIndex:right] intValue]) { 
      [result addObject:[leftArray objectAtIndex:left++]]; 
      //left++; 
     } else { 
      [result addObject:[rightArray objectAtIndex:right++]]; 
      //right++; 
     }*/ 
    } 

    NSRange leftRange = NSMakeRange(left, [leftArray count] - left); 
    NSRange rightRange = NSMakeRange(right, [rightArray count] - right); 
    NSArray * newRight = [rightArray subarrayWithRange:rightRange]; 
    NSArray * newLeft = [leftArray subarrayWithRange:leftRange]; 
    newLeft = [result arrayByAddingObjectsFromArray:newLeft]; 

    return [newLeft arrayByAddingObjectsFromArray:newRight]; 
} 

請讓我知道如果任何人有合併排序任何其他方法。

Answer 1

我不明白爲什麼你們這些人想要的很長的路要走..即使有這樣做的已經簡單的方法...

我做了一個自己希望這將幫助你..

- (NSArray *)arrayMergeSort:(NSArray *)targetArray 
{ 
    if (targetArray.count < 2) 
     return targetArray; 

    long midIndex = targetArray.count/2; 

    NSArray *arrayLeft = [targetArray subarrayWithRange:NSMakeRange(0, midIndex)]; 

    NSArray *arrayRight= [targetArray subarrayWithRange:NSMakeRange(midIndex, targetArray.count - midIndex)]; 

    return [self arrayMerge: [self arrayMergeSort:arrayLeft] : [self arrayMergeSort:arrayRight]]; 
} 

對於安排合併：

- (NSArray *)arrayMerge:(NSArray *)arrayLeft :(NSArray *)arrayRight 
{ 
    NSMutableArray *resultArray = [[NSMutableArray alloc] init]; 

    int i = 0, j = 0; 

    while (i < arrayLeft.count && j < arrayRight.count) 
     [resultArray addObject:([arrayLeft[i] intValue] < [arrayRight[j] intValue]) ? arrayLeft[i++] : arrayRight[j++]]; 

    while (i < arrayLeft.count) 
     [resultArray addObject:arrayLeft[i++]]; 

    while (j < arrayRight.count) 
     [resultArray addObject:arrayRight[j++]]; 

    return resultArray; 
} 

，並用它喜歡：

//Sample array 
NSArray *activeArray = @[@101,@201,@301,@121,@11,@123,@21,@14,@32,@76,@89,@987,@65]; 

NSLog(@"arrayMergeSort %@",[self arrayMergeSort:activeArray]); 

輸出將是：

而且也是這個冒泡排序的，如果你需要這樣的：

- (NSArray *)arrayBubbleSort:(NSArray *)targetArray 
{ 
    NSMutableArray *resultArray = [targetArray mutableCopy]; 

    for (int k = 0; k < resultArray.count; k++) 
    { 
     for (int l = 0; l < resultArray.count; l++) 
     { 
      if ([resultArray[k] intValue] < [resultArray[l] intValue]) 
      { 
       [resultArray exchangeObjectAtIndex:k withObjectAtIndex:l]; 
      } 
     } 
    } 

    return resultArray; 
} 

希望我已經幫你..乾杯..

Answer 2

你」我犯了一個簡單的錯誤。合併排序工作我拆分數組，排序到兩個一半，然後合併結果。

你mergeSort:方法不分裂，兩半不排序，然後調用merge:合併兩個（可惜未排序）兩部分。

在致電merge:之前，您需要對mergeSort:進行遞歸調用來對兩半進行排序 - 這是您錯過的簡單步驟。

我在學習鍛鍊猜測這一點，所以沒有代碼，但你幾乎沒有（解決它和它的工作）。

BTW一旦你固定它，你可能要想想爲什麼你不需要爲分裂部創建新的陣列（但其更容易創建的合併一個新陣列）。

HTH