文章概述
介绍各大常用经典的排序算法和效率，以及python实现
常用算法（冒泡排序，选择排序，快速排序，插入排序）
冒泡排序
介绍：冒泡排序算法思想比较简单，对要排序的列表，从第一个元素起，依次比较相邻两个元素，如果顺序不对，就交换，直到最小（大）元素“冒”出来。时间复杂度 O(n²)
算法描述：
- 依次比较相邻元素，如果第一个比第二个大，就交换位置，直到最后一个元素比较过后，最后一个元素就是最大值
- 重复执行步骤1，除了最后一个元素
- 重复执行上述步骤
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²)
算法描述：
- 从未排列表中找到最大（小）值，放到已排列表首位
- 从剩余未排列表中找到最大（小）值，放到已排列表末尾
- 重复步骤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
- 重复执行上述步骤，直到不可再分
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²)
算法描述：
- 默认第一个元素放在已排列表
- 从剩余未排列表中找到第一个，按顺序插入已排列表
- 重复步骤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
