一、冒泡排序

1、从前往后相邻元素进行对比，如果前一个元素大于后一个元素则交换，将最大的元素“浮”到最后的位置上

2、再对前n-1个元素进行相同操作

3、持续对越来越少的元素进行相同操作，每一轮都选出当前的最大数，直到没有任何元素需要比较

优化：1、若某一轮没有进行任何交换，则说明已经有序，不需要再进行迭代，可以用一个标志来记录这一状态

　　　2、可以记录下每一轮最后一次进行交换的位置，这个位置后面的数据已经有序不需要再进行比较，因此可以确定下一轮的迭代范围

def bubble_sort(List):    n = len(List)    k = n    for i in range(n):        label = 1        for j in range(1,k):            if List[j-1]>List[j]:                List[j],List[j-1]=List[j-1],List[j]                k = j                label = 0        if label:            return List    return Lista = [8,7,6,5,4]print(bubble_sort(a))

二、选择排序

1、从未排序列表选出最小数，放入已排序列表第一位

2、再从剩余的未排序列表选出最小数，放入已排序列表末尾

3、以此类推，直到所有元素排序完毕

def selest_sort(List):    n = len(List)    for i in range(n):        min =i        for j in range(i,n):            if List[j]

三、插入排序

对每个未排序的数据，在已排序数据中从后向前扫描，寻找相应位置并插入

1、从第一个元素开始，看作已排序数据

2、取出下一个元素，从后向前扫描已排序数据，寻找插入位置

3、以此类推，直到所有数据都有序

def insert_sort(List):    n = len(List)    for i in range(1,n):        temp = List[i]        index = i        for j in range(i,-1,-1):            if List[j]>temp:                List[j+1] = List[j]                index = j        List[index] = temp    return Lista = [8,7,6,5,4]print(insert_sort(a))

四、希尔排序

希尔排序又称增量递减排序，是一种高级的插入排序算法

1、首先将列表以step=n//2为步长进行划分，对每个分组进行插入排序

2、将步长缩小至step= step//2，再进行插入排序

3、直到步长缩减为1，进行最后一次插入排序

def shell_sort(List):    n = len(List)    step = n//2    while step>=1:        for i in range(step,n):            while i>=step and List[i-step]>List[i]:                List[i-step],List[i]=List[i],List[i-step]                i = i -step        step = step//2    return Lista = [8,7,6,5,4]print(shell_sort(a))

五、快速排序

插入排序采用分治法的思想，先确定一个基准数，然后将小于等于基准数的放到左边，大于基准数的放大右边

再对左右分区分别重复上述步骤，直到每个分区只剩下一个数

def quick_sort(List):    return qsort(List,0,len(List)-1)def qsort(List,left,right):    if left>=right:        return List    base = List[left]    l = left    r = right    while l
     
      = base and l
     

六、归并排序

归并排序同样采用分治法的思想，首先递归对列表进行分解，再递归进行合并

合并的时候，比较两个列表的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个列表为空，最后把另一个列表的剩余部分复制过来即可。

def merge_sort(List):    if len(List)<=1:        return List    n = len(List)    num = n//2    left = merge_sort(List[:num])    right = merge_sort(List[num:])    return merge(left,right)def merge(left,right):    l = 0    r = 0    result = []    while l