// 冒泡排序
- (void)bubbleSort {
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@"98",@"75",@"89",@"53",@"67",@"92"]];
for (int i = 0; i < array.count - 1; i++) {
for (int j = 0; j < array.count-1-i; j++) {
//原理：從第1個(gè)數(shù)開始起邪蛔，與后面的數(shù)字相互比較急黎，滿足條件的向后位移（值交換），若不滿足條件侧到，拿到大一點(diǎn)的數(shù)值繼續(xù)向后比較
if ([array[j] intValue] > [array[j+1] intValue]) {
// 開始交換數(shù)據(jù)
NSString *temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
NSLog(@"%@",array);
}
}
// 選擇排序
- (void)selectSort {
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@"98",@"75",@"89",@"53",@"67",@"92"]];
for (int i = 0; i < array.count-1; i++) {
// 原理：從i后面第i+1個(gè)數(shù)起勃教，跟array[i]相互比較，滿足條件即交換值
for (int j = i+1; j < array.count; j++) {
// if里面的 '>' '<' 條件決定了排序的 升降
if ([array[i] intValue] > [array[j] intValue]) {
NSString *temp = array[j];
array[j] = array[i];
array[i] = temp;
}
}
NSLog(@"%@",array);
}
}
// 二分法查找
- (void)binarySearch {
// OC方法實(shí)現(xiàn)二分法：indexOfObject:inSortedRange:options:usingComparator:
/*
NSArray *sortedArray = ... // must be sorted
id searchObject = ...
NSRange searchRange = NSMakeRange(0, [sortedArray count]);
NSUInteger findIndex = [sortedArray indexOfObject:searchObject
inSortedRange:searchRange
options:NSBinarySearchingFirstEqual
usingComparator:^(id obj1, id obj2)
{
return [obj1 compare:obj2];
}];
*/
NSArray *numberArray = @[@1, @3, @27, @36, @42, @70, @82];
NSNumber *searchNum = @70;
NSUInteger mid;
NSUInteger min = 0;
NSUInteger max = [numberArray count] - 1;
BOOL found = NO;
while (min <= max) {
mid = (min + max)/2;
if ([searchNum intValue] == [numberArray[mid] intValue]) {
NSLog(@"We found the number! It is at index %lu", mid);
found = YES;
break;
} else if ([searchNum intValue] < [numberArray[mid] intValue]) {
max = mid - 1;
} else if ([searchNum intValue] > [numberArray[mid] intValue]) {
min = mid + 1;
}
}
if (!found) {
NSLog(@"The number was not found.");
}
}
// 快排和希爾排序
// Created by 葛朋 on 2018/5/26.
- (void)viewDidLoad {
[super viewDidLoad];
NSMutableArray *arr = [[NSMutableArray alloc] initWithObjects:@(6), @(1),@(2),@(5),@(9),@(4),@(3),@(7),@(100),@(80),@(88),@(30),@(35),@(20),@(14),@(34),@(88),@(83),nil];
NSDate* dat = [NSDate dateWithTimeIntervalSinceNow:0];
NSTimeInterval a=[dat timeIntervalSince1970];
// [self quickSortArray:arr withLeftIndex:0 andRightIndex:arr.count - 1];
[self xierAry:arr];
NSDate* dat2 = [NSDate dateWithTimeIntervalSinceNow:0];
NSTimeInterval a2 =[dat2 timeIntervalSince1970];
NSLog(@"%@--時(shí)間:%f",arr,(a2 - a));
}
- (void)xierAry:(NSMutableArray *)ary{
NSInteger n = ary.count;
for (NSInteger gap = n/2 ; gap > 0; gap /= 2) {
for (NSInteger i = gap; i < n; i++) {
for (NSInteger j = i - gap; j>= 0 && ary[j] > ary[j+ gap]; j-= gap) {
[ary exchangeObjectAtIndex:j withObjectAtIndex:(j+gap)];
}
}
}
}
- (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];
}
特別感謝 葛朋 快排、希爾排序
Created by 葛朋 on 2018/5/26.
