??快速排序（Quick Sort）是實(shí)際開發(fā)中經(jīng)常選用的一種排序方式。其排序原理：取數(shù)組中的首個(gè)元素為軸點(diǎn)數(shù)據(jù)，小于軸點(diǎn)的放在軸點(diǎn)前邊大于的放在軸點(diǎn)后邊，分成的左右子數(shù)組重復(fù)此操作的過(guò)程。
// 返回軸點(diǎn)下標(biāo)
- (NSInteger)sortArrayWithBegain:(NSInteger)begain end:(NSInteger)end
{
end--;
// 此處為了規(guī)避左右子數(shù)組不平衡的情況，將固定取數(shù)組第一個(gè)元素改為隨機(jī)取數(shù)組中的某個(gè)值為軸點(diǎn)元素，一定程度規(guī)避了最差時(shí)間復(fù)雜度的出現(xiàn)
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;
}
根據(jù)軸點(diǎn)將數(shù)組分成左右兩個(gè)子數(shù)組
- (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];
}
給出最初的排序數(shù)組
- (void)sort
{
[self sortArrayBegain:0 end:self.sortArray.count];
}
