前言：去年找工作时整理的，没想到这么快又要拿来用

冒泡排序

复杂度：N^2

遍历列表
每次比较相邻元素大小，
if list[i]> list[i+1]：交换元素位置
继续遍历

修改后：识别排序列表和停止的优点
短冒泡排序：加入判断，若某次遍历没有交换，则排序完成

选择排序

复杂度N^2
改进冒泡：相比之减少了交换次数

每次遍历只寻找**最大值**，然后放置在正确的位置

插入排序

N^2，最好的情况下只有N，
基准研究中，插入排序有非常好的性能

在列表较低位置形成有序列表
遍历时插入新的项进入，形成新的有序列表

希尔排序

N~ N^2之间
特点：增量i的选择
若i选择1，则是标准插入排序

对i个子列表进行插入排序
合并i个子列表，进行一次插入排序

归并排序 merge sort

复杂度NLogN，需要额外空间

思路：
1. 二分列表，直到不可拆分；if len(list) >1；logN
2. 对两半排序完成，就执行合并的操作；递归调用merge sort； N
注意:在python里，切片O（K），所以运算需要删除slice运算符

快速排序

NlogN，不需要额外空间
最坏N^2: 如果分割点不在列表中间附近

找pivot值，一般选定mid
拆分成left, mid, right 列表（递归）
最后合并列表

堆排序

NlogN，空间O(1)
相比快排，heap sort “make poor use of cache memory"，不适合较少的元素排序
知道概念大根堆（大顶堆）、小根堆（小顶堆）
1，L(i) <= L(2i)且L(i) <= L(2i+1) 即双亲节点都小于孩子节点
2，L(i) >= L(2i)且L(i) >= L(2i+1) 其中i属于[1, n/2]，双亲节点都大于孩子节点

思路：
初始化堆：从子节点比较较大的子节点，与父节点交换
将堆顶元素输出：堆顶元素与堆底元素（最后一个元素）交换，重新调整堆

时间复杂度：向下调整的时间与树高有关，为O(h)。可以证明在元素个数为n的序列上建堆，其时间复杂度为O(n)。之后还有n-1次向下调整操作，每次调整的时间为O(h)=O(logN)，故在最好，最坏和平均情况下，堆排序的时间复杂度为O(nlogn)。

空间复杂度：仅使用了常数个辅助单元，空间复杂度为O(1)。

参考： 堆排序
https://www.cnblogs.com/wangchaowei/p/8288216.html--# 数据结构——堆（Heap）大根堆、小根堆

(待)！！！侏儒排序

def gnomesort(seq):
    i = 0
    while i < len(seq):
        if i == 0 or seq[i-1] < = seq[i]:
            i += 1
        else:
            seq[i], seq[i-1] = seq[i-1] ,seq[i]
            i - = 1

image.png

image.png

？？？堆排序时间复杂度稳定