https://m./group/6647384153551536654/?iid=58051815856&app=news_article×tamp=1547734877&group_id=6647384153551536654&abtest_id=1 最近拿算法图解重新温习了一下算法,这本书真的非常适合入门,把比较简单算法细节和思路讲的非常清楚。 果然入门计算机语言就该学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 <= high: mid = int((low + high) / 2) guess = list[mid] if guess == item: return mid if guess > item: high = mid - 1 else: low = mid + 1 return Nonemy_list = [1, 3, 5, 7, 9]print(binary_search(my_list, 3)) # => 1print(binary_search(my_list, -1)) # => None
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: smallest = arr[i] smallest_index = i return smallest_indexdef selectionSort(arr): newArr = [] for i in range(len(arr)): smallest = findSmallest(arr) newArr.append(arr.pop(smallest)) return newArrprint(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 四、快速排序 (分而治之策略)
#!/usr/bin/pythondef quicksort(array): if len(array) < 2: return array else: pivot = array[0] less = [i for i in array[1:] if i <= pivot] #超级像伪代码! 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 arrayprint(simpleSort([9,8,6,7,4,5,3,11,2])) #[2, 3, 4, 5, 6, 7, 8, 9, 11]
归并排序: def mergeSort(array): if len(array) < 2: 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 < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 # 此时left或者right其中一个已经添加完毕,剩下的就全部加到result后面即可 result += left[i:] result += right[j:] return resultarray = [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的味道。 |
|
来自: 山峰云绕 > 《Python代码知识游戏黑客编程与英语》