一、插入排序
1.问题
输入：n个数的一个序列⟨a1,a2,⋯,an⟩\left\langle a_1,a_2,\cdots ,a_n\right\rangle⟨a1,a2,⋯,an⟩
输出：⟨a1′,a2′,⋯,an′⟩,满足a1′≤a2′≤...≤an′\left\langle a_1^{'},a_2^{'},\cdots,a_n{'}\right\rangle,满足a_1^{'}\leq a_2^{'}\leq ...\leq a_n^{'}⟨a1′,a2′,⋯,an′⟩,满足a1′≤a2′≤...≤an′
2.思路
在排序子数组A[1..j−1]A[1..j-1]A[1..j−1]后，将单个元素A[j]插入子数组的适当位置，产生排序好的子数组A[1..j]A[1..j]A[1..j]
3.伪代码
INSERTIONSORT(A)INSERTION\ SORT(A)INSERTIONSORT(A)
1forj=2toA.length1\ \bold{for}\ j=2\ to\ A.length1forj=2toA.length
2key=A[j]2\qquad key=A[j]2key=A[j]
3//InsertA[j]intothesortedsequenceA[1..j−1]3\qquad//Insert\ A[j]\ into\ the\ sorted\ sequence\ A[1..j-1]3//InsertA[j]intothesortedsequenceA[1..j−1]
4i=j−14\qquad i=j-14i=j−1
5whilei>0andA[i]>key5\qquad \bold{while}\ i>0\ and\ A[i]>key5whilei>0andA[i]>key
6A[i+1]=A[i]6\qquad \qquad A[i+1]=A[i]6A[i+1]=A[i]
7i=i−17\qquad \qquad i=i-17i=i−1
8A[i+1]=key8\qquad A[i+1]=key8A[i+1]=key
4.时间复杂度
z最坏情况的运行时间O(n2)z最坏情况的运行时间\ O(n^2)z最坏情况的运行时间O(n2)
5.特点
（1）在原数组中排序的
（2）适用于少量元素的排序
6.代码（python）
##从小到大A=[8,2,4,9,3,6]for j in range(1,len(A)): #因为列表的索引是以0开头的，range(a,b)包含头a，不含尾b,即a,a+1,....b-1key=A[j]i=j-1while i>=0 and A[i]>key:A[i+1]=A[i]i-=1A[i+1]=key
二、归并排序
1.问题
排序子数组A[p⋯r],其中p和r是下标。满足p≤r。排序子数组A[p\cdots\ r]\ ,其中p和r是下标。满足p\leq r。排序子数组A[p⋯r],其中p和r是下标。满足p≤r。
若p和r相等，那么该子数组只有一个元素，不需要进行排序。否则，要进行排序。若p和r相等，那么该子数组只有一个元素，不需要进行排序。否则，要进行排序。若p和r相等，那么该子数组只有一个元素，不需要进行排序。否则，要进行排序。
2.思路
———分治法的思想
（1）分解：分解待排序的nnn个元素的序列成各具n/2n/2n/2个元素的两个子序列
（2）解决：使用归并排序递归的排序两个子序列
（3）合并：合并两个已排序的子序列
3.伪代码
MERGE(A,p,q,r)MERGE(A,p,q,r)MERGE(A,p,q,r)
//该过程假设子数组A[p..q]和A[q+1..r]都已排好序//该过程假设子数组A[p..q]和A[q+1..r]都已排好序//该过程假设子数组A[p..q]和A[q+1..r]都已排好序
1n1=q−p+11\ \ n1=q-p+11n1=q−p+1
2n2=r−q2\ \ n2=r-q2n2=r−q
3letL[1..n1+1]andR[1..n2+1]benewarrays//这里设置两个哨兵值，哨兵值的作用是为了表明一个子序列的元素都已取完3\ \ let L[1..n_1+1]\ and R[1..n_2+1]\ be\ new\ arrays\qquad //这里设置两个哨兵值，哨兵值的作用是为了表明一个子序列的元素都已取完3letL[1..n1+1]andR[1..n2+1]benewarrays//这里设置两个哨兵值，哨兵值的作用是为了表明一个子序列的元素都已取完
4fori=1ton14\ \ for\ i=1\ to\ n_14fori=1ton1
5L[i]=A[p+i−1]5\ \qquad L[i]=A[p+i-1]5L[i]=A[p+i−1]
6forj=1ton26\ \ for\ j=1\ to\ n_26forj=1ton2
7R[j]=A[q+j]7\ \qquad R[j]=A[q+j]7R[j]=A[q+j]
8L[n1+1]=∞//哨兵值8\ \ L[n_1+1]=\infty\qquad //哨兵值8L[n1+1]=∞//哨兵值
9R[n2+1]=∞//哨兵值9\ \ R[n_2+1]=\infty\qquad //哨兵值9R[n2+1]=∞//哨兵值
10i=110\ \ i=110i=1
11j=111\ \ j=111j=1
12fork=ptor12\ \ for\ k=p\ to\ r12fork=ptor
13ifL[i]≤R[j]13\ \qquad if\ L[i]\leq R[j]13ifL[i]≤R[j]
14A[k]=L[i]14\ \qquad \qquad A[k]=L[i]14A[k]=L[i]
15i=i+115\ \qquad \qquad i=i+115i=i+1
16elseA[k]=R[j]16\ \qquad else A[k]=R[j]16elseA[k]=R[j]
17j=j+117\ \qquad \qquad j=j+117j=j+1
MERGE−SORT(A,p,r)MERGE-SORT(A,p,r)MERGE−SORT(A,p,r)
1ifp<r:1\ if\ p<r:1ifp<r:
2q=⌊(p+r)/2⌋2\qquad q=\lfloor {(p+r)/2}\rfloor2q=⌊(p+r)/2⌋
3MERGE−SORT(A,p,q)3\qquad MERGE-SORT(A,p,q)3MERGE−SORT(A,p,q)
4MERGE−SORT(A,q+1,r)4\qquad MERGE-SORT(A,q+1,r)4MERGE−SORT(A,q+1,r)
5MERGE(A,p,q,r)5\qquad MERGE(A,p,q,r)5MERGE(A,p,q,r)
4.时间复杂度
最坏情况的运行时间
T(n)={Θ(1)n=12T(n/2)+Θ(n)n>1T(n)=\begin{cases} \Theta(1)& \text{n=1}\\ 2T(n/2)+\Theta(n)& \text{n>1} \end{cases}T(n)={Θ(1)2T(n/2)+Θ(n)n=1n>1
注释：
Θ(1)表示常量时间\Theta(1)表示常量时间Θ(1)表示常量时间
Θ(n)表示n的线性时间\Theta(n)表示n的线性时间Θ(n)表示n的线性时间
为了求出T(n)T(n)T(n)的具体值，采用递归树的方法。
将上述公式写成如下形式：
T(n)={cn=12T(n/2)+cnn>1T(n)=\begin{cases} c& \text{n=1}\\ 2T(n/2)+cn& \text{n>1} \end{cases}T(n)={c2T(n/2)+cnn=1n>1
在计算机中，lgn的底数是2在计算机中，\lg n的底数是2在计算机中，lgn的底数是2
T(n)=Θ(nlgn)T(n)=\Theta(n\lg n)T(n)=Θ(nlgn)
5.代码（python）
###合并排序import mathimport numpy as npmath.ceil(2.3) #向上取整：大于等于x的最小整数math.floor(2.3) #向下取整数：小于等于x 的最大整数def merge_sorted(seq,p,r): #A是数组，p，r是下标if p<r:q=math.floor((r+p)/2)merge_sorted(seq,p,q)merge_sorted(seq,q+1,r)merge(seq,p,q,r) def merge(seq,p,q,r):n1=q+1-pn2=r-qL=np.zeros(n1+1) R=np.zeros(n2+1)L[n1]=seq.max()+1 #数组的下标是以0开头的R[n2]=seq.max()+1for i in range(n1):L[i]=seq[p+i]for j in range(n2):R[j]=seq[q+1+j]i,j=0,0for k in range(p,r+1): if L[i]<=R[j]:seq[k]=L[i]i+=1else:seq[k]=R[j]j+=1
运行过程：
三、快速排序
1.问题
排序数组A[p..r]排序数组A[p..r]排序数组A[p..r]
2.思路
———分治法的思想
分解：数组A[p…r]被划分为两个（可能为空）子数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的每一个元素都小于等于A[q],而A[q]也小于等于A[q+1…r]中的每个元素。
解决：通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序。
合并：因为子数组都是原址排序的，所以不需要合并操作：数组A[p…r]已经有序。
3.伪代码
QUICKSORT(A,p,r)QUICKSORT(A,p,r)QUICKSORT(A,p,r)
1ifp<r1\ if\ p<r1ifp<r
2q=PARTITION(A,p,r)2\qquad q=PARTITION(A,p,r)2q=PARTITION(A,p,r)
3QUICKSORT(A,p,q−1)3\qquad QUICKSORT(A,p,q-1)3QUICKSORT(A,p,q−1)
4QUICKSORT(A,q+1,r)4\qquad QUICKSORT(A,q+1,r)4QUICKSORT(A,q+1,r)
PARTITION(A,p,r)PARTITION(A,p,r)PARTITION(A,p,r)
//关键部分，实现了对子数组A[p..r]的原址排序//关键部分，实现了对子数组A[p..r]的原址排序//关键部分，实现了对子数组A[p..r]的原址排序
1x=A[r]1\ x=A[r]1x=A[r]
//x=A[r]//x=A[r]//x=A[r]作为主元，即围绕它来划分子数组A[p..r]A[p..r]A[p..r]
2i=p−12\ i=p-12i=p−1
3forj=ptor−13\ for\ j=p\ to\ r-13forj=ptor−1
4ifA[j]≤x4\qquad if\ A[j]\leq x4ifA[j]≤x
5i=i+15\qquad \qquad i=i+15i=i+1
6exchangeA[i]withA[j]6\qquad \qquad exchange\ A[i] with\ A[j]6exchangeA[i]withA[j]
7exchangeA[i+1]withA[r]7\ exchange\ A[i+1]\ with\ A[r]7exchangeA[i+1]withA[r]
8returni+18\ return\ i+18returni+1
运行过程：
快速排序的随机化版本
从A[p…r]中随机选择一个元素作为主元
RANDOMIZEDPARTITION(A,p,r)RANDOMIZED\ PARTITION(A,p,r)RANDOMIZEDPARTITION(A,p,r)
1i=RANDOM(p,r)1\ i=RANDOM(p,r)1i=RANDOM(p,r)
//////可以保证主元素x=A[r]x=A[r]x=A[r]是等概率的从子数组的r-p+1个元素中选取的
2exchangeA[r]withA[i]2\ exchange\ A[r]\ with\ A[i]2exchangeA[r]withA[i]
3returnPARTITION(A,p,r)3\ return\ PARTITION(A,p,r)3returnPARTITION(A,p,r)
RANDOMIZEDQUICKSORT(A,p,r)RANDOMIZED\ QUICKSORT(A,p,r)RANDOMIZEDQUICKSORT(A,p,r)
1ifp<r1\ if\ p<r1ifp<r
2q=RANDOMIZEDPARTITION(A,p,r)2\qquad q=RANDOMIZED\ PARTITION(A,p,r)2q=RANDOMIZEDPARTITION(A,p,r)
3RANDOMIZEDQUICKSORT(A,p,q−1)3\qquad RANDOMIZED\ QUICKSORT(A,p,q-1)3RANDOMIZEDQUICKSORT(A,p,q−1)
4RANDOMIZEDQUICKSORT(A,q+1,r)4\qquad RANDOMIZED\ QUICKSORT(A,q+1,r)4RANDOMIZEDQUICKSORT(A,q+1,r)
4.时间复杂度
最坏运行情况
Θ(n2)\Theta(n^2)Θ(n2)
平均运行时间
Θ(nlgn)\Theta(n\lg n)Θ(nlgn)
5.代码（python）
###快速排序def quicksort(A,p,r):if p<r:q=partition(A,p,r)quicksort(A,p,q-1)quicksort(A,q+1,r)def partition(A,p,r):x=A[r]i=p-1for j in range(p,r): #range含头不含尾if A[j]<=x:i+=1inter=A[i]A[i]=A[j]A[j]=intermid=A[i+1]A[i+1]=A[r]A[r]=midreturn i+1
四、堆排序
1.堆的补充
(1)堆的定义
（二叉）堆是一个数组，可以被看成是一个近似的完全二叉树。树上的每一个节点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左向右填充的。
(2)堆的属性
表示堆的数组A包括两个属性：A.lengthA.lengthA.length表示数组元素的个数，A.heapsizeA.heapsizeA.heapsize表示有多少个堆元素存储在该数组中。也就是说，虽然A[1..A.length]A[1..A.length]A[1..A.length]可能都存有数据，但是A[1..A.heapsize]A[1..A.heapsize]A[1..A.heapsize]中存放的是堆的有效元素。0≤A.heapsize≤A.length0\leq A.heapsize\leq A.length0≤A.heapsize≤A.length
(3)堆的要素
a. 每个结点圆圈内部的数字是它所存储的数据，节点上方的数字是它在数组中相应的下标
b. 树的根结点是A[1]
c. 父结点和左孩子，右孩子
给定一个结点的下标，可以求出父结点、左孩子和右孩子的下标。
PARENT(i)PARENT(i)PARENT(i)
1return⌊i/2⌋1\quad return\ \lfloor{i/2}\rfloor1return⌊i/2⌋
LEFT(i)LEFT(i)LEFT(i)
1return2i1\quad return\ 2i1return2i
RIGHT(i)RIGHT(i)RIGHT(i)
2return2i+12\quad return\ 2i+12return2i+1
d. 没有子结点的结点称为叶子
e. 一个堆中的结点的高度就是该结点到叶结点最长简单路径上边的树目
f. 堆的高度定义为根结点的高度
g. 含n个元素的堆的高度为Θ(lgn)\Theta(\lg n)Θ(lgn)
证明
在高度为h的堆中，
元素个数最多是底层全满的时候，即
20+21+⋯+2h=21+h−1\ \quad 2^0+2^1+\cdots+2^h=2^{1+h}-120+21+⋯+2h=21+h−1
元素个数最少是底层只有一个结点的时候，即
20+21+⋯+2h−1+1=2h\ \quad 2^0+2^1+\cdots+2^{h-1}+1=2^h20+21+⋯+2h−1+1=2h
假设含n个元素的堆的高度为h,那么有
2h≤n≤21+h−1⇒h≤lgn<h+1⇒h=⌊lgn⌋\ \quad 2^h\leq n\leq 2^{1+h}-1 \\ \ \qquad \Rightarrow h\leq lgn<h+1\\ \ \qquad \Rightarrow h=\lfloor {\lg n} \rfloor2h≤n≤21+h−1⇒h≤lgn<h+1⇒h=⌊lgn⌋
h.当用数组表示存储n个元素的堆时，叶结点下标分别为⌊n/2⌋+1,⌊n/2⌋+2,⋯,n\lfloor{n/2}\rfloor+1,\lfloor{n/2}\rfloor+2,\cdots,n⌊n/2⌋+1,⌊n/2⌋+2,⋯,n
证明
根据二叉堆的性质，某结点下标为i(非根结点)，那么其父结点下标为⌊i/2⌋\lfloor{i/2}\rfloor⌊i/2⌋，所以最后一个叶结点的父结点下标为⌊n/2⌋\lfloor{n/2}\rfloor⌊n/2⌋，因此下标从⌊n/2⌋+1\lfloor{n/2}\rfloor+1⌊n/2⌋+1开始到n都是叶结点。
(4)最大堆的例子
如上图，该树的高度是3，下标为4（值为8）的结点的高度为1。
(5)堆的分类：最大堆和最小堆
a. 最大堆性质：除了根以外的所有结点iii都要满足：
A[PARENT(i)]≥A[i]\ \qquad A[PARENT(i)]\geq A[i]A[PARENT(i)]≥A[i]
也就是说，最大堆中的最大元素存放在根结点中，并且，在任一子树中，该子树所包含的所有结点的值都不大于该子树根结点的值。
b. 最小堆性质：除了根以外的所有结点iii都要满足：
A[PARENT(i)]≤A[i]\ \qquad A[PARENT(i)]\leq A[i]A[PARENT(i)]≤A[i]
最小堆中的最小元素存放在根结点中。
c. 堆排序算法中使用的是最大堆；最小堆通常用于构造优先队列
2.问题
对A[1..n]排序，其中n=A.length对A[1..n]排序，其中n=A.length对A[1..n]排序，其中n=A.length
3.伪代码
HEAPSORT(A)1BUILD−MAX−HEAP(A)//利用BUILD−MAX−HEAP将输入数组A[1..n]建成最大堆，其中n=A.length。因为数组中(最大堆)的最大元素在根结点A[1]中，故将其与A[n]互换，放到正确的位置。这时，从堆中去掉结点n(可以通过减少A.heap−size的值来实现)，在剩余的结点中，原来根的孩子结点仍然是最大堆，而新的根结点可能违背了最大堆的性质，为了维护最大堆的性质，调用MAX−HEAPIFY(A,1)，从而在A[1..n−1]上构造一个新的最大堆。重复下去。2fori=A.lengthdown23exchangeA[1]withA[i]4A.heap−size=A.heap−size−15MAX−HEAPIFY(A,1)HEAPSORT(A)\\ 1\ BUILD-MAX-HEAP(A)\\ //利用BUILD-MAX-HEAP将输入数组A[1..n]建成最大堆，其中n=A.length。因为数组中(最大堆)的最大元素在根结点A[1]中，故将其与A[n]互换，放到正确的位置。这时，从堆中去掉结点n(可以通过减少A.heap-size的值来实现)，在剩余的结点中，原来根的孩子结点仍然是最大堆，而新的根结点可能违背了最大堆的性质，为了维护最大堆的性质，调用MAX-HEAPIFY(A,1)，从而在A[1..n-1]上构造一个新的最大堆。重复下去。\\ 2\ for\ i=A.length\ down\ 2\\ 3\ \qquad exchange\ A[1]\ with\ A[i]\\ 4\ \qquad A.heap-size=A.heap-size-1\\ 5\ \qquad MAX-HEAPIFY(A,1)HEAPSORT(A)1BUILD−MAX−HEAP(A)//利用BUILD−MAX−HEAP将输入数组A[1..n]建成最大堆，其中n=A.length。因为数组中(最大堆)的最大元素在根结点A[1]中，故将其与A[n]互换，放到正确的位置。这时，从堆中去掉结点n(可以通过减少A.heap−size的值来实现)，在剩余的结点中，原来根的孩子结点仍然是最大堆，而新的根结点可能违背了最大堆的性质，为了维护最大堆的性质，调用MAX−HEAPIFY(A,1)，从而在A[1..n−1]上构造一个新的最大堆。重复下去。2fori=A.lengthdown23exchangeA[1]withA[i]4A.heap−size=A.heap−size−15MAX−HEAPIFY(A,1)
MAX−HEAPIFY(A,i)MAX-HEAPIFY(A,i)MAX−HEAPIFY(A,i) //保持最大堆的性质
//输入一个数组A和一个下标i，使得以下标i为根结点的子树遵循最大堆的性质假定根结点为LEFT(i)和RIGHT(i)的二叉树都是最大堆//输入一个数组A和一个下标i，使得以下标i为根结点的子树遵循最大堆的性质\\ 假定根结点为LEFT(i)和RIGHT(i)的二叉树都是最大堆//输入一个数组A和一个下标i，使得以下标i为根结点的子树遵循最大堆的性质假定根结点为LEFT(i)和RIGHT(i)的二叉树都是最大堆
1l=LEFT(i)2r=RIGHT(i)3ifl≤A.heap−sizeandA[l]>A[i]4largest=l5elselargest=i6ifr≤A.heap−sizeandA[r]>A[largest]7largest=r1\ l=LEFT(i)\\ 2\ r=RIGHT(i)\\ 3\ if\ l\leq A.heap-size\ and\ A[l]>A[i]\\ 4\ \quad largest=l\\ 5\ else\ largest=i\\ 6\ if\ r\leq A.heap-size\ and\ A[r]>A[largest]\\ 7\ \quad largest=r1l=LEFT(i)2r=RIGHT(i)3ifl≤A.heap−sizeandA[l]>A[i]4largest=l5elselargest=i6ifr≤A.heap−sizeandA[r]>A[largest]7largest=r
//从A[i],A[LEFT],A[RIGHT]中选出最大的，将其下标存储在largest中//从A[i],A[LEFT],A[RIGHT]中选出最大的，将其下标存储在largest中//从A[i],A[LEFT],A[RIGHT]中选出最大的，将其下标存储在largest中
8iflargest≠i9exchangeA[i]withA[largest]10MAX−HEAPIFY(A,largest)8\ if\ largest\neq i\\ 9\ \quad exchange\ A[i]\ with\ A[largest]\\ 10\ \quad MAX-HEAPIFY(A,largest)8iflargest=i9exchangeA[i]withA[largest]10MAX−HEAPIFY(A,largest)
//如果A[i]是最大的，那么以i为根结点的子树已经是最大堆，程序结束；如果最大元素是i的某个孩子结点，则交换A[i]和A[largest]的值，从而使i及其孩子都满足最大堆的性质。在交换后，下标为largest的结点的值是原来的A[i],这时以该结点为根的子树又可能会违反最大堆的性质，故递归调用MAX−HEAPIFY//如果A[i]是最大的，那么以i为根结点的子树已经是最大堆，程序结束；如果最大元素是i的某个孩子结点，则交换A[i]和A[largest]的值，从而使i及其孩子都满足最大堆的性质。在交换后，下标为largest的结点的值是原来的A[i],这时以该结点为根的子树又可能会违反最大堆的性质，故递归调用MAX-HEAPIFY//如果A[i]是最大的，那么以i为根结点的子树已经是最大堆，程序结束；如果最大元素是i的某个孩子结点，则交换A[i]和A[largest]的值，从而使i及其孩子都满足最大堆的性质。在交换后，下标为largest的结点的值是原来的A[i],这时以该结点为根的子树又可能会违反最大堆的性质，故递归调用MAX−HEAPIFY
BUILD−MAX−HEAP(A)BUILD-MAX-HEAP(A)BUILD−MAX−HEAP(A)//建堆
//用自底向上的方法把一个大小为n=A.length的数组A[1..n]转换成最大堆//用自底向上的方法把一个大小为n=A.length的数组A[1.. n]转换成最大堆//用自底向上的方法把一个大小为n=A.length的数组A[1..n]转换成最大堆
//子数组A[⌊n/2⌋+1⋯n]中的元素都是树的叶结点。每个叶结点都可以看成是只包含一个元素的堆//子数组A[\lfloor{n/2}\rfloor+1\cdots\ n]中的元素都是树的叶结点。每个叶结点都可以看成是只包含一个元素的堆//子数组A[⌊n/2⌋+1⋯n]中的元素都是树的叶结点。每个叶结点都可以看成是只包含一个元素的堆
1A.heap−size=A.length2fori=⌊A.length/2⌋downto1//对树中的非叶结点调用MAX−HEAPIFY3MAX−HEAPIFY(A,i)1\ A.heap-size=A.length\\ 2\ for\ i=\lfloor{A.length/2}\rfloor\ downto\ 1\\ //对树中的非叶结点调用MAX-HEAPIFY\\ 3\ \quad MAX-HEAPIFY(A,i)1A.heap−size=A.length2fori=⌊A.length/2⌋downto1//对树中的非叶结点调用MAX−HEAPIFY3MAX−HEAPIFY(A,i)
4.代码（python）
###堆排序import math##结点的下标是以1开头的，列表的下标是以0开头的##要想在一个函数中调用另一个函数的变量，需要把该变量设置为全局变量，##如何在函数中修改全局变量：在函数体中用global声明，否则是局部变量。##1.给定某个结点的下标i，求父结点，左孩子和右孩子的下标def parent(i): #给定某个非根结点的下标i，求父结点的下标（这里的下标是以0开头的）return math.floor((i-1)/2) #math.floor(x)向下取整：小于等于x的最大整数#math.ceil(x)向上取整：大于等于x的最小整数def left(i): #给定某个结点的下标i，求左儿子的下标（这里的下标是以0开头的）return 2*i+1def right(i): #给定某个结点的下标i，求右儿子的下标（这里的下标是以0开头的）return 2*i+2 ##2.保持最大堆的性质def max_heapify(A,i): #给定某个结点的下标i，将以该结点为根结点的子树保持最大堆的性质（这里的下标是以0开头的）l=left(i) r=right(i)if l<=heap_size_A and A[l]>A[i]: #这里heap_size_A是列表A索引的最大值largest=l else:largest=iif r<=heap_size_A and A[r]>A[largest]:largest=rif largest != i:mid=A[i]A[i]=A[largest]A[largest]=midmax_heapify(A,largest)##3.建堆def build_max_heap(A):heap_size_A=len(A)-1 #局部变量 for i in range(math.floor((heap_size_A-1)/2),-1,-1):max_heapify(A,i)##4.堆排序def heap_sort(A):build_max_heap(A)for i in range(len(A)-1,0,-1):mid=A[i]A[i]=A[0]A[0]=midglobal heap_size_A #全局变量heap_size_A-=1max_heapify(A,0)A=[4,1,3,2,16,9,10,14,8,7] heap_size_A=len(A)-1 heap_sort(A)
5.时间复杂度
Θ(nlgn)\Theta(n\lg n)Θ(nlgn)
五、计数排序
1.问题
数组A[1..n]的n个元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。对A[1..n]排序数组A[1..n]的n个元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。对A[1..n]排序数组A[1..n]的n个元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。对A[1..n]排序
2.思路
对每一个输入元素xxx, 确定小于x 的元素个数，利用这一信息，直接把xxx放在它在输出数组中的位置。
3.伪代码
COUNTING−SORT(A,B,k)COUNTING-SORT(A,B,k)COUNTING−SORT(A,B,k)
//B[1..n]存放排序的输出，C[0..k]提供临时存储空间//B[1..n]存放排序的输出，C[0..k]提供临时存储空间//B[1..n]存放排序的输出，C[0..k]提供临时存储空间
1letC[0..k]beanewarray2fori=0tok3C[i]=04forj=1toA.length5C[A[j]]=C[A[j]]+16//C[i]nowcontainsthenumberofelementsequaltoI7fori=1tok8C[i]=C[i]+C[i−1]9//C[i]nowcontainsthenumberofelementslessthanorequaltoi.10forj=A.lengthdownto111B[C[A[j]]]=A[j]12C[A[j]]=C[A[j]]−11\ let\ C[0..k]\ be\ a\ new\ array\\ 2\ for\ i=0\ to\ k\\ 3\ \qquad C[i]=0\\ 4\ for\ j=1\ to\ A.length\\ 5\ \qquad C[A[j]]=C[A[j]]+1\\ 6\ //C[i]\ now\ contains\ the\ number\ of\ elements\ equal\ to\ I\\ 7\ for\ i=1\ to\ k\\ 8\ \qquad C[i]=C[i]+C[i-1]\\ 9//C[i]\ now\ contains\ the\ number\ of\ elements\ less\ than\ or\ equal\ to\ i.\\ 10\ for\ j=A.length\ downto\ 1\\ 11\ \qquad B[C[A[j]]]=A[j]\\ 12\ \qquad C[A[j]]=C[A[j]]-11letC[0..k]beanewarray2fori=0tok3C[i]=04forj=1toA.length5C[A[j]]=C[A[j]]+16//C[i]nowcontainsthenumberofelementsequaltoI7fori=1tok8C[i]=C[i]+C[i−1]9//C[i]nowcontainsthenumberofelementslessthanorequaltoi.10forj=A.lengthdownto111B[C[A[j]]]=A[j]12C[A[j]]=C[A[j]]−1
4.代码（python）
###计数排序##数组A[1..n]的n个元素中的每一个都是在0到k区间内的一个整数，其中k为某个整数。def counting_sort(A):B=[0 for i in range(len(A))] #存放排序的输出k=max(A)C=[0 for i in range(k+1)] #记录A中个元素所出现的次数for j in range(len(A)):C[A[j]]+=1#C[i]是i在A中出现的次数for i in range(1,k+1):C[i]=C[i-1]+C[i] #C[i]是在A中小于或等于i的元素的个数 (累加)for j in range(len(A)-1,-1,-1):B[C[A[j]]-1]=A[j] #列表索引以0开头的C[A[j]]-=1return B
5.时间复杂度
Θ(n+k)\Theta(n+k)Θ(n+k)
