排序算法
几种常见的排序算法可以如下图概述
其中稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同
1、冒泡排序
重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来，越小的元素会经由交换慢慢”浮”到数列的顶端。
算法步骤
比较相邻的元素；如果第一个比第二个大，就交换他们两个；移动一位继续比较下一对元素，知道比较完随后一个元素，此时最后的元素会是最大的数。
针对上面比较过的元素重复以上的步骤，除了最后一个。
每次循环对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较。
def bubbleSort(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、 选择排序
选择排序每次循环找到未排序序列最小（最大）元素，将其放到已排序序列末尾。无论什么数据进去都是 O(n²) 的时间复杂度，数据规模越小越好，不占用额外的内存空间。
算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
def selectionSort(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
3 、插入排序
构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个素相等，则将待插入元素插入到相等元素的后面。）
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
4、 希尔排序
希尔排序（递减增量排序）是非稳定排序算法，基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
- 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序的基本思想是：希尔排序将整个序列看作是一个举证，分成m列，逐列进行排序。m从某个整数逐渐减为1，减到1时序列完全有序。
算法步骤
选择一个增量序列 t1，t2，……，tk，其中 t1 > t2 > t3 > … >tk, tk = 1；
将序列分为若干长度为ti的
行
，对每一
列
进行插入排序后合并为一行；
i=i+1继续执行上述操作，直到增量因子tk = 1时整个序列完全有序。
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
5、 归并排序
归并排序是采用分治法、递归的一个非常典型的应用。算法思想时不断将当前序列分为两个子序列（直到不能分割），再不断将两个子序列合并成为一个有序序列（直到最终只剩一个有序序列）。
算法步骤
首先将序列分为左右两个部分，循环至不能再分；
两个部分合并再一起进行排序，将左边部分进行备份，右边不需要，（也可以直接创建一个新空数组来放元素），设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复上一步骤直到某一指针达到序列尾，将另一序列剩下的所有元素直接复制到合并序列尾
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right)) #递归
def merge(left,right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0));
return result
6、 快速排序
快速排序同样采用分治法、递归法。在平均状况下，排序 n 个项目时间复杂度为 Ο(nlogn) 。在最坏状况下则需要 Ο(n2) ，但这种状况并不常见。且 O(nlogn) 记号中隐含的常数因子很小，比时间复杂度稳定等于 O(nlogn) 的归并排序要快很多。
算法步骤
从序列中选择一个轴点（pivot）元素（比如每次选择0位置为轴点元素）；
利用轴点元素将序列分为两个子序列，所有元素比轴点元素小的摆放在轴点元素前面，所有元素比轴点元素值大的摆在轴点元素的后面，相同的数可以到任一边；
对分开的两个子序列递归进行上述操作，直到子序列中只剩下1个元素，不能再分割
def quick_sort(alist, start, end):
if start >= end: # 递归的退出条件
return
mid = alist[start] # 设定起始的基准元素
low = start # low为序列左边在开始位置的由左向右移动的游标
high = end # high为序列右边末尾位置的由右向左移动的游标
while low < high:
# 如果low与high未重合，high(右边)指向的元素大于等于基准元素，则high向左移动
while low < high and alist[high] >= mid:
high -= 1
alist[low] = alist[high] # 走到此位置时high指向一个比基准元素小的元素,将high指向的元素放到low的位置上,此时high指向的位置空着,接下来移动low找到符合条件的元素放在此处
# 如果low与high未重合，low指向的元素比基准元素小，则low向右移动
while low < high and alist[low] < mid:
low += 1
alist[high] = alist[low] # 此时low指向一个比基准元素大的元素,将low指向的元素放到high空着的位置上,此时low指向的位置空着,之后进行下一次循环,将high找到符合条件的元素填到此处
# 退出循环后，low与high重合，此时所指位置为基准元素的正确位置,左边的元素都比基准元素小,右边的元素都比基准元素大
alist[low] = mid # 将基准元素放到该位置,
# 对基准元素左边的子序列进行快速排序
quick_sort(alist, start, low - 1) # start :0 low -1 原基准元素靠左边一位
# 对基准元素右边的子序列进行快速排序
quick_sort(alist, low + 1, end) # low+1 : 原基准元素靠右一位 end: 最后
7 、堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法，堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序，平均时间复杂度为 Ο(nlogn)。
算法步骤
堆序列进行原地建堆；
交换堆顶元素与尾元素，堆的元素数量减1，对0位置进行1次siftDown(向下筛选)操作；
重复上面步骤直至堆的元素数量为1.
def heap_sort(elems):
def siftdown(elems, e, begin, end): #向下筛选
i, j = begin, begin*2+1 #j为i的左子结点
while j < end:
if j+1 < end and elems[j] > elems[j+1]: #如果左子结点大于右子结点
j += 1 #则将j指向右子结点
if e < elems[j]: #j已经指向两个子结点中较小的位置，
break #如果插入元素e小于j位置的值，则为3者中最小的
elems[i] = elems[j] #能执行到这一步的话，说明j位置元素是三者中最小的，则将其上移到父结点位置
i, j = j, j*2+1 #更新i为被上移为父结点的原来的j的位置，更新j为更新后i位置的左子结点
elems[i] = e #如果e已经是某个子树3者中最小的元素，则将其赋给这个子树的父结点
#或者位置i已经更新到叶结点位置，则将e赋给这个叶结点。
end = len(elems)
for i in range(end//2-1, -1, -1): #构造堆序。
siftdown(elems, elems[i], i, end)
for i in range ((end-1), 0,-1): #进行堆排序.i最后一个值为1，不需要到0
print(elems)
e = elems[i] #将末尾元素赋给e
elems[i] = elems[0] #交换堆顶与最后一个元素
siftdown(elems, e, 0, i)
8 、计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n + k)。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
算法步骤
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对序列中所有的元素计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去。
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
9 、桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。在额外空间充足的情况下，尽量增大桶的数量；使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。
桶排序将[0,1)区间划分为n个相同的大小的子区间，这些子区间被称为桶。然后将n个输入元素分别放入各自的桶中。因为输入时均匀独立的，所以一般不会有很多数同时落在一个桶中的情况。这样，我们想对各个桶中的数据进行排序，然后遍历每个桶，按照次序把各个桶中的元素列出来即可。
10 、基数排序
基数排序一般用于长度相同的元素组成的数组。首先按照最低有效数字进行排序，然后由低位向高位进行，可以看做是进行多趟桶排序。如果是整数每个有效数字都在0-9之间，很适合桶排序，建10个桶很方便。
def radixSort():
for k in xrange(4): ``#4轮排序，4位数字
s=[[] for i in xrange(10)]
for i in A:
s[i/(10**k)%10].append(i)
A=[a for b in s for a in b]
return A