首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

python编程,算法难学?不存在的,这书让你像小说一样入门

最近拿算法图解重新温习了一下算法,这本书真的非常适合入门,把比较简单算法细节和思路讲的非常清楚。

果然入门计算机语言就该学python。 大学里面一上来就C++太苦逼了。

然后是第一次强烈的感受到Python解题的魅力。之前学python的时候,觉得不用定义就直接使用很变扭,还有就是可以灵活的使用各种数据结构,也是有点不适应。因为一开始学的就是C++,之前算法和数据结构都是用C++写的,后面工作用Java。Python还没拿来用过。某神说,leetcode里面排名考前的都是用python提交的,因为写起来跟伪代码差不多,有思路就好了,不用像c++、java那样考虑语言的特性。

对于它们的语言特性最近的感受就是:Python就像塑料袋,什么东西都可以往里面塞,不怕变形,兼容性超好;Java像纸箱,类得写好了才能生成对象;C++跟java差不多,像木箱吧哈哈哈。

插要:

大概总结一下里面提到的算法吧(这里的代码都是用python3写的):

一、算法简介

1.1二分查找 :

一个有序数组中找一个数的位置(对应该数字所在数组下标index)。

def binary_search(list, item):

low = 0

high = len(list) - 1

while low

mid = int((low + high) / 2)

guess = list[mid]

if guess == item:

return mid

if guess > item:

high = mid - 1

else:

low = mid + 1

return None

my_list = [1, 3, 5, 7, 9]

print(binary_search(my_list, 3)) # => 1

print(binary_search(my_list, -1)) # => None

也可用递归实现操作对象:数组使用前提:有序的数组性能方面:时间复杂度O(logn)

1.2 旅行商问题:

旅行商前往n个城市,确保旅程最短。求可能的排序:n!种可能。

二、选择排序

2.1 数组和链表

数组:连续存储在硬盘中;链表:分散存储在硬盘中;

2.2 选择排序:将数组元素按照从小到大的顺序排序,每次从数组中取出最小值

def findSmallest(arr):

smallest = arr[0]

smallest_index = 0

for i in range(1, len(arr)):

if arr[i]

smallest = arr[i]

smallest_index = i

return smallest_index

def selectionSort(arr):

newArr = []

for i in range(len(arr)):

smallest = findSmallest(arr)

newArr.append(arr.pop(smallest))

return newArr

print(selectionSort([5, 3, 6, 2, 10])) #[2, 3, 5, 6, 10]

三、递归----一种优雅的问题解决方法

适用递归的算法要满足:

基限条件(即返回的条件)递归条件(调用递归函数)

特点:

自己调用自己,调用栈在内存叠加,如果没有返回条件,将无限循环调用,占用大量内存,最终爆栈终止进程。

还有一种高级一点的递归:

尾递归 (将结果也放入函数参数,内存里面调用栈只有一个当前运行的函数进程)

举个简单的例子: 阶乘f(n) = n!

def fact(x): #递归

if x == 1:

return 1

else:

return x * fact(x-1) #注意这里跟尾递归不同

#尾递归

def factorial(x,result):

if x == 1:

return result

else:

return factorial(x-1,x*result)

if __name__ == '__main__':

print(fact(5)) #5*4*3*2*1 = 120

print(factorial(5,1)) #120

四、快速排序 (分而治之策略)

每次选取数组中一个元素x当作分水岭(一般选取第一个元素):[小于元素x的数组]+[x]+[大于元素x的数组],然后递归调用,直到最后处理的数组元素只剩下零个或者一个平均时间复杂度O(nlogn)最差情况时间复杂度O(n^2) (出现这个情况是:快排的数组本来就是有序的(顺序/倒序),选取的元素又是开头第一个的话,每次变成只能处理一侧的数组了。 改善:可以选取数组中间的元素当作分水岭pivot,只有两边的元素就都能均匀处理了)

#!/usr/bin/python

def quicksort(array):

if len(array)

return array

else:

pivot = array[0]

less = [i for i in array[1:] if i

print(less)

greater = [i for i in array[1:] if i > pivot]

print(greater)

return quicksort(less) + [pivot] + quicksort(greater)

if __name__ == '__main__':

print(quicksort([7,1,10,5,3,2,6]))

'''

[1, 5, 3, 2, 6]

[10]

[]

[5, 3, 2, 6]

[3, 2]

[6]

[2]

[]

[1, 2, 3, 5, 6, 7, 10]

'''

到目前算法为止,复杂度对比:

排序到算法有:

冒泡排序,选择排序,快速排序,归并排序,堆排序(感兴趣到小伙伴可以自己去搜索)

下面列出冒泡排序和归并排序算法:

#冒泡排序,每次寻找最小到元素往前排,就像汽水从下往上冒一样。所以叫冒泡排序啦

def simpleSort(array):

for i in range(len(array)-1):

for j in range(i,len(array)):

if array[i] > array[j]:

temp = array[i]

array[i] = array[j]

array[j] = temp

return array

print(simpleSort([9,8,6,7,4,5,3,11,2])) #[2, 3, 4, 5, 6, 7, 8, 9, 11]

冒泡排序时间复杂度O(n^2)两个for循环搞定,每一轮for循环找到一个最小值。for循环两两元素对比交换

归并排序:

def mergeSort(array):

if len(array)

return array

else:

mid = int(len(array)/2)

left = mergeSort(array[:mid])

right = mergeSort(array[mid:])

return merge(left, right)

def merge(left, right): #并两个已排序好的列表,产生一个新的已排序好的列表

result = [] # 新的已排序好的列表

i = 0 # 下标

j = 0

# 对两个列表中的元素 两两对比

# 将最小的元素,放到result中,并对当前列表下标加1

while i

if left[i]

result.append(left[i])

i += 1

else:

result.append(right[j])

j += 1

# 此时left或者right其中一个已经添加完毕,剩下的就全部加到result后面即可

result += left[i:]

result += right[j:]

return result

array = [9,5,3,0,6,2,7,1,4,8]

result = mergeSort(array)

print('排序后:',result) #排序后: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

归并排序时间复杂度是O(nlogn)最坏情况也是O(nlogn)归并排序采用先分后总的方式,先按中间分,分到数组最后只有一个元素为止,最后两两合并。有点mapReduce的味道。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190117A15W4M00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券