核心思想：分治
第一种：挖坑法
C++：
// 挖坑法
int QuickSort::partitionV1(std::vector<int> &arrNumbers, int startIndex, int endIndex) {
int key = arrNumbers[startIndex];
int i = startIndex;
int j = endIndex;
while ( i < j ) {
while ( i < j && arrNumbers[j] >= key ) {
--j;
}
if ( i < j ) {
arrNumbers[i] = arrNumbers[j];
}
while ( i < j && arrNumbers[i] <= key ) {
++i;
}
if ( i < j ) {
arrNumbers[j] = arrNumbers[i];
}
}
arrNumbers[i] = key;
return i;
}
void QuickSort::sortV1(std::vector<int>& arrNumbers, int startIndex, int endIndex) {
if ( endIndex <= startIndex ) {
return;
}
int index = partitionV1( arrNumbers, startIndex, endIndex );
sortV1( arrNumbers, startIndex, index - 1 );
sortV1( arrNumbers, index + 1, endIndex );
}
void QuickSort::sortV1(std::vector<int>& arrNumbers) {
sortV1( arrNumbers, 0, arrNumbers.size() - 1 );
}
Objective-C：
// 挖坑法
+ (NSInteger)partitionV1:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex {
NSNumber *key = arrMNumbers[startIndex];
NSInteger i = startIndex;
NSInteger j = endIndex;
while ( i < j ) {
while ( i < j && arrMNumbers[j].integerValue >= key.integerValue ) {
--j;
}
if ( i < j ) {
arrMNumbers[i] = arrMNumbers[j];
}
while ( i < j && arrMNumbers[i].integerValue <= key.integerValue ) {
++i;
}
if ( i < j ) {
arrMNumbers[j] = arrMNumbers[i];
}
}
arrMNumbers[i] = key;
return i;
}
+ (void)quickSortV1:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex {
if ( endIndex <= startIndex ) {
return;
}
NSInteger index = [self partitionV1:arrMNumbers
startIndex:startIndex
endIndex:endIndex];
[self quickSortV1:arrMNumbers
startIndex:startIndex
endIndex:index - 1];
[self quickSortV1:arrMNumbers
startIndex:index + 1
endIndex:endIndex];
}
+ (nullable NSArray<NSNumber *> *)quickSortV1:(nonnull NSArray<NSNumber *> *)arrNumbers {
NSMutableArray<NSNumber *> *arrMNumbers = [arrNumbers mutableCopy];
[self quickSortV1:arrMNumbers
startIndex:0
endIndex:arrMNumbers.count - 1];
return [arrMNumbers copy];
}
第二种：指针交换法
C++：
// 指针交换法
int QuickSort::partitionV2(std::vector<int> &arrNumbers, int startIndex, int endIndex) {
int i = startIndex;
int j = endIndex;
while ( i != j ) {
while ( i < j && arrNumbers[j] >= arrNumbers[startIndex] ) {
--j;
}
while ( i < j && arrNumbers[i] <= arrNumbers[startIndex] ) {
++i;
}
if ( i < j ) {
// swap
arrNumbers[i] = arrNumbers[i] ^ arrNumbers[j];
arrNumbers[j] = arrNumbers[i] ^ arrNumbers[j];
arrNumbers[i] = arrNumbers[i] ^ arrNumbers[j];
}
}
if ( i != startIndex) {
arrNumbers[i] = arrNumbers[i] ^ arrNumbers[startIndex];
arrNumbers[startIndex] = arrNumbers[i] ^ arrNumbers[startIndex];
arrNumbers[i] = arrNumbers[i] ^ arrNumbers[startIndex];
}
return i;
}
void QuickSort::sortV2(std::vector<int>& arrNumbers, int startIndex, int endIndex) {
if ( endIndex <= startIndex ) {
return;
}
int index = partitionV2( arrNumbers, startIndex, endIndex );
sortV2( arrNumbers, startIndex, index - 1 );
sortV2( arrNumbers, index + 1, endIndex );
}
void QuickSort::sortV2(std::vector<int>& arrNumbers) {
sortV2(arrNumbers, 0, arrNumbers.size() - 1);
}
Objective-C：
// 指针交换法
+ (NSInteger)partitionV2:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex {
NSInteger i = startIndex;
NSInteger j = endIndex;
while ( i != j ) {
while ( i < j && arrMNumbers[j].integerValue >= arrMNumbers[startIndex].integerValue ) {
--j;
}
while ( i < j && arrMNumbers[i].integerValue <= arrMNumbers[startIndex].integerValue ) {
++i;
}
if ( i < j ) {
NSNumber *temp = arrMNumbers[i];
arrMNumbers[i] = arrMNumbers[j];
arrMNumbers[j] = temp;
}
}
NSNumber *temp = arrMNumbers[i];
arrMNumbers[i] = arrMNumbers[startIndex];
arrMNumbers[startIndex] = temp;
return i;
}
+ (void)quickSortV2:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex {
if ( endIndex <= startIndex ) {
return;
}
NSInteger index = [self partitionV2:arrMNumbers
startIndex:startIndex
endIndex:endIndex];
[self quickSortV2:arrMNumbers
startIndex:startIndex
endIndex:index - 1];
[self quickSortV2:arrMNumbers
startIndex:index + 1
endIndex:endIndex];
}
+ (nullable NSArray<NSNumber *> *)quickSortV2:(nonnull NSArray<NSNumber *> *)arrNumbers {
NSMutableArray<NSNumber *> *arrMNumbers = [arrNumbers mutableCopy];
[self quickSortV2:arrMNumbers
startIndex:0
endIndex:arrMNumbers.count - 1];
return [arrMNumbers copy];
}
第三种：前后指针法
C++：
// 前后指针法
int QuickSort::partitionV3(std::vector<int> &arrNumbers, int startIndex, int endIndex) {
int cur = startIndex;
int pre = cur - 1;
while ( cur <= endIndex ) {
while ( cur <= endIndex && arrNumbers[cur] <= arrNumbers[startIndex] ) {
++cur;
pre = cur - 1;
}
while ( cur <= endIndex && arrNumbers[cur] >= arrNumbers[startIndex] ) {
++cur;
}
if ( cur <= endIndex && pre + 1 < cur ) {
std::swap( arrNumbers[pre + 1], arrNumbers[cur] );
pre = pre + 1;
cur = pre + 1;
}
}
if ( pre <= endIndex && pre != startIndex ) {
std::swap( arrNumbers[pre], arrNumbers[startIndex] );
}
return pre;
}
void QuickSort::sortV3(std::vector<int>& arrNumbers, int startIndex, int endIndex) {
if ( endIndex <= startIndex ) {
return;
}
int index = partitionV3( arrNumbers, startIndex, endIndex );
sortV3( arrNumbers, startIndex, index - 1 );
sortV3( arrNumbers, index + 1, endIndex );
}
void QuickSort::sortV3(std::vector<int>& arrNumbers) {
sortV3(arrNumbers, 0, arrNumbers.size() - 1);
}
Objective-C：
// 前后指针法
+ (NSInteger)partitionV3:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex {
NSInteger cur = startIndex;
NSInteger pre = cur - 1;
while ( cur <= endIndex && pre <= endIndex ) {
while ( cur <= endIndex && arrMNumbers[cur].integerValue <= arrMNumbers[startIndex].integerValue ) {
++cur;
pre = cur - 1;
}
while ( cur <= endIndex && arrMNumbers[cur].integerValue >= arrMNumbers[startIndex].integerValue ) {
++cur;
}
if ( cur <= endIndex && pre + 1 <= endIndex && pre + 1 < cur ) {
NSNumber *temp = arrMNumbers[cur];
arrMNumbers[cur] = arrMNumbers[pre + 1];
arrMNumbers[pre + 1] = temp;
pre = pre + 1;
cur = pre + 1;
}
}
if ( pre != startIndex && pre <= endIndex ) {
NSNumber *temp = arrMNumbers[pre];
arrMNumbers[pre] = arrMNumbers[startIndex];
arrMNumbers[startIndex] = temp;
}
return pre;
}
+ (void)quickSortV3:(nonnull NSMutableArray<NSNumber *> *)arrMNumbers
startIndex:(NSInteger)startIndex
endIndex:(NSInteger)endIndex {
if ( endIndex <= startIndex ) {
return;
}
NSInteger index = [self partitionV3:arrMNumbers
startIndex:startIndex
endIndex:endIndex];
if ( index == -1 ) {
return;
}
[self quickSortV3:arrMNumbers
startIndex:startIndex
endIndex:index - 1];
[self quickSortV3:arrMNumbers
startIndex:index + 1
endIndex:endIndex];
}
+ (nullable NSArray<NSNumber *> *)quickSortV3:(nonnull NSArray<NSNumber *> *)arrNumbers {
NSMutableArray<NSNumber *> *arrMNumbers = [arrNumbers mutableCopy];
[self quickSortV3:arrMNumbers
startIndex:0
endIndex:arrMNumbers.count - 1];
return [arrMNumbers copy];
}
网友评论