数据结构与算法学习的每周总结
狗头保命
心里总是想着每周把学习的东西做一个记录和总结,但是行动总是跟不上,所以写总结的事情就一直一直一直耽搁着,时间长了,要总结的东西多了,觉得反正完成不了就放弃了。好在导师现在要求每周必须交总结,汇报学习的内容,内力没能让我克服惰性,那就借助外力吧,希望在导师的要求和帮助下,养成写总结的习惯。
PS:1.我很多工作的同学,每周都写总结。为了以后能够更好的适应工作,确实应该养成这个好习惯。
2.这个总结只写每周学的数据结构和算法有关的东西,和这个无关的我就单独写,原因是:我想着既然花时间写了就分门别类的写好,以后需要回顾的时候,也容易找到,不仅仅只是应付导师的检查(虽然导师检查是目前写的最大的推动力)。
3.这个算是学习过程的记录,自知写的太浅而且零碎,还请大佬们不要笑话,我会努力认真写的。
第一周
第一周总述
学数据结构与算法一段时间了,但是一直没有记录。所以第一周写的内容确切的说是前面好几周学的总结。根据我的总体规划,第一步是总的学一下这些知识,可能一知半解,但是至少能做到别人说起来,我也能听的懂在说啥的程度,然后第二步是细细的学习,多做一些题目。
所以第一周的内容是总体的叙述一些算法和数据结构的东西,很多东西只知道结果不知道为啥,后面一段时间会细化前面写的内容。
真是很久没有整理了,搞了蛮久才整理了4个排序算法。好多之前想的迷迷糊糊的地方又重新梳理了一遍,确实清晰了很多。剩下还没有整理的部分,这周整理吧,刚好这周开题答辩学不了新的东西
排序算法总体的学习
冒泡排序
原理:
我对冒泡法的理解:
每一轮只能确定一个数最终所在的位置(1.比如上第一轮就是确定了哪个值应该排在最上面 2.这里说的最终的意思是,下面个轮次是不会影响到这个值所在的位置的。比如第一轮后排到最上面的就是最大值,下面的轮次不会对这个已经排完的位置造成影响的)。
第二轮就是确定了第二大的那个值。如果一共有9个数,那就要确定9次,一次确定一个,全都确定完了也就排好序了(ps:9个数如果确定了8个,那么最后那个也就确定了,所以实际写代码的时候循环n-1次就行)。
确定的手段就是从最下面(如果脑子里想的是列表或者数组的话那就是从某一侧)挨个往上比较,碰到上面那个比下面那个小的就交换顺序,这样一轮后最上面那个肯定是最大值。
还有一种理解就是把这数组分成2部分,一部分是有序区,一部分是无序区。刚开始有序区有0个数,无序区有9个数。第一轮结束后,有序区就变为1个数,无序区就变为8个数。第二轮其实就是从无序区的8个数中重复做第一轮所做的事情【也许这就是递归的思想吧】,第二轮结束后有序区就是2个数,无序区就是7个数,以此类推直到无序区为0个数。
代码:
import random
def bubble_sort(dataList):
"冒泡排序"
for i in range(len(dataList)-1):#如果有8个数,那就必须执行7轮,一轮确定一个
for j in (range(len(dataList)-1-i)):#因为一轮有一个数确定了,8个数第一轮(i=0)比7次,第二轮6次
if(dataList[j+1]<dataList[j]):#下面那个比上面的大 就往上冒
dataList[j+1] ,dataList[j]=dataList[j],dataList[j+1] #调换顺序
datalist=list(range(100))
random.shuffle(datalist)#打乱
print("排序前:",datalist)
bubble_sort(datalist)#排序
print("排序后:",datalist)
时间复杂度:
先记住是$O(n^2)$。这个还分最坏情况和最好情况,平均情况。针对最坏情况还可以进行优化,这部分之后写吧。(先把标题扔在这儿)
选择排序
原理:
我觉得选择排序的思想和冒泡排序是一样的,就是每次确定出一个位置最终所在的数字是哪个,流程也是第一轮确定出最大的那个值,然后把这个最大的值安放在最上面那个位置。第二轮确定出二哥(你也可以认为是还没有确定最终所在位置的那堆数里的大哥)所在的位置。如果脑洞大开把这个要排序的数组在大脑中分成有序区与无序区这两部分,那就是每次从无序区里挑出大哥放到有序区里去。开始的时候有序区是0个数,无序区是9个数(假设一共有9个数参加排序),第一轮有序区就成了1个数,无序区就是8个数。一直这样整下去,有序区就是9个数,无序区就是0个数。
和冒泡法不一样的是,选择排序在无序区中挑出最大的那个值的方法不是挨个挨个往上比,碰到大的就交换。选择排序假设最下面那个值最大,把这个值放在手里,然后拿着这个值和其他的比,挨个比,发现其他的比这个值大就拿手里的这个小的和那个大的换,全都看一遍后,手里的那个值就一定时最大的了,知道了哪个是最大的把最大的那个和现在占着最大的那个值所在的位置的那个数交换。
选择排序与冒泡排序思想一样,操作的手段不同,导致了一个是稳定排序(冒泡,因为冒泡是挨着顺序往上冒),一个是不稳定排序(选择排序,飞着换的都不是稳定排序)。
代码:
import random
#给一个列表,从列表中挑出最大的那个值的下标
def findMaxDataIndex(dataList):
maxdataIndex=0
for i in range(1,len(dataList)):
if(dataList[i]>dataList[maxdataIndex]):
maxdataIndex=i
return maxdataIndex
#插入排序
def select_sort(dataList):
for i in range(len(dataList)-1):#如果是9个数,那就得至少走8轮
maxdataindex=findMaxDataIndex(dataList[0:len(dataList)-i])
dataList[maxdataindex],dataList[len(dataList)-1-i]=dataList[len(dataList)-1-i],dataList[maxdataindex]
datalist=list(range(100))
random.shuffle(datalist)#打乱
print("排序前:",datalist)
select_sort(datalist)#排序
print("排序后:",datalist)
时间复杂度:
先记住是$O(n^2)$。这个还分最坏情况和最好情况,平均情况。针对最坏情况还可以进行优化,这部分之后写吧。(先把标题扔在这儿)
插入排序
原理:
插入排序的思想和斗地主时摸牌一样,我们在斗地主(掼蛋)摸牌时,怎么确定刚摸到的牌放在哪里?
- 第一种情况:前面的那个比手上的那个小,后面那个比手上那个大,这时候就放在两者中间。
假如现在手上的牌是A24J,现在摸到了8,应该放在哪里?拿着8和J比发现J比8大,所以8应该在J前面,然后拿着8和4比,发现8比4大,所以8应该在4的后面,那就确定喽,在4的前面在8的后面。
- 第二种情况:最前面的那个比自己还大,或者最后面还没有自己大呢。
假如现在手上的牌是24J,现在摸到了A,应该放在哪里?你拿着A挨个比发现最小的2还比自己大,这时候你就知道A是已知的数中最小的,你就把A放在2前面。 同理你摸到了Q,你会发现比目前最大的J还要大,你就放在J的后面。
这个思想和冒泡和排序就不同了。这个如果是想成有序区和无序区的话,发现有序区其实是动态变化的,而不是和冒泡排序那样到了有序区就不变了。可能刚开始7在有序区里是最大的,但是从无序区里面取数往有序区里面插时有可能从无序区里取个9,那么有序区里放最大值的那个位置就变成了9,原来占着最大值的位置就得往后撤。
代码
import random
#插入排序的难点是怎么插入
def insert_sort(li):
for i in range(1,len(li)):#有多少个数就循环多少次
temp=li[i]#这个就是取出来的数
#将这个数插入有序区
j=i-1
#从后面向前面插入
#比如现在手上的牌是24J,然后这次摸到的是3
#那就先和J比发现没有J大,那J就往后退一个此时变为24JJ(在内存里)
#此时和4比 发现没有4大 此时变为244J
#此时和2比发现比2 大 此时变为234J
while j>=0 and li[j]>temp:
li[j+1]=li[j]
j-=1
li[j+1]=temp
datalist=list(range(100))
random.shuffle(datalist)#打乱
print("排序前:",datalist)
insert_sort(datalist)#排序
print("排序后:",datalist)
时间复杂度
先记住是$O(n^2)$。这个还分最坏情况和最好情况,平均情况。针对最坏情况还可以进行优化,这部分之后写吧。(先把标题扔在这儿)
快速排序
原理
快排,人如其名,就是快。python内置的sort排序里面用的就是优化后的快排,优化解决的问题是稳定性的问题,使用的手段是归并排序的思想。
这一轮变为2341576,5的左边都是比5小的,5的右边都是比5大的,也就是说其实5是确定了其最后所放的位置的。下面只要把5的左右两边排好序就行了。5的左边现在是2341,这个怎么排序呢,同样的把2提出来,然后确定出2最终所在的位置,得到的结果是1243,2的左边是1,右边是43,左边只有一个数不要排了,排右边就行,右边排完就是34。这样5的左边就排完了。同理排出5的右边
代码
import random
def partition(li, left, right):
tmp = li[left]
while left < right:
while left < right and li[right] >= tmp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= tmp:
left += 1
li[right] = li[left]
li[left] = tmp
return left
def _quick_sort(li, left, right):
if left < right: # 待排序的区域至少有两个元素
mid = partition(li, left, right)
_quick_sort(li, left, mid-1)
_quick_sort(li, mid+1, right)
def quick_sort(li):
_quick_sort(li, 0, len(li)-1)
datalist=list(range(100))
random.shuffle(datalist)#打乱
print("排序前:",datalist)
quick_sort(datalist)#排序
print("排序后:",datalist)
时间复杂度
先记住是$O(nlogn)$。这个还分最坏情况和最好情况,平均情况。针对最坏情况还可以进行优化,这部分之后写吧。(先把标题扔在这儿)
堆排序
归并排序
希尔排序
计数排序
桶排序
数据结构的学习
栈
链表
哈希树
总结
第一周总结
这周还有一些没写完,接下来的几周慢慢的补充这部分的内容吧。教训就是以后2-3天就得认真的记录一下,要不然一口气记录好几个星期确实吃不消啊。收获就是:写博客翻盘自己脑子里想的东西能够发现很多盲点。