天天看點

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)

IOS 排序算法寫在前面
//快排
- (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)

穩定性:不穩定

IOS 排序算法寫在前面
//希爾排序

- (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;
            
        }
        
    }
    
}
           
IOS 排序算法寫在前面

傳入數組的冒泡

這裡實作一個把數組傳進來的一個排序算法,傳回值也是一個數組

//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;
}
           

繼續閱讀