八大排序之快速排序

核心思想：分治

第一种：挖坑法
C++：

// 挖坑法
int QuickSort::partitionV1(std::vector<int> &arrNumbers, int startIndex, int endIndex) {
    
    int key = arrNumbers[startIndex];
    int i = startIndex;
    int j = endIndex;
    while ( i < j ) {
        
        while ( i < j && arrNumbers[j] >= key ) {
            
            --j;
        }
        
        if ( i < j ) {
            
            arrNumbers[i] = arrNumbers[j];
        }
        
        while ( i < j && arrNumbers[i] <= key ) {
            
            ++i;
        }
        
        if ( i < j ) {
            
            arrNumbers[j] = arrNumbers[i];
        }
    }
    arrNumbers[i] = key;
    
    return i;
}


void QuickSort::sortV1(std::vector<int>& arrNumbers, int startIndex, int endIndex) {
    
    if ( endIndex <= startIndex ) {
        
        return;
    }
    
    int index = partitionV1( arrNumbers, startIndex, endIndex );
    sortV1( arrNumbers, startIndex, index - 1 );
    sortV1( arrNumbers, index + 1, endIndex );
}


void QuickSort::sortV1(std::vector<int>& arrNumbers) {
    
    sortV1( arrNumbers, 0, arrNumbers.size() - 1 );
}

Objective-C：

// 挖坑法
+ (NSInteger)partitionV1:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
              startIndex:(NSInteger)startIndex
                endIndex:(NSInteger)endIndex {
    
    
    NSNumber *key = arrMNumbers[startIndex];
    NSInteger i = startIndex;
    NSInteger j = endIndex;
    while ( i < j ) {
        
        while ( i < j && arrMNumbers[j].integerValue >= key.integerValue ) {
            
            --j;
        }
        
        if ( i < j ) {
            
            arrMNumbers[i] = arrMNumbers[j];
        }
        
        while ( i < j && arrMNumbers[i].integerValue <= key.integerValue ) {
            
            ++i;
        }
        
        if ( i < j ) {
            
            arrMNumbers[j] = arrMNumbers[i];
        }
    }
    arrMNumbers[i] = key;
    
    return i;
}


+ (void)quickSortV1:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
         startIndex:(NSInteger)startIndex
           endIndex:(NSInteger)endIndex {
    
    if ( endIndex <= startIndex ) {
        
        return;
    }
    
    NSInteger index = [self partitionV1:arrMNumbers
                             startIndex:startIndex
                               endIndex:endIndex];
    [self quickSortV1:arrMNumbers
           startIndex:startIndex
             endIndex:index - 1];
    [self quickSortV1:arrMNumbers
           startIndex:index + 1
             endIndex:endIndex];
}


+ (nullable NSArray<NSNumber *> *)quickSortV1:(nonnull NSArray<NSNumber *> *)arrNumbers {
    
    NSMutableArray<NSNumber *> *arrMNumbers = [arrNumbers mutableCopy];
    [self quickSortV1:arrMNumbers
           startIndex:0
             endIndex:arrMNumbers.count - 1];
    
    return [arrMNumbers copy];
}

第二种：指针交换法
C++：

// 指针交换法
int QuickSort::partitionV2(std::vector<int> &arrNumbers, int startIndex, int endIndex) {
    
    int i = startIndex;
    int j = endIndex;
    while ( i != j ) {
        
        while ( i < j && arrNumbers[j] >= arrNumbers[startIndex] ) {
            
            --j;
        }
        
        while ( i < j && arrNumbers[i] <= arrNumbers[startIndex] ) {
            
            ++i;
        }
        
        if ( i < j ) {
            
            // swap
            arrNumbers[i] = arrNumbers[i] ^ arrNumbers[j];
            arrNumbers[j] = arrNumbers[i] ^ arrNumbers[j];
            arrNumbers[i] = arrNumbers[i] ^ arrNumbers[j];
        }
    }
    if ( i != startIndex) {
        
        arrNumbers[i] = arrNumbers[i] ^ arrNumbers[startIndex];
        arrNumbers[startIndex] = arrNumbers[i] ^ arrNumbers[startIndex];
        arrNumbers[i] = arrNumbers[i] ^ arrNumbers[startIndex];
    }
    
    return i;
}


void QuickSort::sortV2(std::vector<int>& arrNumbers, int startIndex, int endIndex) {
    
    if ( endIndex <= startIndex ) {
        
        return;
    }
    
    int index = partitionV2( arrNumbers, startIndex, endIndex );
    sortV2( arrNumbers, startIndex, index - 1 );
    sortV2( arrNumbers, index + 1, endIndex );
}


void QuickSort::sortV2(std::vector<int>& arrNumbers) {
    
    sortV2(arrNumbers, 0, arrNumbers.size() - 1);
}

Objective-C：

