快速排序

快速排序

快速排序的思想是这样的：如果要排序数组中下标从p到r之间的一组数据，选择p到r之间的任意一个数据作为pivot(分区点)。
遍历p到r之间的数据，将小于pivot的放到左边，将大于pivot的放到右边，将pivot放到中间。经过这一步骤之后，数组p到r之间的数据就被分成了三个部分，前面p到q-1之间都是小于pivot的，中间是pivot，后面的q+1到r之间是大于pivot的。

根据分治、递归的处理思想，可以用递归排序下标从p到q-1之间的数据和q+1到r之间的数据，直到区间缩小为1，就说明所有的数据都有序了。

代码实现如下：

@interface DMQuickSort : NSObject

// 快速排序
- (void)quickSort:(NSMutableArray *)dataArray;

@end

@implementation DMQuickSort

// 快速排序
- (void)quickSort:(NSMutableArray *)dataArray
{
    NSLog(@"快速排序前：%@", dataArray);
    if ([dataArray count] > 1) {
        [self quickSort:dataArray startIndex:0 endIndex:[dataArray count] - 1];
    }
    NSLog(@"快速排序后：%@", dataArray);
}

- (void)quickSort:(NSMutableArray *)dataArray startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex
{
    if (startIndex >= endIndex) {
        return;
    }
    
    // 获取分区点
    NSInteger tmpIndex = [self partitionDataArray:dataArray startIndex:startIndex endIndex:endIndex];
    [self quickSort:dataArray startIndex:startIndex endIndex:tmpIndex - 1];
    [self quickSort:dataArray startIndex:tmpIndex + 1 endIndex:endIndex];
}

// 获取分区点
- (NSInteger)partitionDataArray:(NSMutableArray *)dataArray startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex
{
    NSNumber *tmpValue = [dataArray objectAtIndex:endIndex];
    NSInteger targetIndex = startIndex;
    for (NSInteger i = startIndex; i <= endIndex; i++) {
        NSNumber *curNum = [dataArray objectAtIndex:i];
        if ([curNum integerValue] <= [tmpValue integerValue]) {
            NSNumber *oneNum = [dataArray objectAtIndex:targetIndex];
            [dataArray replaceObjectAtIndex:targetIndex withObject:curNum];
            [dataArray replaceObjectAtIndex:i withObject:oneNum];
            targetIndex++;
        }
    }
    
    return targetIndex - 1;
}

@end

@interface DMSortDemo : NSObject

@end

@implementation DMSortDemo

- (void)demo 
{   
    // 快速排序
    DMQuickSort *quickSort = [[DMQuickSort alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [dataArray addObject:[NSNumber numberWithInteger:10]];
        [dataArray addObject:[NSNumber numberWithInteger:2]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:1]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [quickSort quickSort:dataArray];
    }
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:11]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:9]];
        [dataArray addObject:[NSNumber numberWithInteger:8]];
        [quickSort quickSort:dataArray];
    }
}

@end

方法- (NSInteger)partitionDataArray:(NSMutableArray *)dataArray startIndex:(NSInteger)startIndex endIndex:(NSInteger)endIndex 就是随机选择一个元素作为pivot，然后对A[p...r]分区，返回pivot的下标。
如果不考虑空间消耗的话，分区方法可以写的非常简单。申请两个临时数组X和Y，遍历A[p...r]，将小于pivot的元素都拷贝到临时数组X，将大于pivot的元素都拷贝到临时数组Y，最后再将数组X和数组Y中数据顺序拷贝到A[p...r]。

如果按照这种思路实现的话，分区函数就需要很多额外的内存空间，所以快排就不是原地排序算法了。如果希望快排是原地排序算法，那它的空间复杂度得是O(1)，那分区函数就不能占用太多额外的内存空间，就需要在A[p...r]的原地完成分区操作。
通过游标i把A[p...r]分成两部分。A[p...i-1]的元素都是小于pivot的，暂且叫它“已处理分区”，A[i...r]是“未处理区”。每次都从未处理区间A[i...r]中取一个元素A[j]，与pivot对比，如果小于pivot，则将其加入到已处理区间的尾部，也就是A[i]的位置。如下图所示

因为分区的过程设计交换操作，如果数组中有两个相同的元素，比如序列6,7,6,3,5,4，在经过第一次分区操作之后，两个6的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

快速排序的性能分析

第一，快速排序是稳定的排序算法吗？

快速排序不是一个稳定的排序算法。

第二，快速排序的时间复杂度是多少？

快速排序在发部分情况下的时间复杂度都可以做到O(nlogn)，只有在极端情况下，才会退化到O(n*n)。

第三，快速排序的空间复杂度是多少？

快速排序是原地排序，所以空间复杂度是O(1)。