python技术面试题(十五)--算法
正文共： 7049 字 5 图 预计阅读时间： 18 分钟
每日分享
If you lose, don't lose the lesson.
直译：如果你输了，不要失去教训。
意译：吃一堑长一智。
小闫语录：
输了并不代表一无所有，你所经历的同样宝贵。如果你没有总结教训，只是沉浸在阴霾中，这样你就真的输了。
昨天公众号突然来了好多新的小伙伴，希望大家学有所成，也希望我的文章可以帮助到你。同时谢谢大家的关注。新来的小伙伴一定要先看使用指南。在文末的『优质文章推荐』第一篇。历史文章通过关键字查询方法见菜单栏『来看看嘛』中。方便你更好的使用本公众号。
算法
1. 算法的五大特性
输入：算法具有0个或多个输入。
输出：算法至少有一个输出。
有穷性：算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成。
确定性：算法中的每一步都有确定的含义，不会出现二义性。
可行性：算法的每一步都是可行的，也就是说每一步都能够执行有限次数完成。
2. 冒泡排序的思想
冒泡排序的过程，就好像咱们喝汽水时，那些小气泡一点一点从下往上的冒，最后到了最顶部。这只是一种形象的类比，用实际的例子来说明一下。假如有一个列表，其中的数字是无序排列的，通过冒泡要实现的结果就是将列表中的数字从小到大排序。
那么怎么实现呢？我们可以将列表中左侧第一个和第二个数字先进行比较，将较小的排在左侧；然后再比较第二个和第三个数字，较小的排在左侧，再比较第三个和第四个......将列表中的数字第一轮比较完之后，最大的数，排在了列表的最尾端。然后重复上面的步骤，但是尾端最大的数不再参与比较，一轮一轮的比较完之后，实现将列表中的数字从小到大排序后的效果。这样是不是最小的数一点一点从后往前冒了呢？
冒泡的最优时间复杂度为O(n)，最坏时间复杂度为O(n^2)。空间复杂度为O(1)。
那么下面使用代码实现一个冒泡排序：
def bubble_sort(alist):
for j in range(0,len(alist)-1):
for i in range(j):
if alist[i] > alist[i+1]:
alist[i],alist[i+1] = alist[i+1],alist[i]
print(alist)
alist = [66,0,1,55,3,99,100,2553245]
bubble_sort(alist)
print(alist)
---------------结果--------------
[0, 66, 1, 55, 3, 99, 100, 2553245]
[0, 1, 66, 55, 3, 99, 100, 2553245]
[0, 1, 55, 66, 3, 99, 100, 2553245]
[0, 1, 55, 3, 66, 99, 100, 2553245]
[0, 1, 3, 55, 66, 99, 100, 2553245]
[0, 1, 3, 55, 66, 99, 100, 2553245]细心的人已经看出来了，输出的最后两个列表是一样的。也就是在排序的过程中有一些步骤是无用的，因为比较的过程中有些元素已经实现了有序，不需要再比较。这是一个需要优化的地方，感兴趣的小伙伴可以自己手动优化一下。优化过后你会发现还有需要优化的地方，如果感兴趣，可以查找一下关于鸡尾酒排序的资料。
3. 快速排序的思想
快速排序的方法和冒泡排序类似，也属于交换排序。也就是通过不断的比较元素之间的大小，同时不断的交换元素的位置，实现排序的效果。那么它为什么叫快速排序呢？因为它快啊！（......很欠揍的样子）
我们简单的了解一下快速排序。快速排序就是先找到一个基准（一般来说拿列表中的第一个元素先做为基准），然后利用这个基准，将列表中的元素分为两部分。一部分（这部分中的元素每一个都要比基准大）放在基准的右侧；另一部分（这一部分中的元素都比基准小）放在基准左侧。第一轮划分完毕，第二轮会将左部分和右部分再次进行第一轮的步骤。然后不断的划分啊划分啊划分啊......直到最后列表中的元素变成了有序，就结束排序。
看到了上面的步骤是不是发现一个问题？这不就是我们的递归思想吗？对的，稍后我们就利用递归的方法实现一个快速排序。
快速排序的最优时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)，空间复杂度为O(logn)。它是不稳定的。
下面使用代码实现一个快速排序：
# ==============快速排序==================
def quick_sort(alist, start, end):
# 递归的退出条件
if start >= end:
return
# 设定起始元素为要寻找位置的基准元素
mid = alist[start]
# low为序列左边的,由左向右移动的游标
low = start
# high为序列右边的,由右向左移动的游标
high = end
while low < high:
# 如果low与high未重合，high指向的元素比基准元素大，则high向左移动
while low < high and alist[high] >= mid:
high -= 1
# 当high指向的元素比基准元素小了
# 将high指向的元素放到low的位置上
alist[low] = alist[high]
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low < high and alist[low] < mid:
low += 1
# 当low指向的元素比基准元素大了
# 将low指向的元素放到high的位置上
alist[high] = alist[low]
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置
# 将基准元素放到该位置
alist[low] = mid
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low-1)
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low+1, end)
alist = [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)python中没有指针的概念，上述代码中的游标就类似于指针的效果。 本次使用的方法和c语言中的“挖坑法”类似。当然还有其他的很多方法，大家可以查阅相关资料进行学习。
4. 插入排序
插入排序是一种简单直观的排序方法，我想说一句废话（插入排序就是通过插入来实现排序），想了想还是忍住了。插入排序的思路是什么样的呢？下面且听我慢慢道来。
有一个无序列表，让我们将其中的元素从小到大进行排序。使用插入排序，首先将从左到右的第一个元素所在的区域叫做有序区，其他的元素在的区域叫做无序区。然后将无序区中的元素从左到右开始取，取出来一个元素就将其放在有序区的合适位置（比如无序区取了一个3，有序区有两个数字1和4，那么我们就将3放到1和4之间）。不断的从无序区取，向有序区合适位置插，直到最后无序区没有值了，列表也就变成了有序列表。
最优时间复杂度为O(n)，最坏时间复杂度为O(n^2)，具有稳定性。
那么用代码实现一个插入排序：
def insert_sort(alist):
# 从第二个位置，即下标为1的元素开始向前插入
for i in range(1, len(alist)):
# 从第i个元素开始向前比较，如果小于前一个元素，交换位置
for j in range(i, 0, -1):
if alist[j] < alist[j-1]:
alist[j], alist[j-1] = alist[j-1], alist[j]5. 选择排序
有了上面算法的基础，选择排序理解就没那么难了。
同样有一个无序列表，我们需要对其从小到大进行排序。使用选择排序的话，我们先从列表中挑选出一个最大值，然后将其和列表最尾端的值进行调换。最后一个元素就是最大值，毫无悬念，它找到了自己的最终归属，不需要再参与排序（它所在的区域叫做有序区，剩余元素处于无序区）。剩下的元素再挑选一个最大值，将其放到放到有序区的合适位置......不断的重复以上步骤，直到所有的元素放到有序区，得到了一个有序列表，完成我们的需求。
最优时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)，不稳定。
代码实现：
def selection_sort(alist):
n = len(alist)
# 需要进行n-1次选择操作
for i in range(n-1):
# 记录最小位置
min_index = i
# 从i+1位置到末尾选择出最小数据
for j in range(i+1, n):
if alist[j] < alist[min_index]:
min_index = j
# 如果选择出的数据不在正确位置，进行交换
if min_index != i:
alist[i], alist[min_index] = alist[min_index], alist[i]6. 希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 DL.Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
最优时间复杂度根据步长序列的不同而不同，最坏时间复杂度为O(n^2)，不稳定。
看完后你心中肯定有一万头草泥马在奔腾了，一定想说『说人话！』好吧，还是用个例子说明一下希尔排序的思想吧.....
希尔排序的基本思想是：将数组列在一个表中并对列分别进行插入排序，重复这过程，不过每次用更长的列（步长更长了，列数更少了）来进行。最后整个表就只有一列了。将数组转换成表是为了更好地理解这算法，算法本身还是使用数组进行排序。
例如，假设有这样一组数[ 13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10 ]，如果我们以步长为5开始进行排序，我们可以通过将这些数放在有5列的表中来更好地描述算法，这样他们就像下面了：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10然后我们对每列进行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45将上述四行数字，依序接在一起时我们得到：[ 10,14,73,25,23,13,27,94,33,39,25,59,94,65,82,45 ]。这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45再次对列进行排序，变为下面这样：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94然后将上面的6行数字在衔接在一起：[ 10,14,13,25,23,33,27,25,59,39,65,73,45,94,82,94 ]。然后我们以1为步长进行排序，此时就是简单的插入排序了。最后结果为：
[10, 13, 14, 23, 25, 25, 27, 33, 39, 45, 59, 65, 73, 82, 94, 94]我们使用代码实现一个希尔排序：
def shell_sort(alist):
n = len(alist)
# 初始步长
gap = n // 2
while gap > 0:
# 按步长进行插入排序
for i in range(gap, n):
j = i
# 插入排序
while j>=gap and alist[j-gap] > alist[j]:
alist[j-gap], alist[j] = alist[j], alist[j-gap]
j -= gap
# 得到新的步长
gap = gap // 2
alist = [ 13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10 ]
shell_sort(alist)
print(alist)7. 桶排序
当列表中的数值取值范围太大，或者不是整数的时候，可以使用桶排序来解决问题。
桶排序基本思想就是将一个大区间划分成n个相同大小的子区间，称为桶。将n个记录分布到各个桶中。如果有多于一个记录被分到同一个桶中，需要进行桶内排序。最后依次把各个桶中的记录列出来就得到有序序列。
其实就是预先准备很多“桶”，然后把无序列表中的数，按照对应的区间放入桶中，桶里的数超过两个了，那么桶内再进行排序，然后将所有的数按照“桶”的顺序排列出来（一个桶内有多个数据的，按照桶内排好的顺序依次取出）。这是典型的以空间换时间，进行排序的数变少了，效率高了，时间就短了，但是占据了很多空间。
8. 归并排序
归并排序采用了分而治之的思想，先递归分解无序列表，再合并列表。我们先来看一下两个有序的列表如何进行合并：
1.我们有两个列表：
list1 = [3,5,7,8]
list2 = [1,4,9,10]2.为了合并，我们需要再建立一个空列表。
list = []3.然后就是将两个有序列表list1和list2分别从左到右比较两个列表中哪一个值比较小，然后复制进新的列表中：
# 一开始新列表是空的
['3',5,7,8] ['1',4,9,10] []
# 然后两个指针分别指向第一个元素，进行比较，显然，1比3小，所以把1复制进新列表中：
['3',5,7,8] [1,'4',9,10] [1]
# list2的指针后移，再进行比较，这次是3比较小：
[3,'5',7,8] [1,'4',9,10] [1,3]
# 同理，我们一直比较到两个列表中有某一个先到末尾为止，在我们的例子中，list1先用完。
[3,5,7,8] [1,4,'9',10] [1,3,4,5,7,8]
# 最后把list2中剩余的元素复制进新列表即可。
[1,3,4,5,7,8,9,10]为了突出比较的过程，我们将比较时的数字加了引号，其实它是int类型。由于前提是这两个列表都是有序的，所以整个过程是很快的。
上面就是归并排序中最主要的想法和实现了。接下来我们完整的对归并排序进行描述：
有一个列表，我们将其对半分，不断的重复这个过程，问题的规模就越来越小，直到分成了一个一个的数字（一个数字就相当于排好序了），接下来呢，就是类似于上面的过程了，两两合并，然后再两两合并，直到最后合并为一个有序的列表。正所谓天下之势，分久必合合久必分。现在有了一个了解了吧？
最优时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)，稳定。
代码实现：
def merge_sort(alist):
if len(alist) <= 1:
return alist
# 二分分解
num = len(alist)//2
left = merge_sort(alist[:num])
right = merge_sort(alist[num:])
# 合并
return merge(left,right)
def merge(left, right):
'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
#left与right的下标指针
l, r = 0, 0
result = []
while l<len(left) and r<len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += left[l:]
result += right[r:]
return result
alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = merge_sort(alist)
print(sorted_alist)
---------------------------
[17, 20, 26, 31, 44, 54, 55, 77, 93]9. 计数排序
对于那些数值取值范围不是很大的整数构成的列表怎么进行排序呢？那就是计数排序了，它的性能甚至会超过那些O(nlogn)的排序。神奇吧？
它是通过列表的下标来确定元素的正确位置。假如有一个列表，它由20个随机整数构成，且每个元素的取值范围从0到10。利用计数排序，我们可以建立一个长度为11的新列表，新列表下标从0到10上的元素初始值都为0。然后遍历无序的列表，每一个整数按照其值在新列表中进行对号入座，新列表中对应下标的元素进行加1操作（比如整数2，那么新列表中下标为2的元素由原来的0加1后变为了1；如果再有个整数2，那么下标为2的元素由原来的1加1变为了2。类似这样的操作，直到无序列表中所有的整数遍历完）。
新列表中每一个下标位置的值，代表的是无序列表中该整数出现的次数（下标的值与无序列表中对应的整数相等）。最后将新列表进行遍历，注意输出的是下标值，下标对应的元素是几，该下标就输出几次，遍历完成，无序列表变为了有序。
不适用于计数排序的情况：
1.当列表中最大值和最小值差距过大时；
2.当列表中元素不是整数时；
如果原始列表的规模是N，最大值和最小值的差是M的话，计数排序的时间复杂度和空间复杂度是多少呢？
答：时间复杂度为O(N+M)，空间复杂度如果只考虑统计列表大小的话，为O(M)。
优质文章推荐: