Objective-C实现冒泡,选择,插入,快速排序算法

首先是header文件:

#import <Foundation/Foundation.h>

@interface Sort : NSObject{
    
}
//冒泡排序
-(void)bunbleSortWithArray:(NSArray *)aData;
//选择排序
-(void)selectSortWithArray:(NSArray *)aData;
//插入排序
-(void)insertSortWithArray:(NSArray *)aData;
//快速排序,对冒泡排序的一种改进
-(void)quickSortWithArray:(NSArray *)aData;
-(void)swapWithData:(NSMutableArray *)aData index1:(NSInteger)index1 index2:(NSInteger)index2;
@end

接着是实现:

#import "Sort.h"

@interface Sort()
-(void)quickSortWithArray:(NSArray *)aData left:(NSInteger)left right:(NSInteger)right;
@end

@implementation Sort

- (id)init
{
    self = [super init];
    if (self) {
        // Initialization code here.
    }
    
    return self;
}

-(void)bunbleSortWithArray:(NSArray *)aData{
    NSMutableArray *data = [[NSMutableArray alloc]initWithArray:aData];
    for (int i=0; i<[data count]-1; i++) {
        for (int j =0; j<[data count]-1-i; j++) {
            if ([data objectAtIndex:j] > [data objectAtIndex:j+1]) {
                [self swapWithData:data index1:j index2:j+1];
            }
        }
    }
    NSLog(@"冒泡排序后的结果:%@",[data description]);
}

-(void)selectSortWithArray:(NSArray *)aData{
    NSMutableArray *data = [[NSMutableArray alloc]initWithArray:aData];
    for (int i=0; i<[data count]-1; i++) {
        int m =i;
        for (int j =i+1; j<[data count]; j++) {
            if ([data objectAtIndex:j] < [data objectAtIndex:m]) {
                m = j;
            }
        }
        if (m != i) {
            [self swapWithData:data index1:m index2:i];
        }
    }
    NSLog(@"选择排序后的结果:%@",[data description]);
}

-(void)insertSortWithArray:(NSArray *)aData{
    NSMutableArray *data = [[NSMutableArray alloc]initWithArray:aData];
    for (int i = 1; i < [data count]; i++) {
        id tmp = [data objectAtIndex:i];
        int j = i-1;
        while (j != -1 && [data objectAtIndex:j] > tmp) {
            [data replaceObjectAtIndex:j+1 withObject:[data objectAtIndex:j]];
            j--;
        }
        [data replaceObjectAtIndex:j+1 withObject:tmp];
    }
    NSLog(@"插入排序后的结果:%@",[data description]);
}

-(void)quickSortWithArray:(NSArray *)aData{
    NSMutableArray *data = [[NSMutableArray alloc] initWithArray:aData];
    [self quickSortWithArray:data left:0 right:[aData count]-1];
    NSLog(@"快速排序后的结果:%@",[data description]);
    
}

-(void)quickSortWithArray:(NSMutableArray *)aData left:(NSInteger)left right:(NSInteger)right{
    if (right > left) {
        NSInteger i = left;
        NSInteger j = right + 1;
        while (true) {
            while (i+1 < [aData count] && [aData objectAtIndex:++i] < [aData objectAtIndex:left]) ;
            while (j-1 > -1 && [aData objectAtIndex:--j] > [aData objectAtIndex:left]) ;
            if (i >= j) {
                break;
            }
            [self swapWithData:aData index1:i index2:j];
        }
        [self swapWithData:aData index1:left index2:j];
        [self quickSortWithArray:aData left:left right:j-1];
        [self quickSortWithArray:aData left:j+1 right:right];
    }
}


//-(void)dealloc{
//}

-(void)swapWithData:(NSMutableArray *)aData index1:(NSInteger)index1 index2:(NSInteger)index2{
    NSNumber *tmp = [aData objectAtIndex:index1];
    [aData replaceObjectAtIndex:index1 withObject:[aData objectAtIndex:index2]];
    [aData replaceObjectAtIndex:index2 withObject:tmp];
}

@end

然后写main函数测试:

#import <Foundation/Foundation.h>
#import "Sort.h"

#define kSize 20
#define kMax 100

int main (int argc, const char * argv[])
{
    
    // insert code here...
    NSLog(@"Hello, World!");
    
    NSMutableArray *data = [[NSMutableArray alloc] initWithCapacity:kSize];
    
    for (int i =0;i<kSize;i++) {
        u_int32_t x = arc4random() % kMax;//0~kMax
        NSNumber *num = [[NSNumber alloc] initWithInt:x];
        [data addObject:num];
    }
    
    NSLog(@"排序前的数据:%@",[data description]);
    
    Sort *sort = [[Sort alloc] init];
    [sort bunbleSortWithArray:data];
    [sort selectSortWithArray:data];
    [sort insertSortWithArray:data];
    [sort quickSortWithArray:data];
    return 0;
}

相关推荐