iOS 快速排序

作者: 丶天空蓝丶 | 来源:发表于2020-07-17 13:28 被阅读0次

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

首先我们看下为啥要使用快速排序，
如：现在我们有一个数组，需要对里面的数据进行排序，使用最原始的双层for循环排序

    _dataInt = 0;
     NSLog(@"begin");
    for (NSInteger i = 0; i < 10000; i ++) {
        NSInteger num = arc4random() % 10000;
        [_sortArray addObject:[NSString stringWithFormat:@"%ld",num]];
    }
    for (NSInteger i = 0; i < _sortArray.count; i ++) {
        for (NSInteger j = i + 1; j < _sortArray.count; j ++) {
            if ([_sortArray[i] integerValue] > [_sortArray[j] integerValue]) {
                [_sortArray exchangeObjectAtIndex:i withObjectAtIndex:j];
            }
            _dataInt ++;
        }
    }
    NSLog(@"%ld",_dataInt);

输出结果：
2020-07-17 11:31:46.737619+0800 TestOC[2596:130719] begin
2020-07-17 11:32:04.346488+0800 TestOC[2596:130719] 49995000

测试发现，在进行有一万条数据的数组排序情况下：

整个排序耗时达到了快20秒，执行了将近5千万次
如果数据变成10万条，这个耗时会变成100倍，
显然这种方法进行排序是不合理的，因为现实中万级别的数据还是存在的
造成这种原因是因为这种排序时间复杂度是平方阶O(n^2)，不适合处理过大的数据

现在我们使用下快速排序

    快速排序（Quick Sort）是实际开发中经常选用的一种排序方式。其排序原理：取数组中的首个元素（为了避免左右子数组不平衡的情况，一般将固定取数组首个元素改为随机取数组中的某个值为轴点元素，一定程度规避了最差时间复杂度的出现）为轴点数据，小于轴点的放在轴点前边大于的放在轴点后边，分成的左右子数组然后重复此操作的过程。

  现在用快速排序对数组进行排序：

 NSLog(@"begin");
    for (NSInteger i = 0; i < 100000; i ++) {
        NSInteger num = arc4random() % 10000;
        [_sortArray addObject:[NSString stringWithFormat:@"%ld",num]];
    }

    [self sortArrayBegain:0 end:_sortArray.count];
    
    NSLog(@"%ld",_dataInt);

- (void)sortArrayBegain:(NSInteger)begain end:(NSInteger)end {
    if (end - begain < 2) {
        return;
    }
//    获取排序后轴点数据的下标
    NSInteger mid = [self sortArrayWithBegain:begain end:end];
//    将轴点前数据当一个数组，重新排序
    [self sortArrayBegain:begain end:mid];
//    将轴点后数据当一个数组，重新排序
    [self sortArrayBegain:mid + 1 end:end];
}

// 返回轴点下标
- (NSInteger)sortArrayWithBegain:(NSInteger)begain end:(NSInteger)end {
    end--;
//    此处为了规避左右子数组不平衡的情况，将固定取数组第一个元素改为随机取数组中的某个值为轴点元素，一定程度规避了最差时间复杂度的出现
    NSInteger randomIndex = begain + arc4random() % (end - begain);
//    轴点数据
    id pivot = self.sortArray[randomIndex];
//    将轴点数据和第一个数据交换位置
    self.sortArray[randomIndex] = self.sortArray[begain];
    self.sortArray[begain] = pivot;
    
    while (begain < end) {
        while (begain < end) {
//            从后向前查
            _dataInt ++;
            if ([pivot integerValue] < [self.sortArray[end] integerValue]) {
                end--;
            } else {
//                如果比轴点数据小，将当前数据复制一份放在前面
                self.sortArray[begain] = self.sortArray[end];
                begain++;
                break;
            }
        }
        while (begain < end) {
            _dataInt ++;
//            从前往后查
            if ([self.sortArray[begain] integerValue] < [pivot integerValue]) {
                begain++;
            } else {
//                如果比轴点数据大，将当前数据复制一个放后面（因为上面将该位置的数据复制一份放在前面了，因此这个位置的数据是重复的）
                self.sortArray[end--] = self.sortArray[begain];
                break;
            }
        }
    }
//    这个下标前面的数据此时已经全部比轴点数据小了，后面的数据全部比轴点数据大，而且改数据以及被复制到别的地方了，而最开始轴点数据位置被别的数据使用，所以此时将这个点赋值成轴点数据
    self.sortArray[begain] = pivot;
    return begain;
}