IOS 排序算法

写在前面

排序算法写在创建的NSMutableArray分类中，因此self代表我们待排序的数组；

算法兼容了升序与降序两种情况，根据输入的

isAcs

来判断是升序或者降序

NSMutanleArray中存放都是对象，对于基本类型的排序对象，对应的是NSNumber或NSString，对数据进行比较的时候要使用

compare

，不能直接使用

>

、

<

、

==

#import "NSMutableArray+SortWay.h"

@implementation NSMutableArray (SortWay)
//交换方法
- (void) swapWithIndex1:(NSInteger)index1 index2:(NSInteger)index2 {
    id temp = self[index1];
    self[index1] = self[index2];
    self[index2] = temp;
}

///排序算法
//isAcs : YES 升序  NO  降序

@end
           

##冒泡排序算法

时间复杂度：最好（有序情况下）O(n)，平均（逆序情况下）O(n^2)

空间复杂度：O(1)

- (void) sortArrayWithBulleAsc:(BOOL)isAcs {
    NSInteger arrayCount = self.count;
    for (NSInteger i = arrayCount - 1; i > 0; i--) {
        BOOL flag = NO;
        for (NSInteger j = 0 ; j < i; j++) {
            if ((isAcs && [self[j] compare:self[j + 1]] == NSOrderedAscending ) || (!isAcs && [self[j] compare:self[j + 1]] == NSOrderedDescending)) {
                [self swapWithIndex1:j index2:j + 1];
                flag = YES;
            }
        }
        if (!flag) {
            break;
        }
    }
}
           

快排

时间复杂度：最好（越接近无序，算法越高效）O(n)，最坏（越接近有序，算法越低效）O(n^2)，平均O(nlogn)

空间复杂度：O(logn)

//快排
- (void) sortArrayWithQuickLowIndex:(NSInteger)low highIndex:(NSInteger)high isAcs:(BOOL)isAcs {
    NSInteger i =low, j = high;
    while (i < j) {
        id temp = self[i];
        while (i < j && ((isAcs && [temp compare:self[j]] == NSOrderedDescending) || (!isAcs && [temp compare:self[j]] == NSOrderedAscending))) {
            j --;
        }
        if (i < j) {
            self[i] = self[j];
            i++;
        }
        while (i < j && ((isAcs && [temp compare:self[i]] == NSOrderedAscending) || (!isAcs && [temp compare:self[j]] == NSOrderedDescending))) {
            i ++;
        }
        if (i < j) {
            self[j] = self[i];
            j --;
        }
   }
        self[i] = temp;
        
        [self sortArrayWithQuickLowIndex:low highIndex:i - 1 isAcs:isAcs];
        [self sortArrayWithQuickLowIndex:i + 1 highIndex:high isAcs:isAcs];
}
           

选择排序

时间复杂度：O(n^2 )

空间复杂度：O(1)

思想：从头至尾顺序扫描序列，找出最小的一个记录，和第一个记录交换，接着从剩下的记录中继续这种选择和交换，最终使序列有序。

//选择排序
- (void) sortArrayWithSelect:(BOOL)isAcs {
    for (NSInteger i = 0; i < self.count; i++) {
        NSInteger index = i;
        for (NSInteger j = i + 1; j < self.count; j ++) {
       		id temp = self[index];
            if ((isAcs && [temp compare:self[j]] == NSOrderedAscending) || (!isAcs && [temp compare:self[j]] == NSOrderedDescending)) {
                index = j;
            }
        }
        
        [self swapWithIndex1:i index2:index];
    }
}
           

直接插入排序

时间复杂度： O(n^2)

空间复杂度：O(1)

稳定性：稳定

//直接插入排序
- (void) sortArrayInsert:(BOOL)isAcs {
    for (NSInteger i = 1; i < self.count; i ++) {
        id temp = self[i];
      	NSInteger j = 0
        for ( j = i; j > 0; j --) {
            if ((isAcs && [self[j] compare:self[j - 1]] == NSOrderedAscending) || (!isAcs && [self[j] compare:self[j - 1]] == NSOrderedDescending)) {
                self[j] = self[j - 1];
            }else {
              break;
            }
        }
        self[j] = temp;
    }
}
           

希尔排序

时间复杂度：平均O(nlogn)

空间复杂度：O(1)

稳定性：不稳定

//希尔排序

- (void) sortArrayShell:(BOOL)isAcs {
    
    for (NSInteger d = self.count / 2; d > 0; d /= 2 ) {
        
        for (NSInteger i = d; i < self.count; i ++) {
            id temp = self[i];
          	NSInteger j = 0;
            for (j = i; j >= 0; j-= d ) {
                if ((isAcs && [self[j] compare:self[j - d]] == NSOrderedAscending) ||  (!isAcs && [self[j] compare:self[j - d]] == NSOrderedDescending)) {
                  self[j + d] = self[j];
                }else {
                  break;
                }
            }
          self[j] = temp;
            
        }
        
    }
    
}
           

传入数组的冒泡

这里实现一个把数组传进来的一个排序算法，返回值也是一个数组

//isAsc : YES 升序  NO  降序
- (NSMutableArray *) sortArray:(NSArray*)array isAsc:(BOOL)isAsc {
    NSMutableArray *tempArray = [NSMutableArray arrayWithArray:array];
    NSInteger arrayCount = tempArray.count;
    for (NSInteger i = arrayCount - 1; i > 0; i--) {
        BOOL flag = NO;
        for (NSInteger j = 0 ; j < i; j++) {
            if ((isAsc && [tempArray[j] compare:tempArray[j + 1]] == NSOrderedAscending ) || (!isAsc && [tempArray[j] compare:tempArray[j + 1]] == NSOrderedDescending)) {
                [self swapMutArray:tempArray index1:j index2:j+1];
                flag = YES;
            }
        }
        if (!flag) {
            break;
            
        }
    }
    
    return tempArray;
}


- (void) swapMutArray:(NSMutableArray*)array index1:(NSInteger)index1 index2:(NSInteger)index2 {
    id temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}