算法原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前遍历，找到合适位置插入。
算法步骤：将第一个待排序序列的第一个元素看作是一个有序序列，其余为未排序序列，以此为基础，从第二个元素开始扫描，将扫描到的每个元素都插入到有序序列合适的位置上。
例如 10 23 9 46 11 32
（从小到大排序的每轮排序过程如下 |之前表示排好序的有序序列，后边是待排序的数据）
第一轮结果 10 23 | 9 46 11 32
第二轮结果 9 10 23 | 46 11 32
第三轮结果 9 10 23 46 | 11 32
第四轮结果 9 10 11 23 46 | 32
第五轮结果 9 10 11 23 32 46 |
def insertSort(arr):
for i in range(1,len(arr)):
key=arr[i]
j=i-1
while j>=0 and key<arr[j]:
arr[j+1]=arr[j]
j-=1
arr[j+1]=key
arr=[10,23,9,46,11,32]
insertSort(arr)
print("排序后的数组：")
for i in range(len(arr)):
print("%d"%arr[i])
算法原理：快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
算法步骤：
（1）挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;
（2）分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;
（3）递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
注：递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
例如 10 23 9 46 11 32
（从小到大排序的每轮排序过程如下 以右侧数据为基准 ，加粗表示是基准值，中间有省略轮数）
第一轮结果 10 23 9 11 32 46
第二轮结果 10 9 11 23 32 46
第三轮结果 9 10 11 23 32 46
def partition(arr,low,high):
i=(low-1)
pivot=arr[high]#以右侧为基准
for j in range(low,high):
if arr[j]<=pivot:
i=i+1
arr[i],arr[j]=arr[j],arr[i]
arr[i+1],arr[high]=arr[high],arr[i+1]
return i+1
def quickSort(arr,low,high):
if low<high:
pi=partition(arr,low,high)
quickSort(arr,low,pi-1)
quickSort(arr,pi+1,high)
arr=[10,23,9,46,11,32]
n=len(arr)
quickSort(arr,0,n-1)
print("排序后的数组：")
for i in range(n):
print("%d"%arr[i])
算法原理：每次都找到未排序中最小（大）的。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法步骤：
（1）首先在未排序序列中找到最小（大）元素存放到排序序列的起始位置；
（2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾(也就是和未排序的第一个值交换)；
（3）重复步骤二，直到所有元素均排序完毕。
例如 10 23 9 46 11 32
（从小到大排序的每轮排序过程如下 |之前表示排好序的有序序列，后边是待排序的数据）
第一轮结果 9 | 23 10 46 11 32
第二轮结果 9 10| 23 46 11 32
第三轮结果 9 10 11 |46 23 32
第四轮结果 9 10 11 23| 46 32
第五轮结果 9 10 11 23 32 46|
arr=[10,23,9,46,11,32]
for i in range(len(arr)):
min_idx=i
for j in range(i+1,len(arr)):
if arr[min_idx]>arr[j]:
min_idx=j
arr[i],arr[min_idx]=arr[min_idx],arr[i]
print("排序后的数组：")
for i in range(n):
print("%d"%arr[i])
算法原理：冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。
算法步骤：（从小到大排序）
（1）比较相邻的元素，如果第一个比第二个大就交换；
（2）对每一对相邻元素都做上述同样的工作，从开始第一对直到结尾最后一对，这样都遍历后，最后的元素会是最大的元素；
（3）除最后一个元素，针对剩下的未排序排序重复上述步骤；
（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
例如 10 23 9 46 11 32
（从小到大排序的每轮排序过程如下 |之前表示排好序的有序序列，后边是待排序的数据）
10 23 9 46 11 32
10 9 23 46 11 32
10 9 23 46 11 32
10 9 23 11 46 32
第一轮结果 10 9 23 11 32 46
9 10 23 11 32 46
9 10 23 11 32 46
9 10 11 23 32 46
第二轮结果 9 10 11 23 32 46
依此类推 这个有点特殊 到这就排好了
def bubbleSort(arr):
n=len(arr)
for i in range(n):
for j in range(0,n-i-1):
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
arr=[10,23,9,46,11,32]
bubbleSort(arr)
print("排序后的数组：")
for i in range(len(arr)):
print("%d"%arr[i])
算法原理：归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
分治法:
分割：递归地把当前序列平均分割成两半。
集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。
算法步骤：
（1）申请空间，使其大小为两个已经排序序列之和，用来存放合并后的序列；
（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置；
（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
（4）重复步骤3直到某一指针达到序列尾；
（5）将另一序列剩下的所有元素直接复制到合并序列尾.
例如 10 23 9 46 11 11 32
（从小到大排序的每轮排序过程如下）
第一轮结果 :
先分割 10 23 9 |4611 11 32
再分 10 | 23 9 || 46 11 | 11 32
10 | 9 23 || 11 46 | 11 32
第二轮结果 9 10 23|| 11 11 32 46
第三轮结果 9 10 11 11 23 32 46
def merge(arr,l,m,r):
n1=m-l+1
n2=r-m
#创建两个临时数组
L=[0]*(n1)
R=[0]*(n2)
#把左右数据拷贝到临时数组里
for i in range(0,n1):
L[i]=arr[l+i]
for j in range(0,n2):
R[j]=arr[m+1+j]
#比较两个数组归并到原始数组里
i=0
j=0
k=l
while i<n1 and j<n2:
if L[i]<=R[j]:
arr[k]=L[i]
i+=1
else:
arr[k]=R[j]
j+=1
k+=1
while i<n1:
arr[k]=L[i]
i+=1
k+=1
while j<n2:
arr[k]=R[j]
j+=1
k+=1
def mergeSort(arr,l,r):
if l<r:
m=int((l+(r-1))/2)
mergeSort(arr,l,m)
mergeSort(arr,m+1,r)
merge(arr,l,m,r)
arr=[10,23,9,46,11,11,32]
n=len(arr)
mergeSort(arr,0,n-1)
print("排序后的数组：")
for i in range(len(arr)):
print("%d"%arr[i])
算法原理：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点（大根堆）。堆排序可以说是一种利用堆的概念来排序的选择排序。
算法步骤：（从大到小）
（1）创建一个堆；然后调整堆的元素，保证其满足堆的性质：子节点小于父节点，这样堆首元素就是最大的（构造出一个大根堆）；
（2）把堆首和堆尾互换（堆尾也就是堆的最下最右的元素）；这样就每次都找到了最大值；
（3）把堆的尺寸缩小1，然后把新的数组顶端数据调整到相应位置（也就是调整堆使其满足那个性质仍保证堆首元素是最大的）；
（4）重复步骤2，3，直到堆的尺寸为1。
注：通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中
父节点i的左子节点在位置(2i+1);
父节点i的右子节点在位置(2i+2);
子节点i的父节点在位置floor((i-1)/2);
def heapify(arr,n,i):
#确保了根节点和他的两个子节点是符合大根堆性质的
largest=i#这一部分的根节点
l=2*i+1#左子节点
r=2*i+2#右子节点
if l<n and arr[largest]<arr[l]:
largest=l
if r<n and arr[largest]<arr[r]:
largest=r
if largest!=i:
arr[i],arr[largest]=arr[largest],arr[i]
heapify(arr,n,largest)
def heapSort(arr):
n=len(arr)
#heapify函数实际上是对传入的arr[i]点在其所有根部中确定它的位置；
for i in range(n,-1,-1):
heapify(arr,n,i)
#交换元素
for i in range(n-1,0,-1):
#arr[0]一直是大根堆的堆顶，也就是未排序数组中最大的那个元素，每次都用末尾的元素和他交换，这样就得到了最大值
arr[i],arr[0]=arr[0],arr[i]
heapify(arr,i,0)
arr=[10,23,9,46,11,11,32]
n=len(arr)
heapSort(arr)
print("排序后的数组：")
for i in range(n):
print("%d"%arr[i])
算法原理：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。（使用时有局限性）
算法步骤：依次统计数组元素的个数，把数组的值作为下标。
def countSort(arr,maxValue):
bucketLen=maxValue+1
bucket=[0]*bucketLen
for a in arr:
if not bucket[a]:
bucket[a]=0
bucket[a]+=1
arr.clear()
for i in range(len(bucket)):
while bucket[i]>0:
arr.append(i)
bucket[i]-=1
return arr
arr=[10,23,9,36,11,19,32]
srr=countSort(arr,40)
print(srr)
算法原理：希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。（分组插入排序）
算法步骤：
（1）先选择一个增量序列；
（2）按增量序列个数k，对其进行k趟排序；
（3）每趟排序，根据对应的增量，将待排序序列分成若干子序列，分别对子序列进行直接插入排序，直到增量因子为1时。
def shellSort(arr):
n=len(arr)
gap=int(n/2)
while gap>0:
for i in range(gap,n):
temp=arr[i]
j=i
while j>=gap and arr[j-gap]>temp:
arr[j]=arr[j-gap]
j-=gap
arr[j]=temp
gap=int(gap/2)
arr=[10,3,19,36,11,19,32]
shellSort(arr)
print("排序后的数组：")
for i in range(len(arr)):
print("%d"%arr[i])
算法原理：先排元素的最后一位，再排倒数第二位，直到所有位数都排完。不能先排第一位，那样最后依然是无序。排序是基于桶排序实现的，向桶中放元素的时候一定要按顺序放。
算法步骤：
（1）先从最低位排起，取元素某一位的值 i是从个位开始算起 （0） int(x/(10**i))%10 取到这个位数 存到桶数组的相应位置；
（2）依次取倒数第二位数字
（3）重复上述步骤直到最高位取完。
def radixSort(s):
i=0#记录当前正在排的是数据的第几位数
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
arr=[10,23,19,36,51,49,32]
radixSort(arr)
print("排序后的数组：")
for i in range(len(arr)):
print("%d"%arr[i])
算法原理：对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（Topological sorting）：
from collections import defaultdict
class Graph:
def __init__(self,vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self,u,v):
self.graph[u].append(v)
def topologicalSortUtil(self,v,visited,stack):
visited[v] = True
for i in self.graph[v]:
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
stack.insert(0,v)
def topologicalSort(self):
visited = [False]*self.V
stack =[]
for i in range(self.V):
if visited[i] == False:
self.topologicalSortUtil(i,visited,stack)
print (stack)
g= Graph(6)
g.addEdge(5, 2)
g.addEdge(5, 0)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(2, 3)
g.addEdge(3, 1)
print ("拓扑排序结果：")
g.topologicalSort()