目标C中的合并排序

Question

我试图在目标-C中实现合并排序.

这是一个类似的问题,在以下链接中询问,没有找到答案,因此创建了一个新问题.

在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;
}

希望我帮助过你..干杯..