主要介绍下几种排序算法，顺便复习一下：

1. 冒泡排序

①算法介绍：
对数据项两两相邻比较，通过N-1次循环后，得出结果

②算法代码：

def bubblesort(alist):
    flag = True
    len_list = len(alist)-1
    while flag and len_list:
        for x in range(len_list):
            if alist[x+1] < alist[x]:
                tmp = alist[x]
                alist[x] = alist[x+1]
                alist[x+1] = tmp
        len_list -= 1
    return alist

③算法分析：
算法过程需要N-1次循环，比对次数由N-1逐次降低至1，每次循环中发生数据项比对。比对次数总和为N^2/2-N/2, 即比对 时间复杂度O(N^2)

每次循环包括赋值与交换操作。交换时间复杂度：O(N^{2)：其中交换次数最少为0（顺序列表）;最差为每次比对都要交换值O(N}2)
（缺点：时间复杂度要求高）
无需额外空间去存储。只有一个tmp
（优点，空间复杂度要求低）

2. 选择排序

①算法介绍：
在每次循环中选择最大项位置，放入最后一项，进行N-1次循环

②算法代码：

def select_sort(alist):
    len_list = len(alist)-1
    for i in range(len_list, 0, -1):
        maxfix = 0
        for x in range(1, i+1):
            if alist[x] > alist[maxfix]:
                maxfix = x
        
        tmp = alist[i]
        alist[i] = alist[maxfix]
        alist[maxfix] = tmp
    
    return alist

③算法分析：
与冒泡排序相同，算法过程需要N-1次循环，比对次数由N-1逐次降低至1，每次循环中发生数据项比对。比对次数总和为N^2/2-N/2, 即比对时间复杂度仍是O(N^2)

每次循环包括赋值交换操作。相比冒泡，因为每次最多只涉及一次交换，时间复杂度仅为O(N)

无需额外空间去存储。只有一个tmp
（优点，空间复杂度要求低）

3. 插入排序

①算法介绍：
在每次循环中，将前面已排好序的列表项与第N项进行比对，找到插入合适的位置，完成排序。
②算法代码：

def insert_sort(alist):
    for i in range(1, len(alist)):
        pos = i
        val = alist[i]
        while pos > 0 and alist[pos-1] > val:
            alist[pos] = alist[pos-1]
            pos -= 1

        alist[pos] = val

③算法分析：
算法过程依旧需要N-1次循环，每次循环发生数据比对。
最差情况下每次循环 都需要 比对及插入 当前列表中 所有的数据项，时间复杂度为O(N^2)
最好情况下，即列表已是有序，只需要一次比对，时间复杂度为O(N)

但相比冒泡与选择排序，由于只有一次赋值，性能稍微优于前两者。但时间复杂度相同。

4. 谢尔排序

①算法介绍：
对列表间隔进行插入排序，循环每次间隔从N/2逐步降低间隔为1（1就是前面的插入排序），每次循环中，对每个数进行间隔排序。

②算法代码：

def shell_sort(alist):
    sublist = len(alist) // 2
    while sublist > 0:
        for start_pos in range(sublist):
            insert_sort(alist, start_pos, sublist)
            # 固定间隔后，间隔中的每一项的循环调用插入排序，起点从第一项开始，间隔sublist长度

        sublist = sublist // 2
        # 然后减小间隔，最终完成排序


def insert_sort(alist, start, gap):
    for i in range(start + gap, len(alist), gap):
        pos = i
        val = alist[i]

        while pos >= gap and alist[pos - gap] > val:
            alist[pos] = alist[pos - gap]
            pos -= gap

        alist[pos] = val

③算法分析：
可以减少很多插入排序中的无效比对，时间复杂度约为O(N^1.5)

5. 归并排序

①算法介绍：
将数据表分割为两个子列表，将子列表进行归并，子列表排好序后，并归并。
采用递归算法：

