算法

算法（Algorithm）：一个计算过程，解决问题的方法。

时间复杂度

时间复杂度是用来估计算法运行时间的单位。一般来说时间复杂度低的算法更快。常见的时间复杂度如下（按效率从高到低）：

• O(1)
• O(logn)
• O(n)
• O(nlogn)
• O(n*n)，应该是n的平方，打不出来

不常见的时间复杂度（特别复杂的）：

• O(n!)，N的阶乘
• O(2^n)，2的N次方
• O(n^n)，N的N次方

快速判断时间复杂度：

• 有循环减半的情况：O(logn)
• 有m次循环：O(n^m)，n的m次方

空间复杂度

空间复杂度是用来评估算法内存占用大小的一个式子。

不展开了，有个概念叫“空间换时间”。

排序

排序讲了下面九种方法：

• 下面3个算法算比较Low的，但是好理解
  • 冒泡排序
  • 选择排序
  • 插入排序
• 快速排序
• 下面2个是比较难的
  • 堆排序
  • 归并排序
• 最后的三个地位比较尴尬，没什么人用
  • 基数排序
  • 希尔排序
  • 桶排序

排序算法关键点：有序区和无序区。

一开始都是无序区，然后慢慢的产生有序区，有序区逐步变大，无序区逐步变小。最后全部都是有序区，排序完成。

冒泡排序

冒泡算是最基础和常用的了，下面的两个算法了解一下就好了，一般用还是用冒泡的。

代码如下：

import randomdef bubble_sort(li):    for i in range(len(li) - 1):        for j in range(len(li) - i - 1):            if li[j] > li[j+1]:                li[j], li[j+1] = li[j+1], li[j]        print(li)    return liif __name__ == '__main__':    li = random.sample(range(10), 10)    print(bubble_sort(li))

从头开始，每次比较相邻的两个数，如果前面的大，就交换位置。然后往后移一位再进行比较。一直比较到最后，这是一趟。一趟完成后，最大的数就移到最后了，有序区就增加了一位。这一趟进行了n-1次比较。

下一趟的话，由于无序区少了一位，所以比上一趟少比较一次。如果已经比较了i趟，这趟只需要比较n-i-1次。所以每一趟比较的次数是n-i-1次，就是n-i-1次循环，这个是内层的循环。总共需要比较n-1躺，这个是外层的循环，循环n-1次。

时间复杂度：O(n^2)

优化：如果某一趟里没有进入if进行交换，那么实际排序就完成了，可以直接结束了。下面是优化了的算法：

def bubble_sort(li):    for i in range(len(li) - 1):        exchange = False        for j in range(len(li) - i - 1):            if li[j] > li[j+1]:                li[j], li[j+1] = li[j+1], li[j]                exchange = True        if not exchange:            break        print(li)    return li

选择排序

一趟遍历最小的数，放到第一个位置；再一趟，遍历余下的数，找到最小的放到下一个位置……

代码如下：

import randomdef select_sort(li):    for i in range(len(li) - 1):        min_index = i        for j in range(i+1, len(li)):            if li[min_index] > li[j]:                min_index = j        if min_index != i;            li[min_index], li[i] = li[i], li[min_index]        print(li)    return liif __name__ == '__main__':    li = random.sample(range(10), 10)    print(select_sort(li))

时间复杂度：O(n^2)

插入排序

插入排序，先用扑克摸牌来描述一下。首先摸到一张牌，直接加入手牌，你手上就是有序区。然后摸到下一张，遍历你的手牌，把新摸到的牌插到合适的位置。如此循环，直到把牌摸完，你手上的牌就是排好序的了。不过这和下面代码的逻辑有很大差别。

最初，认为第一个位置是有序区，后面的是无序区。然后有序区向无序区扩充一位，把新加入到有序区的元素插到对应的位置，直到无序区变空。插入的过程是，其实也是一次冒泡，依次一个一个比较，如果大小反了，就交换位置。

def insert_sort(li):    for i in range(1, len(li)):        tmp = li[i]        for j in range(i):            if li[i-j-1] > tmp:                li[i-j-1], li[i-j] = li[i-j], li[i-j-1]            else:                li[i-j] = tmp                break        print(li)    return li

这里不知道写成这样还是不是插入排序了。不过故意写的和冒泡很像。

