计划书：每天3个算法题、3个知识点
2018-12-19
算法题：
快排
- 时间复杂度：O(nlogn)，最坏情况下O(n^2)
- 空间复杂度：O(logn)
- 解法1:选取第一个数或最后一个数为基准
#选取第一个数为基准
def quick_sort(array, left, right):
if left >= right:
return
low = left
high = right
key = array[low]
while left < right:
while left < right and array[right] > key:
right = right-1
array[left] = array[right]
while left < right and array[left] < key:
left = left+1
array[right] = array[left]
array[right] = key
quick_sort(array, low, left-1)
quick_sort(array, left+1, high)
return array
#选取最后一个数为基准
def quick_sort(array, left, right):
if left < right:
pivot = partition(array, left, right)
quick_sort(array, left, pivot-1)
quick_sort(array, pivot+1, right)
def partition(array, left, right):
key = array[right]
i = left-1
for j in range(left,right):
if array[j] <= key:
i = i+1
array[i], array[j] = array[j], array[i]
array[i+1],array[r] = array[r], array[i+1]
return i+1
解法2:随机选取数为基准
好处：在待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就引入了随机选取枢轴。
python代码待补充。。。解法3:
三数取中法，解法参考https://www.jianshu.com/p/a92e6b40c6b7
好处：虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏情况下还是O(n^2），要缓解这种情况，就引入了三数取中选取枢轴。（上面的代码思想都是直接拿序列的最后一个值作为枢轴，如果最后这个值刚好是整段序列最大或者最小的值，那么这次划分就是没意义的。 所以当序列是正序或者逆序时，每次选到的枢轴都是没有起到划分的作用。快排的效率会极速退化。所以可以每次在选枢轴时，在序列的第一，中间，最后三个值里面选一个中间值出来作为枢轴，保证每次划分接近均等。）
python代码待补充。。。
冒泡排序
- 时间复杂度：
- 空间复杂度：
- 解法：从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大（小）的数据元素交换到了无序队列的队尾，从而成为有序序列的一部分；下一次继续这个过程，直到所有数据元素都排好序。标志变量用于记录每趟冒泡排序是否发生数据元素位置交换。如果没有发生交换，说明序列已经有序了，不必继续进行下去了。
def Bubble_sort(mylist):
for i in range(len(mylist)-1):
flag = False
for j in range(len(mylist)-1-i):
if mylist[j] > mylist[j+1]:
mylist[j], mylist[j+1] = mylist[j+1], mylist[j]
flag = True
if not flag:
break
归并排序
解法参考：https://www.jianshu.com/p/3ad5373465fd
12-20
知识点：
时间复杂度：O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
-
空间复杂度：
常见排序的时间及空间复杂度 逻辑回归&交叉熵（重点）
逻辑回归（logistic regression）定义：用来解决分类问题，因为通过拟合样本得到一个概率值。
- GBDT系列（重点）
决策树算法： - ID3（Iterative Dichotomiser 3）
- C4.5
- SVM
