算法-快速排序

快速排序的思想就是分治法，取任意一个数为基数，从左或者从右边开始比较，从左边比的话就是比基数小，从右边比的话就是比基数大，这样一分为二，最终就是基数左边的比基数小，右边的比基数大，依次在去分解左边的数据和右边的数据

1、经典写法

1.1双向填坑法

// 左侧为基准，右侧开始
- (void)quickSort:(NSMutableArray *)arr left:(int)l right:(int)r {
    if (l >= r) {
        return;
    }
    int i=l,j=r,x=[arr[l] intValue];
    while (i<j) {
        while (i<j && [arr[j] intValue] >= x) {
            j--;
        }
        if (i<j) {
            arr[i]=arr[j];
            i++;
        }
        while (i<j && [arr[i] intValue] < x) {
            i++;
        }
        if (i<j) {
            arr[j]=arr[i];
            j--;
        }
    }
    arr[i] = [NSString stringWithFormat:@"%d",x];
    [self quickSort:arr left:l right:i-1];
    [self quickSort:arr left:i+1 right:r];
}

1.2双向交换法

// 左侧为基准，左侧开始
- (void)quickSort:(NSMutableArray *)arr left:(int)l right:(int)r {
    if (l >= r) {
        return;
    }
    int i=l,j=r,x=[arr[l] intValue];
    while (i<j) {
        while ([arr[i] intValue] <= x) {
            i++;
        }
        while ([arr[j] intValue] > x) {
            j--;
        }
        if (i<j) {
            [self swapArr:arr i:i j:j];
        }
    }
    [self swapArr:arr i:j j:l];
    [self quickSort:arr left:l right:j-1];
    [self quickSort:arr left:j+1 right:r];
}

2、算法导论-单向交换法

过程图解.png partition伪代码

// 右侧为基准，左侧开始
- (int)partition:(NSMutableArray *)a left:(int)p right:(int)r {
    int x = [a[r] intValue];
    int i = p-1;
    for (int j = p ; j<r; j++) {
        if ([a[j] intValue] <= x) {
            i++;
            [self swapArr:a i:i j:j];
        }
    }
    [self swapArr:a i:i+1 j:r];
    return i+1;
}
- (void)quickSortSF:(NSMutableArray *)arr left:(int)l right:(int)r {
    if (l<r) {
        int i = [self partition:arr left:l right:r];
        [self quickSortSF:arr left:l right:i-1];
        [self quickSortSF:arr left:i+1 right:r];
    }
}