冒泡算法是，每一趟在无序区做一次冒泡，每一趟冒泡的区域减少1个元素。而这里，每一趟，在有序区的最后加入一个元素，做一次冒泡，每一趟冒泡的区域增加一个元素。冒泡算法，优化后，外层的循环有可能提前结束。这里是内层的循环有可能提前结束。所以时间复杂度，包括各种理想情况下的复杂度，这两种算法感觉是一样的。时间复杂度：O(n^2)如果不是一次就能获得整个列表，而是像开头描述的那样，一张牌一张牌的摸上来，这种场景下，应该是插入算法更合适。

快速排序

这个是好写的排序算法里最快的，快的排序算法里最好写的。

思路：去一个元素P（就取第一个元素），使P归位（某个方法）；归位后的效果是列表被P粉尘了2个部分，左边都比P小，右边都比P大；然后递归完成排序：

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)

上面的partition就是归位的方法，接下来是归位的思路：mid、left、right都是下标。先把P元素取出来，现在left的位置空出来了，right的位置向左移动，同时和P比较，找到的第一个比P小的元素，移动到left的位置。然后right左边停在新的位置，left的位置向右移动，同时和P比较，找到的第一个比P大的元素，移动到right的位置。上面的步骤交替进行直到left和tight重叠，把P元素放到这个位置完成归位。

这里想到了一句歌词：跟着我，左手右手一个慢动作，右手左手慢动作重播下面是加上归位方法的完整代码：

import randomdef quick_sort(li):    def _quick_sort(li, left, right):        if left < right:            mid = partition(li, left, right)            print(li)            _quick_sort(li, left, mid-1)            _quick_sort(li, mid+1, right)        return li    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]        # 到这里left和right是一样的了，所以用left少个字母        li[left] = tmp        return left    left = 0    right = len(li)-1    return _quick_sort(li, left, right)if __name__ == '__main__':    li = random.sample(range(10), 10)    print(quick_sort(li))

递归函数不要加装饰器：

这里再封装了一层，不只是因为要传3个参数。入口函数值需要传列表就可以了，另外2个参数是列表下标的最小值和最大值。还有一个好处是，可以加装饰器，但是装饰器不能直接给递归函数加，否则每次递归都会带上装饰器。如果要计算运行时间的话，装饰器不能加载递归函数上。解决办法就是这样，外面再封装一层不会调用自己的然后可以加装饰器。关于这里效率的提高，可以这么理解。在一个时间复杂度里，做了更多的事情。之前的3种方法，一趟只把一个数放到了该去的位置，其他数不管。而这里，在一个时间复杂度里，不光把一个数放到了它该在的位置，还把两边的数字大小分开了。内建的排序python原本就提供列表的排序 li.sort() ，大多数语言包括python，他们的排序算法也都是快速排序。不过python原生的方法比我们自己写的方法更快，这个主要是因为内建方法的底层是C语言实现的。结论就是，学这个也没用，主要就是掌握算法。要排序还是调用.sort()就好了。

时间复杂度：O(nlogn)

不严谨的计算，每次都切一半，然后循环N次，就是上面的复杂度。但是其实并不一定每次正好切一半的。极端情况下，甚至每次都是拿到了最大或最小的数，并没有把其他元素分在两边，而是都在一边，另外一边是没有的。这样时间复杂度还是O(N^2)。

递归深度

由于这是用递归实现的，python有最大递归深度。如果深度不够，那么要手动设置一下 sys.setrecursionlimit(999) 。

堆排序

理解堆排序之前，首先得理解二叉树

二叉树

先要理解一下二叉树，二叉树是度不超过2的树。

满二叉树，像下面这样全填满就是了。

完全二叉树，看图更好理解。

完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。依次从上往下，从左往右排，排出来的就是完全二叉树。

看下面的这个完全二叉树，每个元素里表了数字。父节点的数字是i，那么它左孩子节点就是2i+1，它的右孩子节点就是2i+2。

可以把上面的每个圈圈看做是一个元素，里面的数字就是这个元素在数组里的下标，现在把内容填进去就是这样的：

小结

现在可以把数组存放到一个完全二叉树里。通过规律可以从父亲的下标得到孩子的下标，或从孩子的下标找到父亲的下标。

堆排序

堆是一颗特殊的完全二叉树，有下面2种：

• 大根堆：任意节点都比其孩子节点大
• 小根堆：任意节点都比其孩子节点小

堆排序过程：

1. 建立堆
2. 得到堆顶元素
3. 去掉堆顶，将堆最后一个元素放到堆顶。此时通过一次调整重新使堆有序
4. 得到堆顶元素，为第二个元素
5. 重复之前的步骤，直到堆变空

import randomdef sift(li, low, high):    """做一次调整使堆有序"""    i = low  # 父节点下标    j = 2 * i + 1  # 左孩子下标    tmp = li[i]  # 父节点的值    while j <= high:        if j < high and li[j] < li[j+1]:  # j

