在 Objective C 中合并排序

Question

我正在尝试在 objective -C 中实现归并排序。

这是在以下 link 中提出的类似问题，没有找到答案，因此创建了一个新问题。

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: 进行递归调用以对两半进行排序 - 这是您错过的简单步骤。

我是在学习练习中猜到的，所以没有代码，但你已经差不多了（修复它，它确实有效）。

顺便说一句，一旦你修复了它，你可能想考虑为什么你不需要为拆分部分创建新数组（但为合并创建一个新数组要容易得多）。

HTH

在 Objective C 中合并排序

Merge Sorting in Objective C

mergesort

objective-c