排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
内部排序的分类：
一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，快速排序，插入排序，希尔排序，归并排序，堆排序等。
另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。
常见排序算法的一些特性：
冒泡排序
通过上面的动图也可以看出来，冒泡通过两重循环遍历每一个数后将最大的’冒’出去
冒泡是相邻元素之间的比较，每次把最大的’冒’出去
由于需要经过两重循环，所以时间复杂度为： O(n2)
选择排序
选择排序相比冒泡排序不稳定，时间复杂度也是。
选择排序没趟都会产生最小值，它不是相邻元素的比较而是在该元素设置一个索引 i 。
然后与数组的其他元素依次比较（除了上一个索引值），直到找到小于该元素（索引
接着继续从 i 索引（此时已经不是原来的数值）值与索引
冒泡是相邻元素比较，选择不是相邻元素比较
选择排序是把最小的选出来
快速排序
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于最终它应该在的地方。
(3) 递归地把”基准值前面的子数列”和”基准值后面的子数列”进行排序。
快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
假设有如下数组，将两个哨兵设在左右端，最左端的值为基准
1.右边向左运动，直到找到一个比基准小的数
2.左边向右运动，直到找到一个比基准大的数
3.交换两个数
4.如果两个哨兵不相遇，则继续上述步骤
5.相遇之后和基准交换
这样‘6’就永远在它最终应该待的地方了，对6的前一半和后一半进行上述完整操作即可（递归）
参考文献：
/art/03/430986.htm
插入排序
(1) 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
(2) 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
(3) i++并重复第二步直到i==n-1。排序完成。
直接插入排序的时间复杂度是 O(n2)
希尔排序
是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。分组的插入排序
先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
如排序数据为[ 5 9 7 2 3 1 6 ]，那么数据长度为7
第一次分割 gap=7/2=3
i和j之间总是间隔gap个单位，其中j从gap遍历到数据中的最后一个数，j=i-gap
如上图，最后一次交换时 j−gap>=0 ，但在这里没有什么影响，下面将看出使用 j−gap 的作用
第二次分割 gap=3/2=1
当分割的间隔是1的时候，首先交换前两个的值，当j和i分别移到3和1的时候，首先交换，因为3>1，然后应该往前迭代，即 j−=gap ，否则的话我们只比较了3和1，而实际上最前面的2也是大于1的，也应该交换。
如此往复，我们就会得到最终的排序结果。
归并排序
是分治法的一种，上图可以清晰的描述排序过程
先拆分（递归），后合并
效率为 O(n log n)
Python的实现
'''冒泡排序重复走访过要排序的序列，一次比较两个元素，如果他们的顺序错误就将他们进行交换，一次冒上来的是最小的，其次是第二小。时间复杂度：O(n^2)空间复杂度:O(1)稳定性：稳定'''def BubbleSort(data):for i in range(len(data)):for j in range(len(data)-i-1):if data[j]>data[j+1]:data[j+1] , data[j] = data[j] , data[j+1]'''选择排序选择排序相比冒泡排序不稳定，时间复杂度也是。选择排序没趟都会产生最小值，它不是相邻元素的比较而是在该元素设置一个索引i。然后与数组的其他元素依次比较（除了上一个索引值），直到找到小于该元素（索引j）时交换两元素，接着继续从i索引（此时已经不是原来的数值）值与索引j+1值比较。重复上述比较过程……简单的原理图如下：冒泡是相邻元素比较，选择不是相邻元素比较'''def SelectionSort(data):for i in range(len(data)):for j in range(i+1,len(data)):if data[j]<data[i]:data[i] , data[j] = data[j] , data[i]'''快速排序快速排序流程：(1) 从数列中挑出一个基准值。(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于最终它应该在的地方。(3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序。快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。'''def QuickSort(lists, left, right):# 快速排序if left >= right:return listskey =leftlow = lefthigh = rightwhile left < right:while left < right and lists[right] >= lists[key]:#如果右边比基准小，停下right -= 1while left < right and lists[left] <= lists[key]:#如果左边比基准大，停下left += 1lists[right],lists[left]=lists[left],lists[right]#交换现在的左右值lists[right] ,lists[key]=lists[key],lists[right] #left和right汇合后和基准交换print_data(data)#交换过程QuickSort(lists, low, left - 1)QuickSort(lists, left + 1, high)return lists'''直接插入排序1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=12. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。3. i++并重复第二步直到i==n-1。排序完成。直接插入排序的时间复杂度是O(N2)。假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。'''def InsertionSort(data):for i in range(1,len(data)):key=data[i]j=i-1while j>=0:if data[j]>key:data[j+1]=data[j]data[j]=keyj-=1'''希尔排序是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。分组的插入排序j-=gap第一次交换数据后，看它是后面的数否还小于前面的数如2 3 1 5 9 6这个序列以1位步长的话一次交换后2 1 3 5 9 6此时j指向第二个数，i指向第三个数 所以交换后应该用j-gap往前查看是否前面的更小'''def ShellSort(data):gap=int(len(data)/2) #排序的分组while gap>0:for i in range(gap,len(data)):j=i-gapwhile data[j]>data[i] and j >=0:data[j],data[i]=data[i],data[j]j-=gapi-=gapgap=int(gap/2)'''归并排序先拆分，后合并'''def MergeSort(ls):if len(ls)<2:return lsmid = len(ls) >> 1 #相当于除2取整left = MergeSort(ls[:mid])right = MergeSort(ls[mid:])return merge(left,right)def merge(left, right):result = []i, j = 0, 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result += left[i:]result += right[j:]return result'''打印函数'''def print_data(data):for i in data:print(i,end=' ')print() '''测试代码'''data=[5,9,7,2,3,1,6]BubbleSort(data)print_data(data)data=[5,9,7,2,3,1,6]SelectionSort(data)print_data(data)data=[5,9,7,2,3,1,6]QuickSort(data,0,6)print_data(data)data=[5,9,7,2,3,1,6]InsertionSort(data)print_data(data)data=[5,9,7,2,3,1,6]ShellSort(data)print_data(data)data=[5,9,7,2,3,1,6]data=MergeSort(data)print_data(data)
图片来自维基百科
