前言
排序有内部排序和外部排序之分，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
一、交换排序(一)：冒泡排序
解析：
第1轮，从(0,n)遍历，找出第1小的数，放在第1位
第2轮，从(1,n)遍历，找出第2小的数，放在第2位
核心思想：每一循环，都能找到基准位置对应的数(第1小，第2小)。
def bubbling_sor(orgin_list):
length = len(orgin_list)
temp = 0
# 从list[0]开始遍历，进行外循环，list[i]作为基准位置比较数
for i in range(length):
# 用之后的数值与基准位置的数进行比较，进行内循环
for j in range(i+1,length):
# 如果基准位置之后的数，比基准位置更小，就进行替换，这样一轮内循环，都能保证基准位置的数比其后面的数值更大
if orgin_list[i] > orgin_list[j]:
orgin_list[i],orgin_list[j] = orgin_list[j],orgin_list[i]
return orgin_list
二、交换排序(二)：快速排序(填坑排序、分治排序)
快速排序是冒泡排序的一种优化，先用填坑法将数组进行分割，左边小于基准数，右边全部大于基准数，再用分治法分别递归，
1、将A[0]，作为基准数，挖走到temp中，A[0]现在为坑
2、从右到左扫，找到第一个比基准数小的位置j，将这个位置的数A[j]放到A[0]，此时A[j]留坑
3、从A[1]，开始从左向右扫，找到第一个比基准数的位置i，将这个数A[i]放到A[j]，此时A[i]留坑
4、重复2、3步骤，一直到i,j会合。将temp放入a[i]，这样i左边的数就比A[i]小，右边比A[i]大
5、对左边和右边分别进行递归。
def quick_sort(A,left,right):
if left < right:
i = left
j = right
temp = A[left] # 将第一个数作为基准数，存入temp,同时基准位置就留坑了
while i < j:
# 从右向前扫，找到小于基准数的值，将其放入坑中，再次留出一个坑
while (A[j] > temp and i<j):
j -= 1
if i < j:
A[i] = A[j]
i += 1
# 从前往后扫，找到大于基准数的值，将其放入上一个坑，从而留出一个坑
while (A[i] < temp and i< j):
i += 1
if i < j:
A[j] = A[i]
j -= 1
A[i] = temp # 将最开始挖出来的数填入坑中，至此，i左边的数就小于i,i右边的数都大于i.
# 大小分离结束
# 分治开始，递归排序
quick_sort(A,left,i-1)
quick_sort(A,i+1,right)
return A
if __name__ == "__main__":
orgin = [5, 3, 4, 2, 7, 4, 6, 8]
quick_sort(orgin,0,len(orgin)-1)
三、插入排序(一)：直接插入排序
基本思想：将待排序的无序数列看成是一个仅含有一个元素的有序数列和一个无序数列，将无序数列中的元素逐次插入到有序数列中，从而获得最终的有序数列。
def insert_sort(orgin_list):
length = len(orgin_list)
# 从list[0]开始遍历，进行外循环，list[i]作为基准位置比较数
for i in range(length-1):
# 拿有序的数组之后的一个数，往里面插
for j in range(i+1,0,-1):
if orgin_list[j] > orgin_list[j-1]:
break
orgin_list[j], orgin_list[j-1] = orgin_list[j-1], orgin_list[j]
return orgin_list
四、插入排序(二)：希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
def shellSort(nums):
# 设定步长
step = len(nums)/2
while step > 0:
for i in range(step, len(nums)):
# 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
while i >= step and nums[i-step] > nums[i]:
nums[i], nums[i-step] = nums[i-step], nums[i]
i -= step
step = step/2
return nums
五、选择排序(一)：简单选择排序
基本思想：在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
def select_sort(orgin_list):
length = len(orgin_list)
# 从list[0]开始遍历，进行外循环，list[i]作为基准位置比较数
for i in range(length-1):
mi = i
for j in range(i,length):
#找到最小的一个数的位置
if orgin_list[j] < orgin_list[mi]:
mi = j
orgin_list[mi],orgin_list[i] = orgin_list[i],orgin_list[mi]
return orgin_list
六、选择排序(二)：堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
def adjust_heap(lists, i, size):
lchild = 2 * i + 1
rchild = 2 * i + 2
max = i
if i < size / 2:
if lchild < size and lists[lchild] > lists[max]:
max = lchild
if rchild < size and lists[rchild] > lists[max]:
max = rchild
if max != i:
lists[max], lists[i] = lists[i], lists[max]
adjust_heap(lists, max, size)
def build_heap(lists, size):
for i in range(0, (size/2))[::-1]:
adjust_heap(lists, i, size)
def heap_sort(lists):
size = len(lists)
build_heap(lists, size)
for i in range(0, size)[::-1]:
lists[0], lists[i] = lists[i], lists[0]
adjust_heap(lists, 0, i)
七、归并排序
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
八、基数排序(桶排序)
是将数列分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间O(n)。但桶排序并不是比较排序，不受到O(n*log n)下限的影响。