经典排序算法详细介绍

时间复杂度

渐进时间复杂度（asymptotic time complexity）的概念，官方的定义如下：

若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。

记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。

渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

O(n)是nums中的元素个数算法和n呈线性关系，忽略了常数。实际是

T = c1*n + c2;
但是
T = 2*n + 2 O(n)
T = 2000*n + 10000 O(n)
T = 1*n*n + 0 O(n^2)

上面的表达式中第三个n下于3000的时候都是比前面的要小的，但是在n接近无穷的时候，
就是不一样了，所以O是渐进时间复杂度描述n趋近于无穷的情况

O一般是计算最坏的结果
均摊复杂度，有时早规律出现的时候可以使用均摊复杂度
复杂度震荡，在边界情况下，来回操作，过于着急（Eager)解决方案就是Lazy

数据结构操作的复杂性

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做 S(n)=O(f(n))。比如直接插入排序的时间复杂度是 O(n^2) ,空间复杂度是O(1) 。而一般的递归算法就要有 O(n) 的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

前面提到了，时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。类比一下，空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
我还是拿具体的例子来给你说明。（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

我们常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚我说的这些内容已经足够了。

时间-空间 复杂度详解：https://www.cnblogs.com/chenjinxinlove/p/10038919.html

稳定性

排序算法的稳定性，通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。即：如，如果A1 == A2，A1 原来在 A2 位置前，排序后 A1 仍然是在 A2 位置前。

　　1、如果排序算法是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所利用。              基数排序就是这样，先按低位排序，逐次按高位排序，那么，低位相同的数据元素其先后位置顺序即使在高位也相同时是不会                改变的。

　　2、学习排序原理时，可能编的程序里面要排序的元素都是简单类型，实际上真正应用时，可能是对一个复杂类型（自定义类型）             的数组排序，而排序的键值仅仅只是这个元素中的一个属性，对于一个简单类型，数字值就是其全部意义，即使交换了也看不               出什么不同。但是，对于复杂类型，交换的话可能就会使原本不应该交换的元素交换了。比如：一个“学生”数组，欲按照年龄排             序，“学生”这个对象不仅含有“年龄”，还有其它很多属性。假使原数组是把学号作为主键由小到大进行的数据整理。而稳定的排             序会保证比较时，如果两个学生年龄相同，一定不会交换。也就意味着尽管是对“年龄”进行了排序，但是学号顺序仍然是由小到            大的要求。

　　3、如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能相对会少一些。

常用排序算法

算法比较

