快速排序
快速排序的思想是这样的：如果要排序数组中下标从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)。
