【Mac OS开发】使用gcd快速排序数组,使用gcd多线程查找数组中的最大值

此示例的功能:使用gcd排序一个有4万数字的数组,数组中的数字都是随机生成的

生成数组代码如下

    _numsMutableArray = [[NSMutableArray alloc] init];
    
    for (int i = 0; i < 40000; i++) {
        NSNumber *temp = [NSNumber numberWithInt:arc4random_uniform(1000000)];
        [_numsMutableArray addObject:temp];
    }

生成的数字范围在0~一百万,再都添加到数组中。

非常简单粗暴地分4个线程,排序一个有这么多数字的数组,思路为,先多线程排序数组的不同部分,然后再合并,合并这里我就是再快排一次……因为我想不出什么好的合并方法。其实用了线程速度也没有什么提升……罢了,先练习怎么用objective-c的线程。

dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
//创建一个线程队列
//下面这句就开辟了子线程
dispatch_async(queue, ^{
    //调用类方法quickSort快速排序
    [[self class] quickSort:self->_numsMutableArray low:0 high:10000];
});

用同样的方法开其他三个子线程。

dispatch_async(queue, ^{
    //排序第1万位到第2万位之间的数组
    [[self class] quickSort:self->_numsMutableArray low:10001 high:20000];
});
dispatch_async(queue, ^{
    //排序第2万位到第3万位之间的数组
    [[self class] quickSort:self->_numsMutableArray low:20001 high:30000];
});
dispatch_async(queue, ^{
    //排序第3万位到第4万位之间的数组
    [[self class] quickSort:self->_numsMutableArray low:30001 high:39999];
});

这样就可以让一个数组的四个部分有序,有序之后把这个四个部分再排序。

[[self class] quickSort:_numsMutableArray low:0 high:39999];

这样就完成了一个多线程练习。gcd属于是浅入门了。

那么现在可以观察一下,这些线程到底是不是并行。

//MARK: gcd
    dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0);
    
    dispatch_async(queue, ^{
        //排序
        NSLog(@"10000");
        [[self class] quickSort:self->_numsMutableArray low:0 high:10000];
        NSLog(@"10001");
    });
    dispatch_async(queue, ^{
        //排序
        NSLog(@"20000");
        [[self class] quickSort:self->_numsMutableArray low:10001 high:20000];
        NSLog(@"20001");
    });
    dispatch_async(queue, ^{
        //排序
        NSLog(@"30000");
        [[self class] quickSort:self->_numsMutableArray low:20001 high:30000];
        NSLog(@"30001");
    });
    dispatch_async(queue, ^{
        //排序
        //这些log都在子线程中,40000代表进入线程,40001代表执行完毕。
        NSLog(@"40000");
        [[self class] quickSort:self->_numsMutableArray low:30001 high:39999];
        NSLog(@"40001");
    });
//这个log在主线程中
    NSLog(@"jfkdslajflkdsj");

控制台输出为

2021-05-13 09:33:10.221206+0800 NSOperationPractice[6073:474997] jfkdslajflkdsj
2021-05-13 09:33:10.221214+0800 NSOperationPractice[6073:475037] 10000
2021-05-13 09:33:10.221219+0800 NSOperationPractice[6073:475034] 20000
2021-05-13 09:33:10.221229+0800 NSOperationPractice[6073:475033] 30000
2021-05-13 09:33:10.221250+0800 NSOperationPractice[6073:475036] 40000
2021-05-13 09:33:10.231717+0800 NSOperationPractice[6073:475036] 40001
2021-05-13 09:33:10.232100+0800 NSOperationPractice[6073:475037] 10001
2021-05-13 09:33:10.232303+0800 NSOperationPractice[6073:475033] 30001
2021-05-13 09:33:10.232469+0800 NSOperationPractice[6073:475034] 20001

多运行几次就会发现,这些线程开始和结束的时间并不是按1234顺序的,他们是并行执行的。而且,在主线程中的log尽管写在最后,也是最先输出的。如果我们要得到最大值最小值,思路应该是,在四个线程中得到最大值,然后比较这四个值,那么这四个值怎么取得呢?我们不能在这四个线程后面直接比较,因为上面说到,主线程是先执行的。所以要用到线程组的知识,我们创建四个线程,让代码等待这四个线程执行完毕之后,再来比较。

参考链接:https://www.jianshu.com/p/5fc974a951fd

之前写四个线程的时候,应该也有人觉得,一个一个的写太麻烦,现在就用for循环来写。

//创建一个线程队列
dispatch_queue_t concurrentQueue = dispatch_queue_create("com.group", DISPATCH_QUEUE_PRIORITY_DEFAULT);
    //用数组存4个最大值
    NSMutableArray *tempArray = [[NSMutableArray alloc] init];
    //创建一个线程组
    dispatch_group_t group = dispatch_group_create();
    for(int i = 0; i < 4; i++){
        //在循环中创建4个线程
        dispatch_group_async(group, concurrentQueue, ^{
            //numsMutableArray是一个我自己写的类方法,里面找最大值,很简单,代码附在最后。
            int t = [[self class] findTheMaxNumber:self->_numsMutableArray low:i * 10000 high:i * 10000 + 9999];
            [tempArray addObject:@(t)];
//            NSNumber *testNumb = [NSNumber numberWithInt:t];上一句的@(t)就是这句话的简写,创建了一个NSNumber对象。
        });
    }

    dispatch_group_notify(group, concurrentQueue, ^{
        //子线程执行完毕可以进入这个代码块。
        //NSLog(@"end");
        //NSLog(@"%@",tempArray);
        int finallyMaxNumber = -1;
        for(int i = 0; i < 4; i++){
            if(finallyMaxNumber < [[tempArray objectAtIndex:i] intValue]){
                finallyMaxNumber = [[tempArray objectAtIndex:i] intValue];
            }
        }
        NSLog(@"the max number %d",finallyMaxNumber);
    });

这样就实现了找最大值。

下面附上两个类方法的代码。

在AppDelegate.h中

+ (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high;
+ (int)findTheMaxNumber:(NSMutableArray *)array low:(int)low high:(int)high;

在AppDelegate.m中

+ (int)findTheMaxNumber:(NSMutableArray *)array low:(int)low high:(int)high{
    int maxNumber = -10;
    for(int i = low; i < high; i++){
        if(maxNumber < [array[i] intValue]){
            maxNumber = [array[i] intValue];
        }
    }
    return maxNumber;
}
//快速排序类方法
+ (void)quickSort:(NSMutableArray *)array low:(int)low high:(int)high{
    if(array == nil || array.count == 0){
        return;
    }
    if(low >= high){
        return;
    }
    
    int mid = low + (high - low)/2;
    NSNumber *prmt = array[mid];
    int i = low;
    int j = high;
    
    while(i <= j){
        while([array[i] intValue] < [prmt intValue]){
            i++;
        }
        while([array[j] intValue] > [prmt intValue]){
            j--;
        }
        if(i <= j){
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
            i++;
            j--;
        }
    }
    if(low < j){
        [[self class]quickSort:array low:low high:j];
    }
    if(high > i){
        [[self class]quickSort:array low:i high:high];
    }
}

由于刚开始学Objective-C不能保证全部内容准确无误,如有错误欢迎留言。

Fin.

上一篇:react全局变量使用react-redux


下一篇:优化总结:有哪些APP启动提速方法?