一个参考图
查找:
顺序查找 二分查找 hash查找
排序:
冒泡排序 选择排序 插入排序
希尔排序 归并排序 快速排序
顺序查找
原理:
从列表中第一个元素开始按顺序逐个查找
分析:
最好情况——第一个元素就是，复杂度O(1)
最欢情况——最后一个元素就是，要经历n步，复杂度O(n)
平均下来就是n/2步
所以，顺序查找的复杂度为O(n)
二分查找
HASH查找
原理:
定义某种hash函数，然后将列表中的每一项转化为一个与hash槽相关的数值，也就是每一项落在了hash表中的某个槽中，举个例子原始数据中有65这个数据，hash表有11个槽，65%11=10，于是65这个数据落在了10号槽。
查找的时候根据hash函数算出待查找的数所在的槽，便可一步搜到。
分析:
先不考虑一个槽中出现了多个数据的情况。
因为hash函数算出每个数据所在的位置一定了，所以其搜索操作不随列表项的增加而增加。hash查找的复杂度为O(1)。
冒泡排序
原理:
- 找出最大的值:
从第一个树开始与紧邻后面的一个数做比较，并通过交换位置来确保后面一个数要大于与其做比较的前一个数。直到列表的最末尾变成了最大值 - 然后找出次大的值
- 重复直到找到最小值
分析:
最好的情况:
列表本身就是顺序列表，只需遍历一遍列表即可，其复杂度为O(n)
最坏的情况:
列表本身是个逆序列表，需要遍历n次列表，一共需要的操作步数为n(n+1)/2，其复杂度为O(n^2)
于是冒泡排序的复杂度为O(n^2)
选择排序
原理:
选择排序是冒泡排序的改进版，每一次遍历只需要进行一次交换。冒泡排序每次遍历可能需要进行多次交换，而选择排序只需找到最大的值，然后将它与最后一个数交换位置。
最终遍历n-1次，进行n-1次交换。
分析:
虽然选择排序交换次数减少，但比较次数与冒泡排序相同。因此选择排序的空间复杂度与冒泡排序同为O(n^2)
