快速排序 排序大型数组时出错

Question

当我尝试对十万个整数的数组进行排序时，我收到一条错误消息（我已经测试了排序，它适用于五万个）：

警告：无法加载任何 Objective-C 类信息。这将大大降低可用类型信息的质量。

我也有迭代的比较方法，出现同样的错误

为什么会出现此错误消息？

是否可以对该列表进行排序，如果是，如何解决？

-(void) quickSort{
   return [self quickSort:0 pivot:[self.toSort count]-1 right: [self.toSort count]-1];
}
-(void) quickSort:(int) left pivot:(int) pivot right:(int) right {
    if(left < right){
        pivot = [self compareToPivot:[[self.toSort objectAtIndex:right] intValue] start:left finish:right position:left];
        [self quickSort:pivot+1 pivot:pivot right:right];
        [self quickSort:left pivot:pivot right:pivot-1];
    }
}
-(int) compareToPivot:(int) pivot start:(int)start finish:(int)finish position:(int)pos{
    if(pos == finish){
        [self switchNums:start second:finish];
        return start;
    }
     if([[self.toSort objectAtIndex:pos] intValue] <= pivot){
     [self switchNums:pos second:start];
     return [self compareToPivot:pivot start:start+1 finish:finish position:pos+1];
}
return [self compareToPivot:pivot start:start finish:finish position:pos+1];
}
-(void) switchNums:(int)first second:(int)second{
    id temp = [self.toSort objectAtIndex:second];
    [self.toSort replaceObjectAtIndex:second withObject:[self.toSort objectAtIndex:first]];
    [self.toSort replaceObjectAtIndex:first withObject:temp];
}

迭代比较，运行良好：

-(int) compareToPivot:(int) pivot start:(int)start finish:(int)finish position:(int)pos{
while(pos != finish){
    if([[self.toSort objectAtIndex:pos] intValue] <= pivot){
        [self switchNums:pos second:start];
        start+=1;
    }
        pos++;
}
[self switchNums:start second:finish];
return start;

}

Answer 1

虽然快速排序本身被认为是一种递归算法，但分区步骤（您的comparetoPivot方法）不适用于递归。 并且您对此方法的实现不仅是递归的，而且就堆栈空间而言，它也是 O（N）。 每次递归到compareToPivot中时，您只使用比以前少一个元素进行递归。 在大约 100K 元素声音下爆炸（耗尽堆栈）是可以预期的，因为默认堆栈约为 500KB。

我用你的问题作为练习我的 Obj-C 的借口，我有点生疏。 但这里是递归快速排序的实现，直接来自经典的算法（Cormen等人）一书，并适用于您的toSort数组。 我还没有全部测试出来，但你当然可以试一试。

-(int)partition: (NSMutableArray*)arr pivot:(int)pivot  right:(int)right
{
    int x = [[arr objectAtIndex: pivot] intValue];
    int i = pivot;
    int j = right;
    while (true)
    {
        while ([[arr objectAtIndex: j] intValue] > x)
        {
            j--;
        }
        while ([[arr objectAtIndex: i] intValue] < x)
        {
            i++;
        }
        if (i < j) {
            id objI = [arr objectAtIndex: i];
            id objJ = [arr objectAtIndex: j];
            [arr replaceObjectAtIndex:i withObject:objJ];
            [arr replaceObjectAtIndex:j withObject:objI];
            j--;
            i++;
        }
        else
        {
            return j;
        }
    }
}
-(void)quickSort
{
    int len = (int)[self.toSort count];
    [self quicksort:self.toSort left:0 right:(len-1)];
}
-(void)quicksort: (NSMutableArray*)arr left:(int)left  right:(int)right
{
    if (left< right)
    {
        int q = [self partition:arr pivot:left right:right];
        [self quicksort: arr left:left  right:q];
        [self quicksort: arr left:(q+1) right:right];
    }
}