ios 数据结构和算法
链表
1、链表
查找
插入
移除
2、栈（先进后出，尾部添加或删除元素）
push（入栈）
pop（出栈）
peek（获取顶部值）
3、队列（先进先出，尾部添加元素，头部删除元素）
enqueue（入队）
dequeue（出队）
peek（获取顶部值）
4、双链表（与链表区别在于，双向指针）
查找
插入
移除
5、双端队列（与栈和队列的区别，首尾都能添加元素，首尾均能出列）
enqueue（入队）
dequeue（出队）
peek（获取顶部值）
排序算法
冒泡排序
/*
* 冒泡排序，相邻两个对比，前者比后者大，交换位置
*
*/
-(void)bubbleSort{
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@3,@44,@38,@5,@47,@15,@36,@26,@27,@2,@46,@4,@19,@50,@49]];
BOOL swapped = NO;
do {
swapped = NO;
for (int i = 1; i < array.count; i++) {
NSInteger num1 = [array[i-1] integerValue];
NSInteger num2 = [array[i] integerValue];
if (num1 >num2) {
[array replaceObjectAtIndex:i-1 withObject:[NSNumber numberWithInteger:num2]];
[array replaceObjectAtIndex:i withObject:[NSNumber numberWithInteger:num1]];
swapped = YES;
}
}
} while (swapped);
NSLog(@”冒的排序:%@”,array);
}
选择排序
/*
* 选择排序，标记*小值，循环比较，替换*小值
*
*/
-(void)selectionSort{
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@3,@44,@38,@5,@47,@15,@36,@26,@27,@2,@46,@4,@19,@50,@49]];
NSInteger repeatTimes = array.count -1;
int sortBeginIndex = 0;//开始对比下标
do {
int miniNumIndex = sortBeginIndex;
NSInteger miniNum = [array[sortBeginIndex] integerValue];
for (int i = sortBeginIndex +1; i < array.count; i++) {
NSInteger selectNum = [array[i] integerValue];
if (selectNum < miniNum) {
miniNum = selectNum;
miniNumIndex = i;
}
}
[array replaceObjectAtIndex:miniNumIndex withObject:array[sortBeginIndex]];
[array replaceObjectAtIndex:sortBeginIndex withObject:[NSNumber numberWithInteger:miniNum]];
sortBeginIndex ++;
repeatTimes –;
} while (repeatTimes > 0);
NSLog(@”选择排序:%@”,array);
}
插入排序
/*
* 插入排序，逐个元素拿出来，与其左边元素逐个对比，碰到比该元素小的元素，则插入在对比元素后
*
*/
-(void)insertionSort{
NSMutableArray *array = [NSMutableArray arrayWithArray:@[@3,@44,@38,@5,@47,@15,@36,@26,@27,@2,@46,@4,@19,@50,@49]];
int sortBeginIndex = 1;//开始对比下标
do {
NSInteger sortBeginNum = [array[sortBeginIndex] integerValue];
[array removeObjectAtIndex:sortBeginIndex];
for (int i = sortBeginIndex -1; i >= 0; i–) {
NSInteger compareNum = [array[i] integerValue];
if (compareNum < sortBeginNum) {
[array insertObject:[NSNumber numberWithInteger:sortBeginNum] atIndex:i+1];
break;
}else{
if (i==0) {
[array insertObject:[NSNumber numberWithInteger:sortBeginNum] atIndex:0];
}
}
}
sortBeginIndex ++;
} while (sortBeginIndex < array.count);
NSLog(@”插入排序:%@”,array);
}