冒泡排序 O(n^2)
NSArray *arr = @[@(49),@(38),@(65),@(97),@(76),@(13),@(27),@(48)];
NSMutableArray *mArr = [NSMutableArray arrayWithArray:arr];
///> 生序排序 大的在后面。大的往后面挪动 并不是和第一个比较大小
///> 每一次冒泡 都会把 最大的排在后面
for (NSInteger i = 0; i < mArr.count; i++) {
for (NSInteger j = 0; j < mArr.count - 1 - i; j++) {
if (((NSNumber *)mArr[j]).integerValue > ((NSNumber *)mArr[j + 1]).integerValue) {
[mArr exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
}
NSLog(@"appDidEnterForeground1 %@",mArr);
快排 O(nlog n) 期望时间，O(n^2) 最坏情况
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归以此达到整个数据变成有序序列
NSMutableArray *marr = @[@(29),@(23),@(54),@(3),@(34),@(4),@(34),@(54),@(24),@(40)].mutableCopy;
[self fastSortingWith:marr left:0 right:marr.count - 1];
NSLog(@"%@",marr);
///>. 第一次排序就将比我大的排后面。小的排前面 左右开弓。直到左面小与右面
- (void)fastSortingWith:(NSMutableArray *)arr left:(NSInteger)l right:(NSInteger)r {
if (l >= r) {//如果数组长度为0或1时返回
return;
}
NSInteger i = l;
NSInteger j = r;
NSInteger key = [arr[i] integerValue];
while (i < j) {
///> 从右面查找。小的 交换到 i的位置 i做为交换位 NB
while (i < j && [arr[j] integerValue] >= key) {
j--;
}
arr[i] = arr[j];
///> 从左面查找大 的交换位置 j
while (i < j && [arr[i] integerValue] <= key) {
i++;
}
arr[j] = arr[i];
}
///> 交换位 归位
arr[i] = @(key);
///> 递归左面
[self fastSortingWith:arr left:l right:i-1];
///> 递归右面
[self fastSortingWith:arr left:i+1 right:r];
}
插入排序.插入到有序的数组中 O(n^2)
- (void)insertSort:(NSMutableArray *)array {
for (NSInteger i = 1; i < array.count; i++) {
NSInteger j = i; //j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序
NSInteger temp = [array[i] integerValue]; //temp 是从坑里取数
//把a[i]插入有序序列 因为已经排序好。所以直接找到对应的位置j就好
while (j > 0 && temp < [array[j - 1] integerValue]) { //j > 0 防止越界。写&&前面效率更高
array[j] = array[j - 1];
j--;
}
array[j] = @(temp);
}
}
选择排序 将最小的放到前面 O(n^2)
for (int i=0; i<arr_M.count; i++) {
for (int j=i+1; j<arr_M.count; j++) {
if (arr_M[i]<arr_M[j]) {
[arr_M exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
分开 然后一个一个merge成一个新的数组
iOS开发-冒泡、快排、 插入排序、选择排序、及二分查找
