iOS进阶收藏面试题

算法-几种排序算法 OC 版

2017-03-25  本文已影响390人  Q以梦为马

如果你交给某人一个程序,你将“折磨”他一整天;如果你教某人如何编写程序,你将“折磨”他一辈子。——《大话数据结构》

这阵子抽空看了一些算法与数据结构相关的东西,不得不说算法数据结构这些思想真的是博大精深,作为 iOS 开发人员,为什么要学习算法?说实话很多开发人员可能不会算法,但照样能做 App,有位大家都熟悉的大神在几个月前写了篇文章,我也是无意间读到的,搞 iOS 的学算法有意义吗?,大家有兴趣的话可以去读读。

这两天看了八大排序算法,并试着用 OC 语言写了几种,给大家分享下!

算法一:冒泡排序

个人觉得冒泡排序是最简单的排序了

#pragma mark - 冒泡排序
+ (void)bubbleSort:(NSMutableArray *)mutableArray {
    if(mutableArray == nil || mutableArray.count == 0)
        return;
    NSLog(@"冒泡排序之前: %@", mutableArray);
    for (NSInteger i = 0; i < mutableArray.count; i++) {
        for (NSInteger j = 0; j < mutableArray.count - i - 1; j++) {
            if ([mutableArray[j + 1] floatValue] < [mutableArray[j] floatValue]) {
                CGFloat tempFloat = [mutableArray[j] floatValue];
                mutableArray[j] = mutableArray[j + 1];
                mutableArray[j + 1] = [NSNumber numberWithFloat:tempFloat];
            }
        }
    }
    NSLog(@"冒泡排序之后: %@", mutableArray);
}

算法二:直接插入排序

#pragma mark - 直接插入排序
+ (void)insertSort:(NSMutableArray *)mutableArray {
    if(mutableArray == nil || mutableArray.count == 0)
        return;
    NSLog(@"直接插入排序之前: %@", mutableArray);
    for (NSInteger i = 0; i < mutableArray.count; i++) {
        CGFloat tempFloat = [mutableArray[i] floatValue];
        for (NSInteger j = i - 1; j >= 0 && tempFloat < [mutableArray[j] floatValue]; j--) {
            mutableArray[j + 1] = mutableArray[j];
            mutableArray[j] = [NSNumber numberWithFloat:tempFloat];
        }
    }
    NSLog(@"直接插入排序之后: %@", mutableArray);
}

算法三:选择排序

#pragma mark - 选择排序
+ (void)chooseSort:(NSMutableArray *)mutableArray {
    if(mutableArray == nil || mutableArray.count == 0)
        return;
    NSLog(@"选择排序之前: %@", mutableArray);
    for (NSInteger i = 0; i < mutableArray.count; i++) {
        for (NSInteger j = i + 1; j < mutableArray.count; j++) {
            if ([mutableArray[i] floatValue] > [mutableArray[j] floatValue]) {
                CGFloat tempFloat = [mutableArray[i] floatValue];
                mutableArray[i] = mutableArray[j];
                mutableArray[j] = [NSNumber numberWithFloat:tempFloat];
            }
        }
    }
    NSLog(@"选择排序之后: %@", mutableArray);
}

算法四:折半插入排序

#pragma mark - 折半插入排序
+ (void)binaryInsertSort:(NSMutableArray *)mutableArray {
    if(mutableArray == nil || mutableArray.count == 0)
        return;
    NSLog(@"折半插入排序之前: %@", mutableArray);
    for(NSInteger i = 1 ; i < mutableArray.count ; i++) {
        CGFloat tempFloat = [[mutableArray objectAtIndex:i] floatValue];
        NSInteger left = 0;
        NSInteger right = i - 1;
        
        while (left <= right) {
            CGFloat middle = (left + right) / 2;
            
            if(tempFloat < [[mutableArray objectAtIndex:middle] floatValue]){
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        for(NSInteger j = i ; j > left; j--) {
            [mutableArray replaceObjectAtIndex:j withObject:[mutableArray objectAtIndex:j - 1]];
        }
        [mutableArray replaceObjectAtIndex:left withObject:[NSNumber numberWithFloat:tempFloat]];
    }
    NSLog(@"折半插入排序之后: %@", mutableArray);
}

算法五:希尔排序

#pragma mark - 希尔排序
+ (void)shellSort:(NSMutableArray *)mutableArray {
    if(mutableArray == nil || mutableArray.count == 0)
        return;
    NSLog(@"希尔排序之前: %@", mutableArray);
    NSInteger shellValue = mutableArray.count / 2;
    while (shellValue >= 1) {
        for(NSInteger i = shellValue; i < mutableArray.count; i++) {
            CGFloat tempFloat = [[mutableArray objectAtIndex:i] floatValue];
            NSInteger j = i;
            while (j >= shellValue && tempFloat < [[mutableArray objectAtIndex:(j - shellValue)] floatValue]) {
                [mutableArray replaceObjectAtIndex:j withObject:[mutableArray objectAtIndex:j - shellValue]];
                j -= shellValue;
            }
            [mutableArray replaceObjectAtIndex:j withObject:[NSNumber numberWithFloat:tempFloat]];
        }
        shellValue = shellValue / 2;
    }
    NSLog(@"希尔排序之后: %@", mutableArray);
}

排序算法就先总结到这里,需要看代码打印效果的童鞋可以到这里下载代码:代码传送门

另外分享一篇很不错的博文,八大排序算法,下面是各种排序算法的时间复杂度空间复杂度以及稳定性的展示图表:

图片来自博文八大排序算法
上一篇下一篇

猜你喜欢

热点阅读