数据结构和算法

1.复杂度和简单算法

简单的排序（）

1.选择排序

2.冒泡排序

3.插入排序

4.二分查找

对数器：

2.O(NlogN)的排序

求中点的方法

递归问题的时间复杂度求解：

master公式：（子）

1.归并排序（MergeSort）

一些问题的应用

2.快速排序

快排1.0，最后一个数做num，然后一直递归

快排2.0，荷兰国旗问题做递归，最坏效率O(n2)

快排3.0，随机选一个数放到最后做划分 O(NlogN) 空间复杂度o(logN)

3.堆，以及堆排序

左孩子2i+1，右边2i-1，父位置i-1/2

大根堆，小根堆（java优先级队列，PriorityQueue）

堆排序，先将数组变成一个堆，一直heapInsert构建好之后将第一个和最后一个交换做heapify取最大值

4.比较器，自定义结构的比较

5.桶排序radixSort（不基于比较）

6.总结

传统排序算法的指标

常见的坑

3.链表

1.哈希表

哈希表的增删改查都是常数级别的

2.有序表

3.快慢指针

问题

1.链表有无环，链表相交

4.二叉树

遍历方式（递归）：先序

               后序
               中序
            （非递归）：

宽度优先遍历，使用队列实现

sql=”select * from user where username=’”&username&”‘and pass=’”& pass&’”

用户名和密码都是 ’or’=’or’