寫在前面
排序算法寫在建立的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)
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2cs0TPn5keVRkT5lFVPpHOsJGcohVYsR2MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL0YzN4AjM1IjMzIjNwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
//快排
- (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;
}