// 指针交换法
+ (NSInteger)partitionV2:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
              startIndex:(NSInteger)startIndex
                endIndex:(NSInteger)endIndex {
    
    NSInteger i = startIndex;
    NSInteger j = endIndex;
    while ( i != j ) {
        
        while ( i < j && arrMNumbers[j].integerValue >= arrMNumbers[startIndex].integerValue ) {
            
            --j;
        }
        
        while ( i < j && arrMNumbers[i].integerValue <= arrMNumbers[startIndex].integerValue ) {
            
            ++i;
        }
        
        if ( i < j ) {
            
            NSNumber *temp = arrMNumbers[i];
            arrMNumbers[i] = arrMNumbers[j];
            arrMNumbers[j] = temp;
        }
    }
    NSNumber *temp = arrMNumbers[i];
    arrMNumbers[i] = arrMNumbers[startIndex];
    arrMNumbers[startIndex] = temp;
    
    return i;
}


+ (void)quickSortV2:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
         startIndex:(NSInteger)startIndex
           endIndex:(NSInteger)endIndex {
    
    if ( endIndex <= startIndex ) {
        
        return;
    }
    
    NSInteger index = [self partitionV2:arrMNumbers
                             startIndex:startIndex
                               endIndex:endIndex];
    [self quickSortV2:arrMNumbers
           startIndex:startIndex
             endIndex:index - 1];
    [self quickSortV2:arrMNumbers
           startIndex:index + 1
             endIndex:endIndex];
}


+ (nullable NSArray<NSNumber *> *)quickSortV2:(nonnull NSArray<NSNumber *> *)arrNumbers {
    
    NSMutableArray<NSNumber *> *arrMNumbers = [arrNumbers mutableCopy];
    [self quickSortV2:arrMNumbers
           startIndex:0
             endIndex:arrMNumbers.count - 1];
    
    return [arrMNumbers copy];
}

第三种：前后指针法
C++：

// 前后指针法
int QuickSort::partitionV3(std::vector<int> &arrNumbers, int startIndex, int endIndex) {
    
    int cur = startIndex;
    int pre = cur - 1;
    while ( cur <= endIndex ) {
        
        while ( cur <= endIndex && arrNumbers[cur] <= arrNumbers[startIndex] ) {
            
            ++cur;
            pre = cur - 1;
        }
        
        while ( cur <= endIndex && arrNumbers[cur] >= arrNumbers[startIndex] ) {
            
            ++cur;
        }
        
        if ( cur <= endIndex && pre + 1 < cur ) {
            
            std::swap( arrNumbers[pre + 1], arrNumbers[cur] );
            pre = pre + 1;
            cur = pre + 1;
        }
    }
    if ( pre <= endIndex && pre != startIndex ) {
        
        std::swap( arrNumbers[pre], arrNumbers[startIndex] );
    }
    
    return pre;
}


void QuickSort::sortV3(std::vector<int>& arrNumbers, int startIndex, int endIndex) {
    
    if ( endIndex <= startIndex ) {
        
        return;
    }
    
    int index = partitionV3( arrNumbers, startIndex, endIndex );
    sortV3( arrNumbers, startIndex, index - 1 );
    sortV3( arrNumbers, index + 1, endIndex );
}


void QuickSort::sortV3(std::vector<int>& arrNumbers) {
    
    sortV3(arrNumbers, 0, arrNumbers.size() - 1);
}

Objective-C：

// 前后指针法
+ (NSInteger)partitionV3:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
              startIndex:(NSInteger)startIndex
                endIndex:(NSInteger)endIndex {
    
    NSInteger cur = startIndex;
    NSInteger pre = cur - 1;
    while ( cur <= endIndex && pre <= endIndex ) {

        while ( cur <= endIndex && arrMNumbers[cur].integerValue <= arrMNumbers[startIndex].integerValue ) {

            ++cur;
            pre = cur - 1;
        }

        while ( cur <= endIndex && arrMNumbers[cur].integerValue >= arrMNumbers[startIndex].integerValue ) {

            ++cur;
        }

        if ( cur <= endIndex && pre + 1 <= endIndex && pre + 1 < cur ) {

            NSNumber *temp = arrMNumbers[cur];
            arrMNumbers[cur] = arrMNumbers[pre + 1];
            arrMNumbers[pre + 1] = temp;

            pre = pre + 1;
            cur = pre + 1;
        }
    }
    if ( pre != startIndex && pre <= endIndex ) {

        NSNumber *temp = arrMNumbers[pre];
        arrMNumbers[pre] = arrMNumbers[startIndex];
        arrMNumbers[startIndex] = temp;
    }
    
    return pre;
}


+ (void)quickSortV3:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
         startIndex:(NSInteger)startIndex
           endIndex:(NSInteger)endIndex {
    
    if ( endIndex <= startIndex ) {
        
        return;
    }
    
    NSInteger index = [self partitionV3:arrMNumbers
                             startIndex:startIndex
                               endIndex:endIndex];
    if ( index == -1 ) {
        
        return;
    }
    [self quickSortV3:arrMNumbers
           startIndex:startIndex
             endIndex:index - 1];
    [self quickSortV3:arrMNumbers
           startIndex:index + 1
             endIndex:endIndex];
}


+ (nullable NSArray<NSNumber *> *)quickSortV3:(nonnull NSArray<NSNumber *> *)arrNumbers {
    
    NSMutableArray<NSNumber *> *arrMNumbers = [arrNumbers mutableCopy];
    [self quickSortV3:arrMNumbers
           startIndex:0
             endIndex:arrMNumbers.count - 1];
    
    return [arrMNumbers copy];
}

DEMO