1. 基本结束条件为列表长度为1（列表不能再被分割）
2. 缩小规模（列表进行二分分割）
3. 调用自身（每次分割后的子列表再调用自身进行排序）

②算法代码：

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    # 循环结束条件

    half_len = len(alist) // 2
    left_list = merge_sort(alist[0:half_len])
    right_list = merge_sort(alist[half_len:])
    # 调用自身

    mergelist = []
    while left_list and right_list:
        if left_list[0] <= right_list[0]:
            mergelist.append(left_list.pop(0))
        else:
            mergelist.append(right_list.pop(0))
    mergelist.extend(left_list if left_list else right_list)
    # 子列表再排序融合

    return mergelist

③算法分析：
可分为两个部分：分裂与合并。
二分分裂，时间复杂度为O(logN)
合并，由于对子列表每一下进行对比，时间复杂度为O(N）
总体时间复杂度为O(NlogN)

注意到空间复杂度由于需要额外1倍的列表进行储存，所以空间复杂度较大。

6. 快速排序

①算法介绍：
通过设立一个中值，将列表中比中值大的，放在中值右边列表；比中值小的，放在中值左边列表。这样可以分为子列表，通过递归算法，得出最终结果。

image.png

②算法介绍：

def partition(alist, first, end):
    mid_val = alist[first]
    left_flag = first + 1
    right_flag = end
    done = False
    while not done:

        while left_flag <= right_flag and alist[left_flag] <= mid_val:
            left_flag += 1
        # 先设定左边标志，直到左边标志确定以后，再循环右边标志
        # 两个条件的位置不能反，因为left flag可以超过列表长度

        while right_flag >= left_flag and alist[right_flag] >= mid_val:
            right_flag -= 1
        # 等号防止出现左右标记指向同一个值，出现无限循环

        if left_flag > right_flag:
            done = True
        # 只有在左边标志小于右边标志的情况下才交换

        else:
            tmp = alist[left_flag]
            alist[left_flag] = alist[right_flag]
            alist[right_flag] = tmp

    tmp = alist[first]
    alist[first] = alist[right_flag]
    alist[right_flag] = tmp

    return right_flag


def quick__sort(alist, first, end):
    if first < end:
        # 循环结束条件

        mid_list = partition(alist, first, end)
        # 分割点确定

        quick__sort(alist, first, mid_list - 1)
        # 将分割点左边部分递归

        quick__sort(alist, mid_list + 1, end)
        # 分割点右边递归


def quick_sort(alist):
    quick__sort(alist, 0, len(alist) - 1)
    # 用两个函数的原因在于用一个函数，初始的起始值与末尾初始条件无法在递归中设定


alist = eval(input())
quick_sort(alist)
print(alist)

当然，如果不在乎空间复杂度的话，也可以写成如下格式：

def quick_sort(b):
    """快速排序"""
    if len(b) < 2:
        return b
    # 选取基准，随便选哪个都可以，选中间的便于理解
    mid = b[len(b) // 2]
    # 定义基准值左右两个数列
    left, right = [], []
    # 从原始数组中移除基准值
    b.remove(mid)
    for item in b:
        # 大于基准值放右边
        if item >= mid:
            right.append(item)
        else:
            # 小于基准值放左边
            left.append(item)
    # 使用迭代进行比较
    left_list = quick_sort(left)

    right_list = quick_sort(right)

    return left_list+[mid]+right_list

③算法分析：
算法过程包括分裂与移动；
如果中值能每次将列表分裂为相等的部分，分裂复杂度依旧为O(logN);
但如果中值选择偏离中间值，使得两边数据极为不对等，则分裂复杂度甚至可以达到O(N)

移动复杂度在于两边比较数据，由于每次移动中，都需要比较每项与中间值大小，所以复杂度为O(N);
总体复杂度为O(NlogN)~O(N^2)

另外可以不需要额外的存储空间