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