目录

1.冒泡排序
2.选择排序
3.插入排序
4.堆排序
5.归并排序
6.快速排序
7.希尔排序

一个比较：比快多少？
假设n=100000; =;=1660964;前者约是后者的6000倍；约等于一分钟和4天的比例；
这个比较是为了说明两种复杂度算法的差异之大；更说明了学习更有效率算法的必要性

排序算法可针对数字类型，字符，或者更高级的类型进行排序，算法逻辑都是一样的仅仅比较逻辑做策略模式替换即可。
以下所有代码案例，仅进行数字类型排序

一，冒泡排序

原理：遍历数列，每个过程，比较当前值与下一位置的值，通过交换位置，将较大的数置后；像冒泡一样
总的比较次数为（n-1）+（n-2）+…+1≈。复杂度为

# code utf-8
def up_sort(lis:list, n:int):
    for i in range(n):
        for j in range(0, n-i-1):
            if lis[j] < lis[j+1]:
               lis[j], lis[j+1] = lis[j+1], lis[j]
               print(lis) # 通过这一行打印排序步骤，直接看到冒泡效果

a = [i for i in range(10)]
a.reverse()

print(a)  # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
up_sort(a, len(a))
print(a)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

二，选择排序

原理：从左至右（or从上到下）遍历，寻找遍历最小值，放在数列最左端；递归；
总的比较次数为（n-1）+（n-2）+…+1≈。复杂度为

# code utf-8
def selec_sort(lis:list, n:int):
    for i in range(n):
        # 寻找i~n区间的最小值
        min_index = i
        for j in range(i+1, n):
            if lis[j] < lis[min_index]:
                min_index = j
        # swap函数交换位置，如果是C++ 11以上版本，std中即包含swap
        lis[i], lis[min_index] = lis[min_index], lis[i]

a = [i for i in range(10)]
a.reverse()

print(a)  # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
selec_sort(a, len(a))
print(a)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

三，插入排序（✳️ 有应用价值）

插入排序，是优化版的冒泡排序，在于提前终止循环，节省资源；排序目标有序性越高，插入排序的性能就越优于冒泡和选择
原理：从左至右（or从上到下）遍历，将当前值，插入到左端已排序序列的合适位置；
总的比较次数为（n-1）+（n-2）+…+1≈。复杂度为
对于完全有序的数组，插入排序的复杂度为

# code utf-8
# 方法一：根据自己的理解写的，把握好index的理解，否则容易出错
def insert_sort(lis:list, n:int):   # 
    for i in range(1,n): # 最左侧第一个数字不用排序，默认是已排序列
        for j in range(0, i):
            if lis[i] < lis[j]:
                a = lis[i]
                lis.remove(lis[i])
                lis.insert(j, a)
                break
        print(lis)

# 方法二：根据某教程
def insert_sort(lis:list, n:int):   # 借鉴
    for i in range(1,n): # 最左侧第一个数字不用排序，默认是已排序列
        for j in range(i, 0, -1):
            if lis[j] < lis[j-1]:
                lis[j], lis[j-1] = lis[j-1], lis[j]
            else:
                break
        print(lis)

# 方法三，优化
def insert_sort(lis:list, n:int):
    for i in range(1,n): # 最左侧第一个数字不用排序，默认是已排序列
        temp = lis[i]
        target_index = i
        for j in range(i, 0, -1):
            if temp < lis[j-1]:
                lis[j] = lis[j-1] # 赋值代替交换
                target_index = j - 1 # 当前位置
            else:
                break
        lis[target_index] = temp
        print(lis)

a = [4,7,2,8,3,9,1,6,0]
if __name__ == "__main__":
    insert_sort(a, len(a))

按照原理和代码的说明，可以看到，插入排序在迭代次数上，比较次数上，都要少于冒泡和选择排序；
问题：但是实际测试运行时间，会发现选择排序 优于 插入排序 优于 冒泡排序
原因：这是因为，选择排序比较计算多，但是交换位置操作少，而插入排序和冒泡排序存在大量数组元素位置交换，操作内存的IO时间开销是很大的；

优化思路：
1，使用方法一，只交换一次，（效率未测试）
2，使用方法三，通过赋值替代交换；此方法同样可用于优化冒泡排序（这样优化后，冒泡排序就变成了选择排序）

四，堆排序

略

五，归并排序一：自顶向下递归（先分组，后merge）（合并排序 merge_sort）

