1.选择排序
选择排序是一种简答直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。不稳定，最好、最坏和平均时间复杂度都是O(n^2),空间复杂度为O(1)。
代码实现要点：两个for循环，外层循环控制排序的趟数，内层循环找到当前趟数的最大（小）值，随后与当前趟数组最（前）后的一位元素交换。
ef select_sort(lists):
count = len(lists)
for i in range(count):
min = i
for j in range(i+1,count):
if lists[min] > lists[j]:
min = j
lists[min],lists[i] = lists[i],lists[min]
return lists`2.插入排序
思路：将一个元素插入到已有序的数组中，在初始时未知是否存在有序的数据，因此将元素第一个元素看成是有序的。与有序的数组进行比较，比它大则直接放入，比它小则移动数组元素的位置，找到个合适的位置插入。当只有一个数时，则不需要插入了，因此需要n-1趟排序，比如10个数，需要9趟排序。时间复杂度：最好O(n)，最差和平均都是O(n^2)，空间复杂度为O(1)。
代码实现：一个for循环内嵌一个while循环实现，外层for循环控制需要排序的趟数，while循环找到合适的插入位置(并且插入的位置不能小于0)。
def insert_sort(lists):
count = len(lists)
for i in range(1,count):
key = lists[i]
j = i - 1
while j>=0:
if lists[j] > key:
lists[j+1] = lists[j]
lists[j] = key
j -= 1
return lists3.冒泡排序
思路：
俩俩交换，大的放在后面，第一次排序后最大值已在数组末尾。
因为俩俩交换，需要n-1趟排序，比如10个数，需要9趟排序
时间复杂度：最好O(n)，最差和平均都是O(n^2)，空间复杂度为O(1)。
代码实现要点：
两个for循环，外层循环控制排序的趟数，内层循环控制比较的次数
每趟过后，比较的次数都应该要减1
优化：如果一趟排序后也没有交换位置，那么该数组已有序～
def bubble_sort(lists):
for i in range(len(lists)-1):
for j in range(len(lists)-i-1):
if lists[j] > lists[j+1]:
lists[j],lists[j+1] = lists[j+1],lists[j]
return lists4.归并排序
归并排序是利用递归和分治技术将数据序列划分为越来越小的半子表，再对半子表排序，最后用递归步骤将排好序的半子表合并成为越来越大的有序序列。二路归并排序需要logn次，每一趟时间复杂度都是O(n)。时间复杂度最好、最坏和平均都是O(nlogn)，空间复杂度为O(1)。稳定的排序方法。
思路：
将两个已排好序的数组合并成一个有序的数组。
将元素分隔开来，看成是有序的数组，进行比较合并
不断拆分和合并，直到只有一个元素
代码实现：
在第一趟排序时实质是两个元素(看成是两个已有序的数组)来进行合并，不断执行这样的操作，最终数组有序
拆分左边，右边，合并...
def merge(left,right):
'''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
i, j = 0, 0
result = []
while i<len(left) and j<len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:] #将没有参与比较的（即左边中自动能得出结果比右边全大的数字）并入result
result += right[j:] #将没有参与比较的（即右边中自动能得出结果比右边全大的数字）并入result
return result
def merge_sort(lists):
if len(lists) <=1 :
return lists
# 二分分解
num = len(lists)//2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left,right)`5.快速排序
快速排序是一种非常高效的排序算法，采用“分而治之”的思想，把大的拆分为小的，小的拆分为更小的。原理为：在数组中找一个元素(节点)，比它小的放在节点的左边，比它大的放在节点右边。一趟下来，比节点小的在左边，比节点大的在右边。不断执行这个操作....
时间复杂度：最差O(n^2)，最好和平均都是O(nlogn)。快速排序过程中需要一个栈空间来实现递归，空间复杂度为O(logn)。
`def quick_sort(lists,left,right):
if left>=right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
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`6.希尔排序
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
时间复杂度最坏情况O(n^2) ，平均O(nlog(n))~O(n^2)，最好O(n^1.3) ，不稳定。
希尔增量一般是gap = gap // 2，只是比普通版插入排序多了这么一个for循环。
`def shell_sort(lists):
count = len(lists)
step = 2
group = count//step
while group > 0:
for i in range(group):
j = i + group
while j < count:
k = j - group
key = lists[j]
while k >= 0:
if lists[k] > key:
lists[k + group] = lists[k]
lists[k] = key
k -= group
j += group
group //=step
return lists`7.堆排序
思路：堆排序使用到了完全二叉树的一个特性，根节点比左孩子和右孩子都要大，完成一次建堆的操作实质上是比较根节点和左孩子、右孩子的大小，大的交换到根节点上，直至最大的节点在树顶
随后与数组最后一位元素进行交换......递归这一过程
首先将待排序的数组构造出一个大根堆
取出这个大根堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个大根堆
重复第二步，直到这个大根堆的长度为1，此时完成排序。
时间复杂度：O(nlogn)，空间复杂度为：O(1)。
代码实现：只要左子树或右子树大于当前根节点，则替换。替换后会导致下面的子树发生了变化，因此同样需要进行比较，直至各个节点实现父>子这么一个条件。
def adjust_heap(lists,i,size): # 调整列表中的元素并保证以i为根的堆是一个大顶堆
lchild = 2* i + 1 #i的左子节点位置
rchild = 2* i + 2 #i的右子节点位置
maxs = i
if i < size/2:
if lchild < size and lists[lchild] > lists[maxs]:
maxs = lchild
if rchild < size and lists[rchild] > lists[maxs]:
maxs = rchild
if maxs != i: # 如果做了堆调整则larger的值等于左节点或者右节点的值，这个时候做堆调整操作
lists[maxs], lists[i] = lists[i], lists[maxs]
adjust_heap(lists,maxs,size)
def bulid_heap(lists,size): # 构造一个堆，将堆中所有数据重新排序
for i in range(size//2)[::-1]: # 自底向上建堆
adjust_heap(lists,i,size)
def heap_sort(lists): # 将根节点取出与最后一位做对调，对前面len-1个节点继续进行堆调整过程。
size = len(lists)
bulid_heap(lists,size)
# 调整后列表的第一个元素就是这个列表中最大的元素，将其与最后一个元素交换，然后将剩余的列表再递归的调整为最大堆
for i in range(size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists,0,i)`8.基数排序
基数排序（radix sort）属于“分配式排序”，又称“桶子法”。将数字切割成个、十、百、千位放入到不同的桶子里，放一次就按桶子顺序回收一次，直至最大位数的数字放完～那么该数组就有序了。
时间复杂度为O(nlog(r)m)，其中r 为所采取的基数，而m 为堆数。
代码实现：
先找到数组的最大值，然后根据最大值/10来作为循环的条件(只要>0，那么就说明还有位数)
将个位、十位、...分配到桶子上，每分配一次就回收一次
import math
def radix_sort(lists,radix=10):
k = int(math.ceil(math.log(max(lists),radix))) #math.log返回参数的对数值；math.ceil小数进1。k表示要进行排序的次数，即最大数是的位数。
bucket = [[] for i in range(radix)] #用列表构建桶
for i in range(1,k+1):
for j in lists:
bucket[j//(radix**(i-1))%(radix**i)].append(j) #按照个/十位等依次将数据放入桶中
del lists[:]
for z in bucket:
lists += z #按照桶中数据的顺序放入列表中
return lists
