1.插入排序
步骤
1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一位置
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置中
6、重复步骤2
'''
插入排序
步骤：
1、从第一个元素开始，该元素可以认为已经被排序
2、取出下一个元素，在已经排序的元素序列中从后向前扫描
3、如果该元素（已排序）大于新元素，将该元素移到下一位置
4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5、将新元素插入到该位置中
6、重复步骤2
'''
def insertion_sort(list):
iter_len = len(list)
if iter_len < 2:
return list
for i in range(1, iter_len):
key = list[i]
j = i - 1
while j >= 0 and list[j] > key:
list[j + 1] = list[j]
j -= 1
list[j + 1] = key
return list
2.归并排序
将一组无序数按n/2递归分解成只有一个元素的子项，然后将这些有序的子元素进行合并。
步骤
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
'''
归并排序
步骤：
将一组无序数按n/2递归分解成只有一个元素的子项，然后将这些有序的子元素进行合并。
1、申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
'''
def merge(nums, first, middle, last):
# 切片边界,左闭右开并且是了0为开始
left = nums[first:middle + 1]
right = nums[middle + 1:last + 1]
for i in range(first, last + 1):
if len(left) > 0 and len(right) > 0:
if left[0] <= right[0]:
nums[i] = left.pop(0)
else:
nums[i] = right.pop(0)
elif len(right) == 0:
nums[i] = left.pop(0)
elif len(left) == 0:
nums[i] = right.pop(0)
def merge_sort(nums, first, last):
''''' merge sort
merge_sort函数中传递的是下标，不是元素个数
'''
if first < last:
middle = int((first + last) / 2)
merge_sort(nums, first, middle)
merge_sort(nums, middle + 1, last)
merge(nums, first, middle, last)
return nums
3.选择排序
步骤：
1、首先在未排序序列中找到最小元素，存放到排序序列的起始位置，
2、然后，再从剩余未排序元素中继续寻找最小元素，
3、然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
'''
选择排序
步骤：
它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，
然后，再从剩余未排序元素中继续寻找最小元素，
然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
'''
def select_sort(a):
''''' 选择排序
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，
顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法。
'''
a_len = len(a)
for i in range(a_len): # 在0-n-1上依次选择相应大小的元素
min_index = i # 记录最小元素的下标
for j in range(i + 1, a_len): # 查找最小值
if (a[j] < a[min_index]):
min_index = j
if min_index != i: # 找到最小元素进行交换
a[i], a[min_index] = a[min_index], a[i]
return a
4.冒泡排序
步骤
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
'''
冒泡排序
步骤
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
'''
def bubble_sort(lists):
# 冒泡排序
count = len(lists)
for i in range(0, count):
for j in range(i + 1, count):
if lists[i] > lists[j]:
lists[i], lists[j] = lists[j], lists[i]
return lists
5.快速排序
快速排序算法和合并排序算法一样，也是基于分治模式。对子数组A[p…r]快速排序的分治过程的三个步骤为：
1、分解：把数组A[p…r]分为A[p…q-1]与A[q+1…r]两部分，其中A[p…q-1]中的每个元素都小于等于A[q]而A[q+1…r]中的每个元素都大于等于A[q]；
2、解决：通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序；
3、合并：因为两个子数组是就地排序的，所以不需要额外的操作。
对于划分partition每一轮迭代的开始，x=A[r],对于任何数组下标k，有：
1)如果p≤k≤i，则A[k]≤x。
2)如果i+1≤k≤j-1，则A[k]>x。
3)如果k=r，则A[k]=x。
'''
快速排序
快速排序算法和合并排序算法一样，也是基于分治模式。对子数组A[p…r]快速排序的分治过程的三个步骤为：
分解：把数组A[p…r]分为A[p…q-1]与A[q+1…r]两部分，其中A[p…q-1]中的每个元素都小于等于A[q]而A[q+1…r]中的每个元素都大于等于A[q]；
解决：通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序；
合并：因为两个子数组是就地排序的，所以不需要额外的操作。
对于划分partition 每一轮迭代的开始，x=A[r], 对于任何数组下标k，有：
1) 如果p≤k≤i，则A[k]≤x。
2) 如果i+1≤k≤j-1，则A[k]>x。
3) 如果k=r，则A[k]=x。
'''
def quick_sort(lists, left, right):
# 快速排序
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
# 必须是lists[right] >= key, 否则left和right会停在一个位置重复循环
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
# 这里不能是lists[left] <= key, 否则会出现left超出lst范围的情况
while left < right and lists[left] < key:
left += 1
lists[right] = lists[left]
# 递归
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists