python不同排序算法的比较

1. 冒泡排序：相邻两个数相比较，如果大于则交换顺序，有序区在列表尾部

 　　代码实例：　　

def 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]

时间复杂度为O(N²)

如果遇到中途排序好而不发生变化的列表：[7,8,9,1,2,3,4,5,6]
改进方法：
def bubble_sort_better(li):
    for i in range(len(li)-1):
        andmark = 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]
                andmark = True
        if  not andmark:
            return

值需要进行三次冒泡即可

2. 选择排序：第i个和后续的元素一一对比，如果小于则交换位置，有序区在列表头部

　　代码实例：　

def select_sort(li):
    for i in range(len(li)-1):
        for j in range(i+1, len(li)):
            if li[i] > li[j]:
                li[i], li[j] = li[j], li[i]

时间复杂度O(N²)

创建新列表存放排序元素
def select_sort_new(li):
　　new_li = []
　　for i in range(len(li)):
　　　　min_li = min(li)　　　　 # 遍历一次li
　　　　new_li.append(min_li)
　　　　li.remove(min_li)　　　　# 遍历一次li
　　return new_li

缺点：创建新的列表，增加空间复杂度，时间复杂度为O(N³）

3. 插入排序：将后续的元素和有序区的元素从右往左比较，大于则不变，小于则插入

 　　代码示例：

def insert_sort(li):
    for i in range(1,len(li)):       　　 # i 为要插入元素的下标
        tem = li[i]                      # 保存插入元素的值
        j = i - 1                        # 插入元素的前一个元素
        while j >=0 and li[j]>tem:    　　# 当插入元素小于对比元素的时候，则将对比的元素后移
            li[j+1] = li[j]
            j -= 1                　　　　# 向比较的元素继续往前移动
        li[j+1] = tem          　　　　　　# 如果大于对比的元素，则插入后面
           
时间复杂度为O(N²)

4. 快速排序：将元素把列表分成左右大小两个部分

 　　代码示例：

def partion(li, left, right):
    tem = li[left]　　　　　　　　# 将左边的元素取出
    while left < right:　　　　　# 如果左边下标小于右边小标，保证中间存在元素
        while left < right and li[right] >= tem:　　
            right -= 1
        li[left] = li[right]　　# 将右边的的元素放到左边空位置上
        
        while left < right and li[left] <= tem:
            left += 1
        li[right] = li[left]
    li[left] = tem　　　　# 当左右指针相等时，则将原来的数放到这个空位置上
    return left　　　　　　# 返回这个分割的元素

# 递归
def quick_sort(li, left, right):
    if left < right：
        mid = partion(li, left, right)
        quick_sort(li, left, mid-1)
        quick_sort(li, mid+1, right)

quick_sort(li, 0, len(li)-1)

时间复杂度为O(NlogN)