文章概述

介绍各大常用经典的排序算法和效率，以及python实现
常用算法（冒泡排序，选择排序，快速排序，插入排序）

冒泡排序

介绍：冒泡排序算法思想比较简单，对要排序的列表，从第一个元素起，依次比较相邻两个元素，如果顺序不对，就交换，直到最小（大）元素“冒”出来。时间复杂度 O(n²)

算法描述：

1. 依次比较相邻元素，如果第一个比第二个大，就交换位置，直到最后一个元素比较过后，最后一个元素就是最大值
2. 重复执行步骤1，除了最后一个元素
3. 重复执行上述步骤
   python实现：

def bubble_sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

选择排序

介绍：从未排列表中找到最值，顺序放到已排列表中。时间复杂度 O(n²)

算法描述：

1. 从未排列表中找到最大（小）值，放到已排列表首位
2. 从剩余未排列表中找到最大（小）值，放到已排列表末尾
3. 重复步骤2，直到所有元素都排好
   python实现：

def selection_sort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

快速排序

介绍：采用分而治之的思想，将要排序的数据分成两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。
。时间复杂度 O(nlog2n)

算法描述：

1. 从列表中选择一个基准元素，比之大的放到左边，反之右边。
2. 分别对左右两部分执行步骤1
3. 重复执行上述步骤，直到不可再分
   python实现：

def quick_sort(data):    
    """快速排序"""    
    if len(data) >= 2:  # 递归入口及出口        
        mid = data[len(data)//2]  # 选取基准值，也可以选取第一个或最后一个元素        
        left, right = [], []  # 定义基准值左右两侧的列表        
        data.remove(mid)  # 从原始数组中移除基准值        
        for num in data:            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num)        
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data

插入排序

介绍： 默认第一个元素为已排，剩余元素依次顺序插入已排列表。时间复杂度 O(n²)

算法描述：

1. 默认第一个元素放在已排列表
2. 从剩余未排列表中找到第一个，按顺序插入已排列表
3. 重复步骤2，直到所有元素都排好
   python实现：

def insert_sort(l):    
    """插入排序"""    
    length = len(l)
    for i in range(1,length):                   #默认第一个元素已经在有序序列中，从后面元素开始插入    
        for j in range(i,0,-1):                 #逆向遍历比较，交换位置实现插入        
            if l[j] < l[j-1]:            
                l[j],l[j-1] = l[j-1],l[j]
    return l