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