快速排序（Quick Sort）是实际开发中经常选用的一种排序方式。其排序原理：取数组中的首个元素为轴点数据，小于轴点的放在轴点前边大于的放在轴点后边，分成的左右子数组重复此操作的过程。
// 返回轴点下标
- (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) {
if ([self compareObjcet:pivot anotherObject:self.sortArray[end]]) {
end--;
} else {
self.sortArray[begain++] = self.sortArray[end];
break;
}
}
while (begain < end) {
if ([self compareObjcet:self.sortArray[begain] anotherObject:pivot]) {
begain++;
} else {
self.sortArray[end--] = self.sortArray[begain];
break;
}
}
}
self.sortArray[begain] = pivot;
return begain;
}
根据轴点将数组分成左右两个子数组
- (void)sortArrayBegain:(NSInteger)begain end:(NSInteger)end
{
if (end - begain < 2) {
return;
}
NSInteger mid = [self sortArrayWithBegain:begain end:end];
[self sortArrayBegain:0 end:mid];
[self sortArrayBegain:mid + 1 end:end];
}
给出最初的排序数组
- (void)sort
{
[self sortArrayBegain:0 end:self.sortArray.count];
}