归并排序

假设列表分两段有序，如何将其合并为一个有序列表？

1. 先拿到两个下标，第一段列表第一个元素的下标和第二段列表第一个元素的下标
2. 比较两个下标对应的元素，得到一个值，加入到一个新的列表，然后对应的下标向后移一位
3. 重复上面的步骤，直到某一个列表取完所有的值，把剩下的列表直接加到新列表的最后

上面的操作称作一次归并，一次归并的代码：

def merge(li, low, mid, high):    """一次归并    low是这次归并第一个元素的下标    mid是第一个列表的最后一个元素，判断还有数    high是第二个列表的最后一个元素，判断还有数    """    i = low  # 第一个列表的第一个元素的下标    j = mid+1  # 第二个列表的第一个元素的下标    li_tmp = []    while i <= mid and j <= high:  # 两个列表必须都有数字        if li[i] < li[j]:            li_tmp.append(li[i])            i += 1        else:            li_tmp.append(li[j])            j += 1    while i <= mid:        li_tmp.append(li[i])        i += 1    while j <= high:        li_tmp.append(li[j])        j += 1    li[low:high+1] = li_tmp  # 最后把临时的列表写回去

运用归并排序

1. 分解：将列表越分越小，直至分成一个元素
2. 一个元素一定是有序的
3. 合并：将两个有序列表归并，列表越合越大

下面是完整的归并代码。分解用了递归，代码简单了，但是理解起来难一点：

import randomdef merge_sort(li):    def merge(li, low, mid, high):        """一次归并        low是这次归并第一个元素的下标        mid是第一个列表的最后一个元素，判断还有数        high是第二个列表的最后一个元素，判断还有数        """        i = low  # 第一个列表的第一个元素的下标        j = mid+1  # 第二个列表的第一个元素的下标        li_tmp = []        while i <= mid and j <= high:  # 两个列表必须都有数字            if li[i] < li[j]:                li_tmp.append(li[i])                i += 1            else:                li_tmp.append(li[j])                j += 1        while i <= mid:            li_tmp.append(li[i])            i += 1        while j <= high:            li_tmp.append(li[j])            j += 1        li[low:high+1] = li_tmp  # 最后把临时的列表写回去    def _merge_sort(li, low, high):        if low < high:            mid = (low + high) // 2            # 下面是递归，每次分一半，直到分完            _merge_sort(li, low, mid)  # 列表前一半            _merge_sort(li, mid+1, high)  # 列表后一半            # 上面的递归，如果列表只有一个元素了，low 和 high就相等，就不满足if条件，递归结束            merge(li, low, mid, high)    low, high = 0, len(li)-1    _merge_sort(li, low, high)    return liif __name__ == '__main__':    li = random.sample(range(10), 10)    print(merge_sort(li))

自己写了一个

上面的例子中的分解是通过递归从大到小每次切一半，完成的分解。我的逻辑第一次0和1做归并，2和3做归并。然后一趟跑完后，2个2个做归并。依次4+4、8+8，直到全部做完：

import randomdef merge_sort(li):    def merge(li, low, mid, high):        """一次归并        low是这次归并第一个元素的下标        mid是第一个列表的最后一个元素，判断还有数        high是第二个列表的最后一个元素，判断还有数        """        i = low  # 第一个列表的第一个元素的下标        j = mid+1  # 第二个列表的第一个元素的下标        li_tmp = []        while i <= mid and j <= high:  # 两个列表必须都有数字            if li[i] < li[j]:                li_tmp.append(li[i])                i += 1            else:                li_tmp.append(li[j])                j += 1        while i <= mid:            li_tmp.append(li[i])            i += 1        while j <= high:            li_tmp.append(li[j])            j += 1        li[low:high+1] = li_tmp  # 最后把临时的列表写回去    i = 1  # 每次i个元素做归并    # 外循环，每次做完整个数组里所有小组的归并后，放大范围继续    while i < len(li):        low = 0        mid = low + i - 1        high = mid + i        # 内循环，根据i分出若干小组，每组都做一次归并        while high < len(li)-1:  # 留着最后一组归并在else里实现            merge(li, low, mid, high)            low = high + 1            mid = low + i - 1            high = mid + i        else:  # 最后做一次            if mid < len(li)-1:  # 如果mid超出范围了，那么就没有1段有序的，就不需要做归并了                high = len(li)-1  # high的下标一定是数组最后一个元素                merge(li, low, mid, high)        print(li)        i *= 2    return liif __name__ == '__main__':    li = random.sample(range(10), 10)    print(li)    print(merge_sort(li))