原理：将排序序列分半，两组排序后再合并成有序序列。递归。
实现：上的细节就是：将序列无限二分，最终分为每组两个元素的很多小组，小组内排序后，两个a级别小组合并排序为b界别，两个b级别再继续合并排序，直至合为一个有序的序列。
复杂度分析：由于是二分法分组，如果总元素是N个，那么序列分裂行为次数（即递归层数）级别的

核心算法->合并两组有序序列逻辑：例如要归并[4,6]，[3,7]两个小组；
1，首先创建一个新的空数组lis_new
2，比较两个序列首位，然后将较小的推入lis_new中。递归。
3，关键点：三个索引，两个待合并小组当前值的索引和新数组的索引(通过比较，赋值，移动索引，而不是删除小组内容，推入新数组这种有更大IO开销的操作)
合并两组序列的复杂度与序列元素个数有关，很简单这个算法是的。
结合上面归并算法的理解，归并算法有两部分，分裂：复杂度，合并：复杂度;
所以归并排序的复杂度是的

归并排序的缺点：占用内存大，典型的空间换时间

以下代码是我根据理解和参考自己实现的，虽然完成了示例中的排序，不保证完全正确。

# code utf-8
import math

def merge_lis(lis, i, j, mid):
    arr1 = [item for item in lis]
    index1, index2 = i, mid+1
    for k in range(j-i+1):
        if index1>mid:
            lis[k+i] = arr1[index2]
            index2 += 1
        elif index2>j:
            lis[k+i] = arr1[index1]
            index1 += 1
        elif arr1[index1] < arr1[index2]:
            lis[k+i] = arr1[index1]
            index1 += 1
        else:
            lis[k+i] = arr1[index2]
            index2 += 1

    print(lis)

def merge_sort(lis:list, n:int):
    def split(lis:list, i:int, j:int): # 要处理的数据段的开始位置，结束位置；前闭后闭
        if (i >= j):
            return
        # 第一步：数组二分
        mid = math.floor((i+j)/2)  # 存在数据过大，溢出风险;向上取整
        split(lis, i, mid)
        split(lis, mid+1, j)
        # 第二步：merge两段，排序核心
        merge_lis(lis, i, j, mid)

    split(lis, 0, n-1)

a = [4,7,2,8,3,9,1,6,0]
if __name__ == "__main__":
    merge_sort(a, len(a))

思考：对于近乎有序的数组，归并排序与插入排序效率比较如何？答案是插入排序更快，大概是倍，这从两者的复杂度上就能计算得出，因为对于近乎有序的数组，优化后的插入排序，复杂度是接近的。
优化：
方法一：判断。同样的，对于归并排序优化后，对于近乎有序的数组，也可以是接近复杂度的，优化方法，仅需增加一行代码；如下代码示例 （提升效率数十倍，当n=50000）
方法二：结合。当归并递归到底的时候（分组足够小的时候，比如每组元素少于10个），此时可使用插入排序来提高性能。（提升效率一倍，当n=50000）

# 只需在上面的程序基础上，增加一行；仅对于无序的进行归并，有序的不归并
if lis[mid] > lis[mid+1]:  
     merge_lis(lis, i, j, mid)

五，归并排序二（自底向上，迭代）

原理不变，优化方式相同；仅逻辑相反；

#此部分由于python的循环语法限制，不易实现，后面补C++实现

六，快速排序

原理：随机选一个数作为基准；将其余的数字与基准比较，分为比基准大和比基准小的两组；递归即可。
。平均复杂度为，如果运气较差，每次都选最小值为基准，复杂度为，本质同选择排序
关键：如何分出两组，并找出基准值的合理索引值。

1，基础版(效率即优于归并)

# 第一版，原理实现
def partation(lis, start, end):
    p = lis[start]
    p_index = start
    for i in range(start+1, end+1):
        if lis[i] < p:
            lis[i], lis[p_index+1] = lis[p_index+1], lis[i]# 较小的数swap到前面
            p_index += 1 # 记录正确索引位置
    lis[start], lis[p_index] = lis[p_index], lis[start]
    return p_index

def _quick_s(lis, start, end):
    if start > end:
        return
    index = partation(lis, start, end)  # 选择基准值，以基准值分组，并返回基准值索引
    _quick_s(lis, start, index-1)
    _quick_s(lis, index+1, end)

def quick_sort(lis:list, n:int):
    _quick_s(lis, 0, n-1)
    pass

a = [4,7,2,8,3,9,1,6,0]
if __name__ == "__main__":
    quick_sort(a, len(a))
    print(a)

问题：
优化：
2，随机化，双路，三路
3，其他问题

六，希尔排序（高级插入排序）

原理：
复杂度为