iOS 快速排序练习

作者: 万年老参 | 来源:发表于2020-02-26 17:50 被阅读0次

iOS 中的冒泡、选择、快速、插入排序算法
iOS标准库中常用数据结构和算法之排序
算法
iOS - 快速排序
iOS快速排序
iOS 快速排序
iOS 快速排序
ios 快速排序
iOS 快速排序
数组的排序

简单写一个快速排序，

-(void)fastLineAry:(NSMutableArray *)ary from:(int)from to:(int)to
{
    int end = to;
    if (to - from >0) {
        int mid = (from +to)/2;
        for (int n = from; n<=end; n++) {
            if ([ary[n] intValue] >[ary[mid] intValue] && n<mid) {
                NSString *str = ary[n];
                [ary removeObjectAtIndex:n];
              //[ary removeObject: str];
                [ary insertObject:str atIndex:to];
                n = n -1;
                end = end -1;
                mid = mid -1;
            }else if([ary[n] intValue]<[ary[mid] intValue] && n>mid){
                NSString *str = ary[n];
                [ary removeObjectAtIndex:n];
              //[ary removeObject: str];
                [ary insertObject:str atIndex:from];
                mid = mid +1;
            }
        }
        NSString *logStr =  [ary componentsJoinedByString:@","];
        NSLog(@"完成一轮比较:\n%@",logStr);
        if(mid - from > 1){
            [self fastLineAry:ary from:from to:mid-1];
        }
        if (to - mid >1) {
            [self fastLineAry:ary from:mid+1 to:to];
        }
    }
}

-(void)paixuAry:(NSMutableArray *)ary
{
    if (ary.count>1) {
        [self fastLineAry:ary from:0 to:(int)ary.count -1];
    }
    NSLog(@"排序完成");
}

NSMutableArray *ary = [NSMutableArray arrayWithArray:@[@"4",@"19",@"15",@"1",@"2",@"0",@"7",@"15",@"17",@"16",@"10",@"18",@"3",@"5",@"14",@"6"]];
[self paixuAry:ary];

打印结果：

2020-02-27 17:23:08.029797+0800  完成一轮比较:
6,14,5,3,10,4,15,1,2,0,7,15,17,16,18,19
2020-02-27 17:23:08.030298+0800  完成一轮比较:
0,2,1,3,4,15,7,6,14,5,10,15,17,16,18,19
2020-02-27 17:23:08.030608+0800  完成一轮比较:
1,0,2,3,4,15,7,6,14,5,10,15,17,16,18,19
2020-02-27 17:23:08.030887+0800  完成一轮比较:
0,1,2,3,4,15,7,6,14,5,10,15,17,16,18,19
2020-02-27 17:23:08.031192+0800  完成一轮比较:
0,1,2,3,4,5,6,14,10,15,7,15,17,16,18,19
2020-02-27 17:23:08.031591+0800  完成一轮比较:
0,1,2,3,4,5,6,7,10,15,14,15,17,16,18,19
2020-02-27 17:23:08.032156+0800  完成一轮比较:
0,1,2,3,4,5,6,7,10,14,15,15,17,16,18,19
2020-02-27 17:23:08.032940+0800  完成一轮比较:
0,1,2,3,4,5,6,7,10,14,15,15,16,18,19,17
2020-02-27 17:23:08.033656+0800  完成一轮比较:
0,1,2,3,4,5,6,7,10,14,15,15,16,17,18,19
2020-02-27 17:23:08.034149+0800  完成一轮比较:
0,1,2,3,4,5,6,7,10,14,15,15,16,17,18,19

第一遍写的代码就出了问题（第一遍写的是注释掉的那两行代码），基本功还是不够，
由于NSArray和NSMutableArray内只能存放NSObject及其子类对象，就存了一堆NSString
测试数组中有两个一样的元素@"15"，ary[m]和ary[n]都为@"15"时，这两个指针指向的是一同一个常量，
所以removeObject会同时移除两个对象，导致后续计算下标和数组长度错误。
有时间还是要去复习一下基础知识