四 快速排序
因此快速排序的最差時(shí)間復(fù)雜度和冒泡排序是一樣的都是O(N2)吞滞，它的平均時(shí)間復(fù)雜度為O(NlogN)。其實(shí)快速排序是基于一種叫做“二分”的思想
- (void)viewDidLoad {
? ? [super viewDidLoad];
? ? NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),nil];
? ? [self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];
? ? NSLog(@"%@",arr);
}
- (void)quickSortArray:(NSMutableArray*)array withLeftIndex:(NSInteger)leftIndex andRightIndex:(NSInteger)rightIndex
{
? ? if(leftIndex >= rightIndex) {//如果數(shù)組長(zhǎng)度為0或1時(shí)返回
? ? ? ? return;
? ? }
? ? NSInteger i = leftIndex;
? ? NSInteger j = rightIndex;
? ? //記錄比較基準(zhǔn)數(shù)
? ? NSInteger key = [array[i] integerValue];
? ? while(i < j) {
? ? ? ? /**** 首先從右邊j開始查找比基準(zhǔn)數(shù)小的值 ***/
? ? ? ? while(i < j && [array[j] integerValue] >= key) {//如果比基準(zhǔn)數(shù)大，繼續(xù)查找
? ? ? ? ? ? j--;
? ? ? ? }
? ? ? ? //如果比基準(zhǔn)數(shù)小，則將查找到的小值調(diào)換到i的位置
? ? ? ? array[i] = array[j];
? ? ? ? /**** 當(dāng)在右邊查找到一個(gè)比基準(zhǔn)數(shù)小的值時(shí)舅踪，就從i開始往后找比基準(zhǔn)數(shù)大的值 ***/
? ? ? ? while(i < j && [array[i]integerValue] <= key) {//如果比基準(zhǔn)數(shù)小，繼續(xù)查找
? ? ? ? ? ? i++;
? ? ? ? }
? ? ? ? //如果比基準(zhǔn)數(shù)大良蛮，則將查找到的大值調(diào)換到j(luò)的位置
? ? ? ? array[j] = array[i];
? ? }
? ? //將基準(zhǔn)數(shù)放到正確位置
? ? array[i] =@(key);
? ? /**** 遞歸排序 ***/
? ? //排序基準(zhǔn)數(shù)左邊的
? ? [self quickSortArray:array withLeftIndex:leftIndex andRightIndex:i - 1];
? ? //排序基準(zhǔn)數(shù)右邊的
? ? [self quickSortArray:array withLeftIndex:i + 1 andRightIndex:rightIndex];
}
來(lái)源：iOS算法筆記-快速排序-OC實(shí)現(xiàn) - 簡(jiǎn)書
詳解：快排
