冒泡排序
1）依次比较相邻两个元素，顺序错误则交换位置；需要两层循环，外层循环控制趟数，内层循环控制比较次数
2）例子：
1
2
3
4
5
6
7
8
9
10
11
12
| NSMutableArray * arr = [NSMutableArray arrayWithArray:@[@"1",@"3",@"2",@"5",@"4"]];
// 外循环控制排序趟数,进行 array.count-1 趟
for (int i = 0; i < arr.count; i ++) {
// 记录是否进行了交换，如果没有交换，数组顺序为顺序，则直接跳出外层循环结束排序
for (int j = 0; j < arr.count - i - 1; j++) {
// 相邻元素比较，若逆序则交换
if ([arr[j] intValue] > [arr[j + 1] intValue]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
}
|
选择排序
1）从第一个元素与其他元素比较找到 最小值，重复操作，直到最后一位结束；需要两层循环，外层循环趟数，里层循环比较次数
2）例子
1
2
3
4
5
6
7
8
9
10
11
| NSMutableArray * arr = [NSMutableArray arrayWithObjects:@"2",@"1",@"5",@"3", nil];
// 外循环控制排序趟数,进行 array.count-1 趟
for (int i = 0; i < arr.count; i ++) {
// 里循环获比较换位
for (int j = i + 1; j < arr.count; j ++) {
if ([arr[i] intValue] > [arr[j] intValue]) {
[arr exchangeObjectAtIndex:i withObjectAtIndex:j];
}
}
}
NSLog(@"arr:%@",arr);
|
直接插入排序
1） 始终定义 第一个元素 为 已排序 的，将 剩余元素 定义为 未排序 逐个插入到 已排序 的排列中；不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去
2）例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| NSMutableArray * arr = @[@2,@1,@3,@5,@4].mutableCopy;
// 插入排序的原理：始终定义第一个元素为有序的，将未排序元素逐个插入到有序的排列中
// 其特点是：不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去
for(int i = 0;i < arr.count;i++){
// 待排序值
NSNumber * temp = arr[i];
// 已排序最大下标
int j = i - 1;
// 待排序与已排序比较，从后向前比较
while (j >= 0 && [arr[j] integerValue] > [temp integerValue]) {
// 如果已排序的 > 待排序的，将往后移动一个位置
[arr replaceObjectAtIndex:(j + 1) withObject:arr[j]];
j --;
}
// 空出来的位置插入新元素
[arr replaceObjectAtIndex:(j + 1) withObject:temp];
NSLog(@"arr:%@",arr);
}
|
打印结果：
1
2
3
4
5
6
7
| 2022-12-13 10:26:19.242271+0800 插入排序[4184:77845] arr:(
1,
2,
3,
4,
5
)
|
希尔排序
1）希尔排序相当于 直接插入排序加强版，引入了 增量 的概念；直到增量为 1 时，再进行直接插入排序
2）例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| NSMutableArray * arr = @[@7,@3,@8,@5,@2,@6,@1,@4].mutableCopy;
// 增量：起始 增量 设为总数的一半
int gap = arr.count/2;
// 直到增量小于1时结束
while (gap >= 1) {
// i 待排元素，以 增量 gap 从后向前扫描
for(int i = 0;i < arr.count;i++){
// 待排元素
NSNumber * temp = arr[i];
// 当前位置
int j = i;
// 跳跃式比较（当前位置）与（当前位置-增量）进行比较
while (j >= gap && [arr[j - gap] integerValue] > [temp integerValue] ) {
[arr replaceObjectAtIndex:j withObject:arr[j - gap]];
j -= gap;
}
// 插入待排序元素
[arr replaceObjectAtIndex:j withObject:temp];
}
// 改变步长
gap = gap/2;
}
NSLog(@"arr:%@",arr);
|
打印结果：
1
2
3
4
5
6
7
8
9
10
| 2022-12-13 10:22:41.910840+0800 插入排序[4124:74568] arr:(
1,
2,
3,
4,
5,
6,
7,
8
)
|
斐波那契数列
1）也就是 兔子数列，当前数是前两个数列之和
2）例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| - (void)viewDidLoad {
[super viewDidLoad];
NSInteger num = 10;
NSInteger total = [self getTotalNum:num];
NSLog(@"total:%ld",total);
}
- (NSInteger)getTotalNum:(NSInteger)num{
if(num == 0){
return 0;
}
if(num == 1){
return 1;
}
return [self getTotalNum:num-2] + [self getTotalNum:num-1];
}
|
打印结果：
1
| 2022-12-13 10:28:32.672554+0800 斐波那契数列[4285:80606] total:89
|
二分查找
1）有序的数组，将数组分割成两份，利用查找的值跟中间值进行比较，如果查找的值大于中间值，就在数组的右边进行查找；如果查找的值小于中间值，就在数组的左边进行查找。如此循环的执行下去，最终找到符合的值。
2）例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| NSArray * arr = @[@(1),@(3),@(5),@(6),@(8),@(10)];
int key = [@(5) intValue];
int min = 0;
int max = arr.count - 1;
int mid;
while (min <= max) {
// 计算中间下标
mid = (min + max) / 2;
// 如果目标值 > 中间下标的中间值
if (key > [arr[mid] intValue]) {
//最小变为中间下标+1
min = mid + 1;
}
// 如果目标值 < 中间下标的中间值
else if (key < [arr[mid] intValue]){
//最大变为中间下标-1
max = max - 1;
}
// 否则，正好
else {
NSLog(@"key:%d",mid);
break;
}
}
|
打印结果：
1
| 2022-12-13 10:33:18.661324+0800 二分查找[4607:86953] key:2
|
递归算法
递归求和1+2+..+n?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| - (void)viewDidLoad {
[super viewDidLoad];
int sum = [self sum:4];
NSLog(@"sum:%d",sum);
}
- (int)sum:(int)n{
if (n == 1) {
return 1;
}else {
return [self sum:n-1] + n;
}
}
|
