冒泡排序
思想
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端
操作
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
演示
bubble_sort.gif
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
选择排序
思想
选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。
操作
- 从未排列表中找到最大（小）值，放到已排列表首位
- 从剩余未排列表中找到最大（小）值，放到已排列表末尾
- 重复步骤2，直到所有元素都排好
注意：这只是思想，在实际操作的时候，考虑的空间复杂度的话，可以在一个列表上做这种操作
演示
select_sort.gif
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
插入排序
思想
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
操作
- 默认第一个元素放在已排列表
- 从剩余未排列表中找到第一个，按顺序插入已排列表
- 重复步骤2，直到所有元素都排好
注意：这只是思想，在实际操作的时候，考虑的空间复杂度的话，可以在一个列表上做这种操作
演示
insert_sort.gif
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
选择排序和插入排序听起来很像，但只要注意一个细节即可：选择排序在将满足条件的元素先选出来（遍历未排序列表），再放入到已排序列表中；插入排序是直接从未排序列表中拿一个元素，然后跟已排序列表的每个元素做比较（遍历已排序列表），再插入到合适的位置
快速排序
思想
采用分而治之的思想，将要排序的数据分成两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。
操作
- 从列表中选择一个基准元素，比之大的放到左边，反之右边。
- 分别对左右两部分执行步骤1
- 重复执行上述步骤，直到不可再分
演示
quick_sort.gif
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