O(n)这样的标志叫做渐近时间复杂度,是个近似值.各种渐近时间复杂度由小到大的顺序如下

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
一般时间复杂度到了2^n(指数阶) 及更大的时间复杂度，这样的算法我们基本上不会用了，不实用了。比如递归实现的汉诺塔问题算法就是O(2^n。

平方阶(n^2)的算法是勉强能用,而nlogn及更小的时间复杂度算法那就是非常高效的算法了啊.

lowB 三人组

冒泡排序 Bubble Sort

性质：稳定性排序算法
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

　　原理：比较两个相邻的元素，将值大的元素交换到右边

　　思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。

由上图可知：

　　1、第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。

　　2、比较第2和第3个数，将小数 放在前面，大数放在后面。

　　3、如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成

　　4、在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。

　　5、在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。

　　6、依次类推，每一趟比较次数减少依次

# Bubble Sort
def bubble_sort(nums):
for i in range(len(nums) - 1): # 这个循环负责设置冒泡排序进行的次数
for j in range(len(nums) - i - 1): # j为列表下标
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums

print(bubble_sort([45, 32, 8, 33, 12, 22, 19, 97]))

# 输出：[8, 12, 19, 22, 32, 33, 45, 97]

# Second
def bubble(bubbleList):
listLength = len(bubbleList)
while listLength > 0:
for i in range(listLength - 1):
if bubbleList[i] > bubbleList[i+1]:
bubbleList[i], bubbleList[i+1] = bubbleList[i+1], bubbleList[i]
listLength -= 1
print bubbleList

if __name__ == '__main__':
bubbleList = [3, 4, 1, 2, 5, 8, 0]
bubble(bubbleList)

算法分析：
　　由此可见：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多                               少趟，内层控制每一趟的循环次数

　　冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排                             在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找                             出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以                             此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。

　　时间复杂度：如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：         　　                 Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。如果很不幸我们的数据是反序的，则需要进行n-1趟排                           序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较                             和移动次数均达到最大值：

综上所述：冒泡排序总的平均时间复杂度为：O(n2) ,时间复杂度和数据状况无关。

选择排序 Selection Sort

性质：不稳定的排序方法
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

　　原理： 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
　　　　　 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
　　　　　 重复第二步，直到所有元素均排序完毕。

　　思路： 从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终　　                       得到一个有序序列。

1、初始状态：序列为无序状态。

2、第1次排序：从n个元素中找出最小(大)元素与第1个记录交换

3、第2次排序：从n-1个元素中找出最小(大)元素与第2个记录交换

4、第i次排序：从n-i+1个元素中找出最小(大)元素与第i个记录交换

5、以此类推直到排序完成

# Selection sort
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

算法分析：
　　由此可见： 每经过一轮排序，有序区域内的元素数量增加1个。
　　　　　　　 如果待排序的元素个数为N。需要经历N-1轮排序。

　　选择排序的优点：n 个记录的文件的直接选择排序可经过n-1 趟直接选择排序得到有序结果。移动数据的次数已知（n-1 次）；

　　时间复杂度：

　　　　1、简单选择排序的比较次数与序列的初始排序无关。假设待排序的系列有N个元素，则比较次数总是 N（N-1）/2而移动次数                      与系列的初始排序有关，当排序正序时，移动次数最少，为0
　　 　　2、当序列反序时，移动次数最多，为 3N（N-1）/2
　　　　　   所以，综上，简单排序的时间复杂度为 O（N*N）
　　　　　   选择排序的简单和直观名副其实，这也造就了它”出了名的慢性子”，无论是哪种情况，哪怕原数组已排序完成，它也将花                       费将近n²/2次遍历来确认一遍。
　　              即便是这样，它的排序结果也还是不稳定的。 唯一值得高兴的是，它并不耗费额外的内存空间。

　　　　　　综上所述：选择排序总的平均时间复杂度为：O(n2) ,时间复杂度和数据状况无关。

插入排序 Lnsertion Sort

性质：稳定性排序算法
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。

　　原理：
　　　　插入排序始终在列表的较低位置维护一个排序的子列表，遇到新的项将它插入到原来的子列表，使得排序的子列表称为一个                  较大的项。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一                个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插                入到已排好序的第一部分中。

　　思路：
　　　　每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

1、从第一个元素开始，该元素可认为已排序。

2、取出下一个元素，在排序好的元素序列中从后往前扫描

3、如果元素(已排序)大于新元素，将该元素移到下一位置

4、重复3.直到找到已排序的元素小于或等于新元素的位置

5、将新元素插入该位置后

6、重复2-5直到排序完成

# Insertion sort
def insert_sort(lst):
for i in range(1,len(lst)):
tmp = lst[i]
j = i - 1
while j >= 0 and tmp < lst[j]:
lst[j + 1] = lst[j]
j = j - 1
lst[j + 1] = tmp
return lst

算法分析：
插入排序是一种简单直观的排序算法，工作原理为构建有序序列，对于未排序元素，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间，直到排序完成，如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。理解了插入排序的思想后，我们便能够得到它的时间复杂度。对于n个元素，一共需要进行n-1轮比较，而第k轮比较需要进行k次数组元素的两两比较，因此共需要进行的比较次数为：1 + 2 + … + (n-1)，所以插入排序的时间复杂度同冒泡排序一样，也为O(n^2)。

对比冒泡和插入的代码，冒泡排序的数据交换比插入排序的数据移动要复杂，冒泡排序需要三次赋值操作，而插入排序只需要一次。
因此，我们对逆序度为K的数组进行排序，用冒泡排序需要进行3*K次单元时间，而插入排序只需要K次单元时间。因此插入排序性能更优。

时间复杂度：

　　1、最好：如果序列已经是排好序的，那么就是最好的情况。
　　　　　　  此时外层循环执行n-1次，每次中内循环体执行1次，赋值语句执行一次，则T（n） = n-1，所以时间复杂度为O（n）。
　　2、最坏：如果序列正好是逆序的，那么就是最坏的情况。
　　　　　　  此时外层循环执行n-1次，对应的内循环体分别执行n-(n-1),n-(n-2),n-(n-3)…,n-3,n-2,n-1，T（n）= n(n-1)/2，所以时间                            复杂度为O（n）。
　　3、平均：平均执行的次数 = n-1 + n(n-1)/2 = 1/2n^2 + 1/2n -1，则平均时间复杂度为O（n^2）。

　　序列中两个相等的元素在排序之后，它们的相对位置不会发生改变。因此插入排序算法是稳定的算法。

　　综上所述：选择排序总的平均时间复杂度为：O(n2) ,时间复杂度和数据状况无关。

NB 三人组

快速排序 Quick Sort

性质：不稳定的排序方法

快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

　　原理：
　　　　先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处                  之直到每一个待处理的序列的长度为1，处理结束

　　思路：
　　　　先从数列中取出一个数作为基准数。分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。                      再对左右区间重复第二步，直到各区间只有一个数

1、求第一趟划分后的结果。

2、关键码 序列递增。

3、以第一个元素为划分基准。(自己设置的排序初始值，这里我选择第一个)

4、将两个指针i，j分别指向表的起始和最后的位置。
反复操作以下两步：

5、 逐渐减小，并逐次比较 j 指向的元素和目标元素的大小，若 p( j ) < T（准基） 则交换位置。

6、逐渐增大，并逐次比较 i 指向的元素和目标元素的大小，若 p( i ) > T（准基） 则交换位置。

7、直到6，5指向同一个值，循环结束。

返回规则是：左边分区+基准值+右边分区

# Quick Sort
def quick_sort(data):
"""quick_sort"""
if len(data) >= 2:
mid = data[len(data)//2]
left,right = [], []
data.remove(mid)
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
a = [2,3,4,1,45,6,6,7,8,7,9,10,18,20,30,12]

print(quick_sort(a))
[1, 2, 3, 4, 6, 6, 7, 7, 8, 9, 10, 12, 18, 20, 30, 45]

算法分析：
快速排序算法的时间复杂度和各次标准数据元素的值关系很大。如果每次选取的标准元素都能均分两个子数组的长度,这样的快速排序过程是一个完全二叉树结构。(即每个结点都把当前数组分成两个大小相等的数组结点,n个元素数组的根结点的分解次数就构成一棵完全二叉树)。这时分解次数等于完全二叉树的深度log2n;每次快速排序过程无论把数组怎样划分、全部的比较次数都接近于n-1次，所以最好情况下快速排序算法的时间复杂度为O(nlog2n):快速排序算法的最坏情况是数据元素已全部有序，此时数据元素数组的根结点的分需次数构成一棵二叉退化树(即单分支二叉树),一棵二叉退化树的深度是n,所以最坏情况下快速排序算法的时间复杂度为O(n2)。般情况下 ,标准元素值的分布是随机的，数组的分邮大数构成模二又树，这样的二叉树的深度接近于log2n, 所以快速排序算法的平均(或称期望）时间复杂度为O(nlog2n)

时间复杂度：

1、快速排序最优的情况就是每一次取到的元素都刚好平分整个数组。
此时的时间复杂度公式则为：T[n] = 2T[n/2] + f(n)；T[n/2]为平分后的子数组的时间复杂度，f[n] 为平分这个数组时所花的时间

2、最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)

这种情况时间复杂度就好计算了，就是冒泡排序的时间复杂度：T[n] = n * (n-1) = n^2 + n;

平均时间复杂度为O（nlog2n）

堆排序 HeapSort

性质：不稳定的排序方法

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

什么是 堆？

堆是一种特殊的完全二叉树

树： 树是不包含回路的连通无向图（任意的两个节点仅有唯一的一条路径连通，在一棵树中加一条边会构成图）
二叉树： 是一种特殊的树，只要不为空，就由根节点、左子树和右子树组成，左子树和右子树分别是一棵二叉树
完全二叉树： 完全二叉树和满二叉树都是一种特殊的二叉树，两者可以一起记，如下图，左边为满二叉树：每个分支节点都有左子树和右子树，所有叶子都在同一层上。右边为完全二叉树，是从右向左减少叶子节点的满二叉树

堆分为：

大顶堆：所有父节点都比子节点大
小顶堆：所有父节点都比子节点小

堆排序就是利用堆（假设利用大顶堆）进行排序的方法。

原理：
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。如此反复执行，便能得到一个有序序列了。
一般升序采用大顶堆，降序采用小顶堆

还有个简易版的：

假设

根节点的左右子树都是堆，但根节点不满足堆的性质（大根堆，小根堆）
可以通过一次向下的调整来将其变成一个堆 (下图)

堆排序过程：

步骤：

　　1、建立堆
　　2、得到堆顶元素，为最大元素
　　3、去掉堆顶，将堆最后一个元素放到堆顶，此时可通过一次调整重新使堆有序。
　　4、堆顶元素为第二大元素
　　5、重复步骤3，直到堆变空
这回理解了吧。

堆排序的实现过程中，其实大部分过程都在调整过程（建立堆，排序的时候去掉堆顶，重新调整）

所以我们先来实现调整堆的代码

def heap_sort(li):
"""
实现堆排序过程：
1、先根据传入的列表构建堆（大根堆）
2、再埃个出数
:param li: 
:return: 
"""
n = len(li)

# 1、构建堆--包围框
for i in range((n-2)//2, -1, -1):
# i 就是每个父节点的位置
# (n-2)//2 是根据堆的最后一个叶子节点位置推算其父节点位置的公式：(i-1)//2
# 而 i 又等于 n - 1, 所以 (i-1)//2 == ((n - 1)-1)//2 == (n-2)//2 
# 第一个 -1 ，因为要从最后一个根节点循环到第一个根节点也就是列表中下标为0的元素，range 为开头闭尾
# 第二个 -1， 倒序
sift(li, i, n-1)

# 2、埃个出数，完成列表排序，
# 原地排序，每次都根节点都和最后一个叶子节点互换，然后调整位置， 再进行如上循环操作，直到堆为空
for i in range(n-1, -1, -1):
# i是每次循环堆里面最后一个数
li[0], li[i] = li[i], li[0]
sift(li, 0, i-1) # 边界值下标， 因为出数完之后，最后原i位置上的元素是出数的结果，所以i位置上的元素不参加调整，故边界值为i-1.


# 书写完毕进行测试

li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)
heap_sort(li)
print(li)


[26, 16, 81, 29, 11, 75, 73, 0, 35, 21, 95, 37, 72, 79, 80, 46, 76, 1, 93, 45, 25, 48, 92, 77, 42, 40, 82, 10, 6, 67, 30, 96, 47, 51, 38, 60, 4, 61, 64, 97, 33, 71, 8, 59, 87, 49, 19, 22, 83, 44, 9, 28, 27, 99, 69, 12, 2, 34, 24, 85, 32, 53, 14, 88, 90, 41, 55, 39, 20, 94, 63, 23, 7, 66, 84, 74, 62, 58, 56, 70, 86, 17, 89, 13, 18, 65, 50, 98, 5, 54, 15, 78, 3, 57, 31, 52, 68, 43, 36, 91]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]

第二种

def bucket_sort(s):
"""桶排序"""
min_num = min(s)
max_num = max(s)
# 桶的大小
bucket_range = (max_num-min_num) / len(s)
# 桶数组
count_list = [ [] for i in range(len(s) + 1)]
# 向桶数组填数
for i in s:
count_list[int((i-min_num)//bucket_range)].append(i)
s.clear()
# 回填，这里桶内部排序直接调用了sorted
for i in count_list:
for j in sorted(i):
s.append(j)

if __name__ == '__main__':
a = [3.2,6,8,4,2,6,7,3]
bucket_sort(a) 
print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

算法分析：
　　优点：

　　　　堆排序的效率与快排、归并相同，都达到了基于比较的排序算法效率的峰值（时间复杂度为O(nlogn)）
　　　　除了高效之外，最大的亮点就是只需要O(1)的辅助空间了，既最高效率又最节省空间，只此一家了
　　　　堆排序效率相对稳定，不像快排在最坏情况下时间复杂度会变成O(n^2)），所以无论待排序序列是否有序，堆排序的效率都                   是O(nlogn)不变（注意这里的稳定特指平均时间复杂度=最坏时间复杂度，不是那个“稳定”，因为堆排序本身是不稳定的）

　　缺点：

　　　（从上面看，堆排序几乎是完美的，那么为什么最常用的内部排序算法是快排而不是堆排序呢？）
　　　　最大的也是唯一的缺点就是——堆的维护问题，实际场景中的数据是频繁发生变动的，而对于待排序序列的每次更新                           （增，删，改），我们都要重新做一遍堆的维护，以保证其特性，这在大多数情况下都是没有必要的。（所以快排成为了实际                 应用中的老大，而堆排序只能在算法书里面顶着光环，当然这么说有些过分了，当数据更新不很频繁的时候，当然堆排序更好               些…）

时间复杂度：
若有n个元素的序列，将元素接腰序组成一棵完全二叉树，当且仅当满足下列条件时称为堆。大根堆是指所有结点的值大于或等于左右子结点的值；小掇堆是指所有结点的值小于或等于左右子结点的值。在调整建堆的过程中，总是将根结点值与左、右子树的根结点进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换。堆排序最坏情况需要0(nlogn)次比较，所以时间复杂度是0(nlogn)

初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。

归并排序 Merge Sort

性质：稳定性排序算法

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

　　原理：
　　　　归并排序是一种递归算法，不断将列表拆分为一半，如果列表为空或有一个项，则按定义进行排序。如果列表有多个项，我                  们分割列表，并递归调用两个半部分的合并排序。一旦对两半排序完成，获取两个较小的排序列表并将它们组合成单个排序                  的新列表的过程

　　思路：
　　　　归并排序中，我们会先找到一个数组的中间下标mid，然后以这个mid为中心，对两边分别进行排序，之后我们再根据两边已                  排好序的子数组，重新进行值大小分配。

1、把长度为n的输入序列分成两个长度为n/2的子序列；
2、对这两个子序列分别采用归并排序；
3、将两个排序好的子序列合并成一个最终的排序序列。

data = [45,3,2,6,3,78,5,44,22,65,46]

# 合并函数，将相邻的两个区间合并为一个
def merge(a, b):
result = []
i = j = 0
while i<len(a) and j<len(b):
if a[i] < b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
result += a[i:]
result += b[j:]
return result

def sorts(data):
length = len(data)
if length <=1:
return data
# 按照平分当前列表的方式将data递归分为很多个平均的列表
mid = length/2
a = sorts(data[:mid])
b = sorts(data[mid:])
# 递归分到每个列表只有一个数字后合并
return merge(a, b)

print sorts(data)

算法分析：
优点：

归并排序的效率达到了巅峰：时间复杂度为O(nlogn)，这是基于比较的排序算法所能达到的最高境界
归并排序是一种稳定的算法（即在排序过程中大小相同的元素能够保持排序前的顺序，3212升序排序结果是1223，排序前后两个2的顺序不变），这一点在某些场景下至关重要
归并排序是最常用的外部排序方法（当待排序的记录放在外存上，内存装不下全部数据时，归并排序仍然适用，当然归并排序同样适用于内部排序…）

缺点：

归并排序需要O(n)的辅助空间，而与之效率相同的快排和堆排分别需要O(logn)和O(1)的辅助空间，在同类算法中归并排序的空间复杂度略高

时间复杂度：

　　1、对于数组：[5,3,6,2,0,1]
　　　  序列可以分为：[5,3,6]和[2,0,1]
　　2、对上面的序列分别进行排序，结果为：
　　　  [3,5,6]和[0,1,2]
　　　  然后将上面的两个序列合并为一个排好序的序列
　　　  合并的方法是：设置两个指针，分别指着两个序列的开始位置，如下所示
　　　  [3,5,6]　　[0,1,2]
　　　　  /|\　　　　/|\
　　3、开始的时候两个指针分别指向3和0，这时我们找到一个空数组，将3和0中较小的值复制进这个 数组中，并作为第一个元素。                 新数组:[0,]
　　4、后面数组的指针后移一位，如下所示　
　　　  [3,5,6]　　[0,1,2]
　　　　/|\　　　　　/| 
　　      将1和3进行比较，1小于3，于是将1插入新数组：[0,1,…]
　　5、后面数组的指针后移一位，如下所示　
　　　　[3,5,6]　　[0,1,2]
　　　　/|\　　　　　 /|
　　     将2和3进行比较，2小于3，于是将2插入新数组：[0,1,2,…]
　　6、将剩余的左边已经有序的数组直接复制进入新数组中去，可以得到新数组：[0,1,2,3,5,6]
　　7、有master公式(递归公式)：T(n)=2T(n/2)+O(N)　　可以得出时间复杂度为：O(N*logN)
　　无论最好还是最坏均为： O(nlgn); 空间复杂度为 O(n); 是一种稳定的排序算法；

算法常规及扩展算法

二分查找法

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

原理：
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

def binary_chop(alist, data):
"""
非递归解决二分查找
"""
n = len(alist)
first = 0
last = n - 1
while first <= last:
mid = (last+first)//2
if alist[mid] > data:
last = mid - 1
elif alist[mid] < data:
first = mid + 1
else:
return True
return False


def binary_chop2(alist, data):
"""
递归解决二分查找
"""
n = len(alist)
if n < 1:
return False
mid = n // 2
if alist[mid] > data:
return binary_chop2(alist[0:mid], data)
elif alist[mid] < data:
return binary_chop2(alist[mid+1:], data)
else:
return True

if __name__ == "__main__":
lis = [2,4, 5, 12, 14, 23]
if binary_chop(lis, 12):
print('ok')
else:
print('false')

二分检索树 （只阐述、待后期补充）
定义：

　　1、二分检索树是一颗二叉树
　　2、二分检索树每个节点的左子树的值都小于该节点的值，每个节点右子树的值都大于该节点的值
　　3、任意一个节点的每棵子树都满足二分检索树的定义
特点：

　　1、高效 不接可以查找数据 插入删除数据的复杂度都是O(logn)
　　2、可以方便的回答很多数据之间的关系
　　3、min max floor ceil select

递归

在函数内部，可以调用其他函数。如果一个函数在内部调用自身，这个函数就是递归函数

1、必须有一个明确的结束条件；
2、每次进入更深一层递归时，问题规模相比上次递归都应有所减少；
3、递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈这种数据结构实现的，每次进入一个函数调用，栈            就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小是有限的，所以递归次数过多会导致栈溢出）

所以我们此时可以理解，递归是依靠 栈 来实现的

目前 Python 能承受递归的最大次数是 998(因机器而异)，大于998会导致栈溢出。
怎么解决呢？
Python设计者在sys模块中提供了一个 setrecursionlimit() 的方法，用来修改递归次数限制。

import sys
sys.setrecursionlimit(1500)

def recursion_test(numb):
print(numb)
if numb <= 0:
return
numb -= 1
recursion_test(numb)

recursion_test(998)

只需这样 就可以解决

希尔排序 Shell s Sort

性质：非稳定性排序算法
希尔排序的名称来源于它的发明者，该算法是第一批冲破二次时间屏障的算法之一，它是基于插入排序改进而成的的一种快速的算法。

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

原理：
 比较相隔一定距离的元素，并且每趟比较所用的距离随算法进行而减小，因此，希尔排序也叫做缩减增量排序。

思路：
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

def shell_sort(alist):
n = len(alist)
# 让步长从大变小，最后一步必须是1,获取gap的偏移值
gap = n // 2
# 只要gap在我们的合理范围内，就一直分组下去
while gap >= 1:
# 按照步长把数据分两半，从步长的位置遍历后面所有的数据,指定j下标的取值范围
for j in range(gap, n):
# 拿当前位置的数据，跟当前位置-gap 位置的数据进行比较
while j-gap >= 0:
# 组内大小元素进行替换操作
if alist[j]<alist[j-gap]:
alist[j], alist[j - gap] = alist[j - gap], alist[j]
# 更新迁移元素的下标值为最新值
j -= gap
else:
# 否则的话，不进行替换
break

# 每执行完毕一次分组内的插入排序，对gap进行/2细分
gap //= 2


if __name__ == '__main__':
alist = [9, 8, 7, 6, 5, 4, 3, 2, 1]
print(alist)
shell_sort(alist)
print(alist)

1、先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

2、选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

3、按增量序列个数k，对序列进行k 趟排序；

4、每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，          整 个序列作为一个表来处理，表长度即为整个序列的长度。

算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

计数排序

性质：稳定的排序方法

计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

原理：
计数排序的算法的原理，其实是非常简单的，它不需要去跟其他元素比来比去，而是一开始就知道自己的位置，所以直接归位，在计数的该元素出现的词频数组里面，出现一次，就直接+1一次即可，如果没有出现改位置就是0，最后该位置的词频，就是代表其在原始数组里面出现的次数，由于词频数组的index是从0开始，所以最后直接遍历输出这个数组里面的每一个大于0的元素值即可。

思路：

1、找出待排序的数组中最大和最小的元素；
2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

def count_sort(s):
"""计数排序"""
# 找到最大最小值
min_num = min(s)
max_num = max(s)
# 计数列表
count_list = [0]*(max_num-min_num+1)
# 计数
for i in s:
count_list[i-min_num] += 1
s.clear()
# 填回
for ind,i in enumerate(count_list):
while i != 0:
s.append(ind+min_num)
i -= 1

if __name__ == '__main__':
a = [3,6,8,4,2,6,7,3]
count_sort(a)
print(a)

步骤：

算法分析：
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

计数排序的缺点
当数值中有非整数时，计数数组的索引无法分配

桶排序 Bucket Sort

性质：稳定的排序方法

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

原理：
　　桶排序与计数排序类似，但可以解决非整数的排序
　　桶排序相当于把计数数组划分为按顺序的几个部分
　　每一部分叫做一个桶，它来存放处于该范围内的数
　　然后再对每个桶内部进行排序，可以使用其他排序方法如快速排序
　　最后整个桶数组就是排列好的数据，再将其返回给原序列

思路：
　　设置一个定量的数组当作空桶；
　　遍历输入数据，并且把数据一个一个放到对应的桶里去；
　　对每个不是空的桶进行排序；
　　从不是空的桶里把排好序的数据拼接起来。

这里选择桶的数量为序列元素个数+1，范围分别是5等分与最大值，和上面那个图一样。
具体问题应该按照具体情况进行桶划分
这里桶内部排序直接调用了sorted

def bucket_sort(s):
"""桶排序"""
min_num = min(s)
max_num = max(s)
# 桶的大小
bucket_range = (max_num-min_num) / len(s)
# 桶数组
count_list = [ [] for i in range(len(s) + 1)]
# 向桶数组填数
for i in s:
count_list[int((i-min_num)//bucket_range)].append(i)
s.clear()
# 回填，这里桶内部排序直接调用了sorted
for i in count_list:
for j in sorted(i):
s.append(j)

if __name__ == '__main__':
a = [3.2,6,8,4,2,6,7,3]
bucket_sort(a) 
print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

计数排序与桶排序都是以牺牲空间换时间，虽然很快，但由于可能产生大量的空位置导致内存增大，尤其是计数排序。

桶排序中尽量使每个桶中的元素个数均匀分布最好

基数排序 Radix Sort

性质：稳定的排序方法

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

原理：
基数排序的原理就是，先排元素的最后一位，再排倒数第二位，直到所有位数都排完。这里并不能先排第一位，那样最后依然是无序。
将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

思路：
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

从这个图中也能看出，排序是基于桶排序实现的。

然后就像排最低位一样，然后再排倒数第二位，再排倒数第三位。注意向桶中放元素的时候一定要按顺序放。

具体代码：

# 这里将列表进行基数排序，默认列表中的元素都是正整数

def radix_sort(s):
"""基数排序"""
i = 0 # 记录当前正在排拿一位，最低位为1
max_num = max(s) # 最大值
j = len(str(max_num)) # 记录最大值的位数
while i < j:
bucket_list =[[] for _ in range(10)] #初始化桶数组
for x in s:
bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组
print(bucket_list)
s.clear()
for x in bucket_list: # 放回原序列
for y in x:
s.append(y)
i += 1

if __name__ == '__main__':
a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424]
radix_sort(a)
print(a)

# 结果
[[], [1], [], [23, 3453], [334, 4, 23424], [5, 345, 345345, 45], [], [67, 7], [78], [99]]
[[1, 4, 5, 7], [], [23, 23424], [334], [345, 345345, 45], [3453], [67], [78], [], [99]]
[[1, 4, 5, 7, 23, 45, 67, 78, 99], [], [], [334, 345, 345345], [23424, 3453], [], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345], [], [], [23424, 3453], [], [345345], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453], [], [23424], [], [345345], [], [], [], [], []]
[[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424], [], [], [345345], [], [], [], [], [], []]
[1, 4, 5, 7, 23, 45, 67, 78, 99, 334, 345, 3453, 23424, 345345]

基数排序不仅仅只能排正整数，只要通过调整元素放入桶数组的方式就可以排序字符串，浮点数等

O(1) 1 1 1