常用排序算法
排序算法非常的多，在学习数据结构和算法时肯定都会学习到关于排序的算法，虽然现在高级语言都自带内置的排序函数，但是理解一些常见排序算法的思想和适用场合也是非常重要的，这也是面试时的经典题目，所以准备找工作的我打算将这些算法复习和整理一遍，所有算法代码采用Python编写。（数组下标从0开始）
冒泡排序
冒泡排序应该是第一个学习的排序算法吧，在学习C语言时就会学到，虽然效率比较低，但是在某些不需要全部排序的情况下也是很有效的，比如只需找出前3大的元素时。
算法描述
从第一个记录开始，相邻记录两两比较，若前一个记录大于后一个记录，则交换
第一趟将序列中最大的记录放到了最后一个位置
n个记录比较n-1趟
代码
def bubble_sort(lists):
for i in range(len(lists)):
for j in range(0, len(lists)-i-1):
if lists[j] > lists[j+1]:
lists[j], lists[j+1] = lists[j+1], lists[j]
优化冒泡代码
def bubble_sort(lists):
for i in range(len(lists)):
flag = True
for j in range(0, len(lists)-i-1):
if lists[j] > lists[j+1]:
flag = False
lists[j], lists[j+1] = lists[j+1], lists[j]
if flag:
break
算法分析
冒泡排序是稳定的，时间复杂度很容易就看出是O(n^2)，所以是一个比较慢的排序算法。优化的冒泡排序是设置一个标识符，当flag为真时说明没有发生交换，则后面都为有序的，可以直接跳出循环。
选择排序
基本思想：序列大小为N,则共进行N-1趟排序，第一趟选出最小的与第一个元素交换，第二趟在剩余的无序序列中选出最小的与第二个元素交换，一直进行N-1趟。
代码
def select_sort(lists):
length, i = len(lists), 0
while i < length-1:
min_temp = i
for j in range(i+1, length):
if lists[j] < lists[min_temp]:
min_temp = j
lists[i], lists[min_temp] = lists[min_temp], lists[i]
i += 1
算法分析
时间复杂度O(n^2),算法是稳定的。选择排序与冒泡排序有点相似，每一轮排序结束时最大的元素将被放置到序列的一端，区别在于选择排序只交换一次，冒泡排序可能交换很多次。
快速排序
快速排序之所以叫快速排序，那当然是因为他快了~
基本思想：任取待排序对象序列中的某个对象v(枢轴，基准，支点)，按照该对象的关键字大小，将整个序列划分为左右两个子序列：
- 左侧子序列中所有对象的关键字都小于或等于对象v的关键字；
- 右侧子序列中所有对象的关键字都大于或等于对象v的关键字；
- 对象v则排在这两个子序列中间(也是它最终的位置)
算法步骤：首先选取一个基准元素(pivot)，基准元素可以任意选择，将基准元素与第一个元素交换。令i指向第一个元素，j指向最后一个元素,首先从最后一个元素开始向前遍历序列，遇到比pivot小的元素时，将j指向的值赋值给i指向的位置；然后i加1，从i开始向后遍历，直到遇到比pivot大的元素，赋值给j指向的位置；然后开始移动j....算法一直重复直到i==j，将pivot的值赋值给j指向的位置。到这一步就将序列分成左右两部分，左边部分小于等于pivot，右边部分大于等于pivot，递归执行上述步骤直到左右序列长度都为1
讲解示例
有数组如下：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 30 | 2 | 87 | 25 | 49 | 50 | 22 | 12 |
令pivot = lists[0] = 30, i = 0, j = 7
j=7时，lists[7]=12 < pivot，lists[i]=lists[j]
得到如下数组: [12, 2, 87, 25, 49, 50, 22, 12]
i++, i=1时，lists[1]=2 < pivot, i++
i=2时, lists[2]=87 > pivot, lists[j]=lists[i]
得到如下数组：[12, 2, 87, 25, 49, 50, 22, 87]
j--, j=6, lists[6]=22 < pivot, lists[i]=lists[j]
得到如下数组：[12, 2, 22, 25, 49, 50, 22, 87]
i++, i=3时，lists[i]=25 < pivot, i++
i=4时, lists[i]=49 > pivot, lists[j]=lists[i]
得到如下数组: [12, 2, 22, 25, 49, 50, 49, 87]
j--, j=5时，lists[j]=50 > pivot, j--
j=4时, j == i,lists[j]=pivot
得到如下数组：[12, 2, 22, 25, 30, 50, 49, 87]
代码
def quick_sort(lists, left, right):
if left < right:
i, j, pivot = left, right, lists[left]
while i < j:
while i < j:
if lists[j] < pivot:
lists[i] = lists[j]
break
j -= 1
while i < j:
if lists[i] > pivot:
lists[j] = lists[i]
break
i += 1
lists[j] = pivot
quick_sort(lists, left, j-1)
quick_sort(lists, j+1, right)
算法分析
快速排序在实际应用中有最好的运行速度，平均时间复杂度为O(nlogn)，但是最坏的情况下位O(n^2)。至于为什么快速排序在时间复杂度为O(nlogn)的一些排序算法中速度最快，感兴趣的可以自己去查查资料。此外影响快速排序效率的关键就是Pivot的选择，常见的有取第一个，取最后一个，取前中后的中间数，pivot如果能正好将序列左右等分，那效率就是最高的。
插入排序
插入排序有多种变形算法，我介绍一下直接插入排序、折半插入排序和希尔排序，前两种算法只在插入的时候有些区别，总体思想是一致的。
插入排序的思想
- 一个记录是有序的
- 从第二个记录开始，将每个记录插入到已排好序的序列中
- 一直进行到第n个记录
直接插入排序
直接插入排序第n次循环将下标为n的元素A插入合适的位置，将A依次与前一个元素B比较，若A>=B,则A不动，进入下一次循环；若A<B，则交换AB，重复上述操作。
代码
def direct_insert_sort(lists):
for i in range(1, len(lists)):
if lists[i] >= lists[i-1]:
continue
lists[i], lists[i-1] = lists[i-1], lists[i]
for j in range(i-1, 0, -1):
if lists[j] >= lists[j-1]:
break
lists[j], lists[j-1] = lists[j-1], lists[j]
算法分析
- 直接插入排序是稳定排序算法
- 时间复杂度：最好情况O(1),最坏O(n2),平均O(n2)
- 空间复杂度O(1)
折半插入排序
在插入排序中，第n次循环时，下标0到n-1的元素是有序的，可以用二分查找找到合适位置并插入第n个元素。
代码
def binary_insert_sort(lists):
for i in range(1, len(lists)):
if lists[i] >= lists[i-1]:
continue
# 折半查找
low, high = 0, i-1
while low <= high:
mid = (high + low) // 2
if lists[mid] > lists[i]:
high = mid - 1
else:
low = mid + 1
for j in range(i, low, -1):
lists[j], lists[j-1] = lists[j-1], lists[j]
算法分析
为什么用low下标作为最终位置呢？可以看while循环的条件是low<=high，且是唯一跳出循环的条件，low与high只以1为增量，所以退出循环时low=high+1，但最后一次有效循环时，low与high与mid是相等的，如果lists[mid] > lists[i],则这个元素应该在mid前面，也就是low前面，如果lists[mid] <= lists[i]，则这个元素应该在mid后面，即low=mid+1这个位置。
希尔排序
希尔排序与直接插入算法大致过程是一样的，希尔排序需要进行多趟排序，先进行宏观排序，再进行微观排序。宏观调整指跳跃式的插入排序
大致过程：
- 将数组分为若干个子序列进行插入排序
例如：将N个记录分成d个子序列
{R[1], R[1+d], R[1+2d] ....}
{R[2], R[2+d], R[2+2d] ....}
....
{R[d], R[d+d], R[d+2d] ....}
- 其中d为增量，他的值在排序过程中从大到小逐渐减少，最后一次排序变为1
代码
def shell_insert_sort(lists, dlta):
# para dlta: 增量d的序列，保证最后一个为1
for k in dlta:
shell_insert(lists, k)
def shell_insert(lists, step):
for i in range(step):
for j in range(i+step, len(lists), step):
if lists[j] >= lists[j-step]:
continue
lists[j], lists[j-step] = lists[j-step], lists[j]
for j in range(j-step, i+step-1, -step):
if lists[j] >= lists[j-step]:
break
lists[j], lists[j-step] = lists[j-step], lists[j]
算法分析
希尔排序是不稳定的排序方法，即元素的相对顺序会改变。但是希尔排序的平均时间复杂度要比直接插入排序快一些，在O(n1.3)与O(n1.5)之间(来自教材)。希尔排序的优势在于减少了元素交换的次数，因为他可以以相对快的速度将大的数转移到数组的后面部分，取决于增量d的序列，因此增量d的序列的选择是算法效率好坏的关键。
归并排序
基本思想：（1）将N个记录看成n个长度为1的有序子表（2）将两两相邻的有序子表进行归并，若子表个数为奇数，最后一个子表进入下一次归并（3）重复步骤（2），直到归并成一个长度为N的有序表
代码
def merge_sort(lists):
step, length = 1, len(lists)
extend = [0 for i in range(length)]
while step < length*2:
start = 0
while start < length:
low, mid = start, min(start+step, length)
high, temp = min(start+step+step, length), low
start1, end1 = low, mid
start2, end2 = mid, high
while start1 < end1 and start2 < end2:
if lists[start1] < lists[start2]:
extend[temp] = lists[start1]
temp += 1
start1 += 1
else:
extend[temp] = lists[start2]
temp += 1
start2 += 1
while start1 < end1:
extend[temp] = lists[start1]
temp += 1
start1 += 1
while start2 < end2:
extend[temp] = lists[start2]
temp += 1
start2 += 1
start += 2 * step
lists, extend = extend, lists
step += step
算法分析
归并排序有两种方式，一种自上而下，一种自下而上，我的示例代码为自下而上，也称为2路归并。归并排序是一个稳定的排序方法，每趟归并耗费O(n)的时间，归并趟数为logn，所以时间复杂度为O(nlogn)。但是也使用了额外的存储空间，空间复杂度为O(n)。
堆排序
堆排序属于选择排序，出发点是利用前一次比较的结果，减少比较次数。
了解堆排序首先需要知道堆的定义，这里用到的堆是完全二叉树，分为小根堆和大根堆。其中最大堆满足如下条件
父结点的值大于等于儿子结点
左右子树都是一个二叉堆
因为待排序的一般是序列，用序列表示如下：
A[i] >= A[2i+1]
且 A[i] > A[2i+2]
堆排序需要解决两个问题
由一个无序序列建成一个最大(小)堆
弹出堆顶元素，调整剩余元素成为新的堆
算法步骤（大根堆）
建立大根堆
输出堆顶元素，即lists[0]与最后一个未排序的元素交换，第一次为最后一个，第二次为倒数第二个......
交换后，未排序的元素不再满足大根堆的特性，重新建堆
重复2.3两步，知道排序完成
代码
def heap_sort(lists):
length = len(lists)
for i in range(length//2-1, -1, -1):
max_heap_adjust(lists, i, length)
for i in range(length-1, 0, -1):
lists[0], lists[i] = lists[i], lists[0]
max_heap_adjust(lists, 0, i)
def max_heap_adjust(lists, start, end):
while True:
imax, ileft, iright = start, 2*start+1, 2*start+2
if ileft < end and lists[start] < lists[ileft]:
imax = ileft
if iright < end and lists[imax] < lists[iright]:
imax = iright
if imax == start:
break
lists[start], lists[imax] = lists[imax], lists[start]
start = imax
算法分析
堆排序是不稳定的排序，时间复杂度为O(nlogn)。且最慢情况下也为O(nlogn)。
这个算法需要对二叉树的一些特性有了解，不然边界情况很容易糊涂了，我自己写代码的时候少了一次循环，改来改去没发现，总觉得是对的，浪费了挺久时间。
总结
有些排序代码一下子写出来还是比较难的，但是算法更重要的是理解吧，毕竟写的这些排序算法也不太用的到,而且同样的思想和步骤也能写出不一样的代码，也会影响排序的快慢，开头也提到过了，高级语言的库里一般都自带排序算法，且速度更快，所以理解透彻就行了。下面我简单的以我写的代码测一下三个O(nlogn)时间复杂度的算法和Python内置sort()的速度快慢。序列全部random产生，同一组测试为同一个序列。
10000个元素
<function merge_sort at 0x00000245EC6AA9D8> costs : 0.03701162338256836
<function quick_sort at 0x00000245EC6AAC80> costs : 0.025029897689819336
<function heap_sort at 0x00000245EC6AAAE8> costs : 0.05319356918334961
<function python_sort at 0x00000245EC6AAE18> costs : 0.002984762191772461
50000个元素
<function merge_sort at 0x000002523ECCA9D8> costs : 0.21823906898498535
<function quick_sort at 0x000002523ECCAC80> costs : 0.1542985439300537
<function heap_sort at 0x000002523ECCAAE8> costs : 0.3872966766357422
<function python_sort at 0x000002523ECCAE18> costs : 0.016024351119995117
100000个元素
<function merge_sort at 0x0000023023FBA9D8> costs : 0.4917008876800537
<function quick_sort at 0x0000023023FBAC80> costs : 0.3395521640777588
<function heap_sort at 0x0000023023FBAAE8> costs : 0.7686326503753662
<function python_sort at 0x0000023023FBAE18> costs : 0.03353142738342285
可以看出python自带的排序sort()方法是远远快于我写的排序算法的。。。。不过快排确实是NlogN级别算法中速度最快的。