和递归比较一下，明显递归简单，但是有点难理解。递归的逻辑是从大到小切，一层一层套，直到切到最小，然后再逐层合并。我是从小到大合上去。

小结-快速排序、堆排序、归并排序

时间复杂度：O(nlogn)

3种排序的时间复杂度都一样，一般情况下的运行时间是：快速排序 < 归并排序 < 堆排序3种排序算法的缺点：

• 快速排序：极端情况下排序效率低
• 归并排序：需要额外的内存开销
• 堆排序：速度是3种算法里相对较慢的

希尔排序

希尔排序是一种分组插入排序算法

1. 先取一个整数 d=n/2，将元素分为d个组，没组相邻元素之间的距离为d，在各组内进行插入排序
2. 再去一个整数 d=d/2，重复上面分组排序的过程，直到d=1
3. 最后做一个d=1的插入排序，就是标准的插入排序

希尔排序每趟并不是元素有序，而是整体数据越来越接近有序。最后一趟才使得所有的数据有序。代码如下：

def _insert_sort(li):    for i in range(1, len(li)):        tmp = li[i]        j = i - 1        while j >= 0 and li[j] > tmp:            li[j+1] = li[j]            j -= 1        li[j+1] = tmpdef shell_sort(li):    gap = len(li) // 2    while gap >= 1:        for i in range(gap, len(li)):            tmp = li[i]            j = i - gap            while j >= 0 and li[j] > tmp:                li[j+gap] = li[j]                j -= gap            li[j+gap] = tmp        gap //= 2    return li

上面贴了一下插入排序的算法做比较。希尔排序只是在插入排序的外面再加个循环，进行分组。做插入排序的时候，间隔不是1而是分组的大小gap。

时间复杂度：O((1+τ)n)

τ就是圆周率的大小，大概也就O(1.3n)，比O(nlogn)大。所以并不快，就没什么用了。

排序的稳定性

稳定性是一个概念，如果大小相同的两个元素在排序后其相对位置不发生变化，那么这个方法是稳定的。如果可能发生变化，那么这个方法称作是不稳定的。

如果要按多个维度进行排序，比如排序第一关键字是姓名，第二关键字是年龄。那么先做一个年龄的排序（稳定不稳定无所谓），然后再在原来的基础上做一个姓名的排序（必须稳定），就能得到正确的结果。快速排序，是不稳定的排序。这个最常用，但是不稳定。冒泡排序、归并排序，是稳定的排序

其他

其他和排序有有关的内容

计数排序

比如有100万个数要进行排序，但是每个数都是0到100之间的整数。这种情况数据很多，但是每条数据的值的范围是有限的，用下面的算法可以很快的做出来：

import randomdef count_sort(li, min_num, max_num):    # 先统计每个数出现的次数，计数    count = [0 for i in range(min_num, max_num+1)]    for num in li:        count[num] += 1    # 遍历上面列表，从小到大，每个数出现过几次就输出几次    i = 0    for num, m in enumerate(count):        for j in range(m):            li[i] = num            i += 1    return lidef create_li(min_num, max_num):    """生成计数排序用的列表"""    li = []    for i in range(100000):        li.append(random.randint(min_num, max_num))    return liif __name__ == '__main__':    li = create_li(0, 100)    print(li)    print(count_sort(li, 0, 100))

做2次O(n)的循环就出来了，时间复杂度是O(n)。但是有限制，就是必须是小范围的集合，并且依靠一个辅助数组，空间复杂度比较大。

内置模块-heapq

heapq模块，提供了基于堆的优先排序算法。

heappush(heap, item) ：往heap堆的最后加一个元素，然后是列表重新变成一个堆。（据我测试，应该是从最后一个父元素开始往上做调整，重新变成一个堆）heappop(heap) ：从堆里弹出一个元素（就是把堆顶的元素提出来，然后再做一次调成，变成堆）利用heapq模块实现堆排序：

import randomimport heapqdef heap_sort2(li):    h = []    for value in li:        heapq.heappush(h, value)    return [heapq.heappop(h) for i in range(len(h))]if __name__ == '__main__':    li = random.sample(range(10), 10)    print(li)    print(heap_sort2(li))

下面的两个方法，直接从ireable里取出n个最大或最小的元素。算法是用堆实现的：

nlargest(n, iterable)nlargest(n, iterable)

li = random.sample(range(10), 10)print(heapq.nlargest(5, li))print(heapq.nsmallest(5, li))