面试题，算法

一. 二叉树遍历

1. 先序遍历 跟节点 A 然后遍历 B子树 遍历完B子树后 再遍历C子树 ABDGHECKFIJ
2. 中序遍历为 左子树 根 右子树 GDHBEAKCIJF
3. 后序遍历是 左子树 右子树 根 GHDEBKJIFCA

二. 排序

排序

1. 冒泡排序

  - (void)popSort {
    int array[] = { 6, 2, 4, 1, 5, 9 };
    int temp = 0;
    for (int i = 1 ; i < 6 ;++i) {
        for (int j = 0 ;j < i ; ++j) {
            if (array[i] > array[j]) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    
    for (int i = 0 ; i < 6 ;++i) {
        NSLog(@"%d",array[i]);
    }
}

2. 插入排序

- (void)insertSort {
   int array[] = { 6, 2, 4, 1, 5, 9 };
   for (int i = 1 ; i < 6 ;++i) {
       int temp = array[i];
       int j;
       for (j = i - 1 ; j >= 0 ;--j) {
           if (array[j] > temp) {
               array[j + 1] = array[j];
           } else {
               break;
           }
       }
       array[j + 1] = temp;
   }
   for (int i = 0 ; i < 6 ;++i) {
       NSLog(@"%d",array[i]);
   }
}

3. 快速排序

void quickSort(int s[], int l, int r)
{
    if (l < r)
    {
        int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
        quickSort(s, l, i - 1); // 递归调用
        quickSort(s, i + 1, r);
    }
}

int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
{
    int i = l, j = r;
    int temp = 0;
    while (i < j)
    {
        // 从右向左找小于x的数来填s[i]
        while(i < j && s[j] >= s[i])
            j--;
        if(i < j)
        {
            temp = s[i];
            s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑
            s[j] = temp;
            i++;
        }
        
        // 从左向右找大于或等于x的数来填s[j]
        while(i < j && s[i] < s[j])
            i++;
        if(i < j)
        {
            temp = s[j];
            s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑
            s[i] = temp;
            j--;
        }
    }
    //退出时，i等于j。将x填到这个坑中。
//    s[i] = x;
    
    return i;
}

三. 数组旋转90度

- (void)rotate90 {
    NSMutableArray *array = [@[@(1),@(2),@(3),
                              @(4),@(5),@(6),
                              @(7),@(8),@(9),
                              @(10),@(11),@(12)] mutableCopy];
    NSMutableArray *resultArray = [NSMutableArray new];
    int width = 3, height = 4;
    for (int i = 0 ; i < width ; ++i) {
        for (int j = 0 ; j < height ; ++j) {
            resultArray[i * height + j] = array[width * (height - j) - (width - i)];
        }
    }
    NSLog(@"result = %@",resultArray);
}

四.单向链表翻转

struct node
{
    int val;
    struct node *pNext;
};
void display(struct node *pHead);
struct node *gen();

// 生成链表
struct node *gen()
{
    struct node *pHead = NULL;
    
    for(int i = 10; i > 0; i--){
        struct node * p = (struct node *)malloc(sizeof(struct node));
        p -> val = i;
        p -> pNext = pHead;
        pHead = p;
    }
    return pHead;
}

// 显示链表
void display(struct node *pHead)
{
    while( pHead != NULL)
    {
        printf("%d ", pHead->val);
        pHead = pHead->pNext;
    }
    printf("\n");
}

// 反转链表调用
{
    struct node rootNode = *gen();
    display(&rootNode);
    struct node node1 = *reverse2(&rootNode);
    display(&node1);
}

// 正常翻转
struct node *reverse(struct node *rootNode) {
    struct node *last = NULL;
    struct node *current = rootNode;
    struct node *newHeader = NULL;
    
    while (current != NULL) {
        struct node *temp = current->pNext;
        if (temp == NULL) {
            newHeader = current;
        }
        current->pNext = last;
        last = current;
        current = temp;
    }
    return newHeader;
}

// 递归翻转
struct node *reverse2(struct node *header) {
    if (header->pNext == NULL) {
        return header;
    }
    struct node *next = header->pNext;
    struct node *pre  = reverse2(next);
    header->pNext = NULL;
    next->pNext = header;
    return pre;
}

五.哈希冲突解决方案

1. 开发定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
2. 再哈希法
3. 链地址法

六.时间复杂度的表示