算法导论*讲了五种排序，分别是插入排序，归并排序，堆排序，快速排序和计数排序。
（1）插入排序
插入排序的最坏情况运行时间为θ（n^2），但其算法的内循环是紧密的，对于小规模输入来说是一个快速的原地排序算法
伪代码如下：
Insertion sort
Insertion sort(A,n) //sort A[1,..n]
for j←2 to n
do key←A[j]
i←j-1
while i>0 and A[i]>key
do A[i+1]←A[i]
i←i-1
A[i+1]←key
c语言程序代码如下：
void insertion(int aa[],int n)
{
int key,i;
for(int j=2;j<=n;j++)
{
key=aa[j];
i=j-1;
while(i>0&&aa[i]>key)
{
aa[i+1]=aa[i];
i--;
}
aa[i+1]=key;
}
}
（2）归并排序
归并排序有着较好的渐进运行时间θ（nlgn）,但其中的MERGE程序不在原地操作
伪代码如下：
MERGE(A,p,q,r) n1←q-p+1 n2←r-q create arrays L[1...n1+1] and R[1...n2+1] for i←1 to n1 do L[i]←A[p+i-1] for j←1 to n2 do R[j]←A[q+j] L[n1+1]←∞ R[n2+1]←∞ i←1 j←1 for k←p to r do if L[i]<=R[j] then A[k]←L[i] i←i+1 else A[k]←R[j] j←j+1 MERGE-SORT(A,p,r) if p<r then q←(p+r)/2 MERGE_SORT(A,p,q) MERGE-SORT(A,q+1,r) MERGE(A,p,q,r)
c语言代码如下：
void merge(int a[],int p,int q,int r)
{
int n1=0,n2=0;
n1=q-p+1;
n2=r-q;
int *L=new int[n1+1];
int *R=new int[n2+1];
for(int i=0;i<n1;i++)
L[i]=a[p+i];
for(int j=0;j<n2;j++)
R[j]=a[q+j+1];
i=0;
j=0;
L[n1]=2147483647;
R[n2]=2147483647;
for(int k=p;k<=r;k++)
{
if(L[i]<=R[j])
{
a[k]=L[i];
i++;
}
else
{
a[k]=R[j];
j++;
}
}
delete[] L;
delete[] R;
}
void mergesort(int a[],int p,int r)
{
if( p<r)
{
int q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
}
}
（3）堆排序
堆排序要用到叫堆的数据结构，它可以在O(nlgn)时间内对n个数进行原地排序。
伪代码如下
表示堆的数组A是一个具有两个属性的对象：length[A]是数组中数组中的元素个数，heap-size[A]是存放在A中的堆的元素的元素个数，就是说，虽然A[1...length[A]]中都可以包含有效值，但A[heap-size[A]]之后的元素都不属于相应的堆，此处heap-size[A]<=length[A]。树的根为A[1]，但定了某个节点的下标i，其父节点PARENT(i),左儿子LEFT(i)和右儿子RIGHT(i)的下标都可以简单的计算出来
伪代码如下：
MAX_HEAPIFY(A,i)
l←LEFT(i)
r←RIGHT(i)
if l<=heap-size[A] and A[l]>A[i]
then largest←l
else largest←r
if r<=heap-size[A] and A[r]>A[largest]
then largest←r
if largest!=i
then exchange A[i]←→A[;argest]
MAX-HEAPIFY(A,largest)
BUILD-MAX-HEAP(A)
heap-size[A]←length[A]
for i←length[A]/2 downto 1
do MAX-HEAPIFY(A,i)
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i←length[A] downto 2
do exchange A[1]←→A[i]
heap-size[A]←heap-size[A]-1
MAX-HEAPIFY(A,1)
c语言代码如下：
int heapsize;
void maxheapify(int a[],int i)
{
int l=0,r=0,largest=0,ex=0;
l=2*i+1,r=2*i+2;
if(a[l]>a[i]&&l<=heapsize)
largest=l;
else
largest=i;
if (r<=heapsize&&a[r]>a[largest])
largest=r;
if (largest!=i)
{
ex=a[i];
a[i]=a[largest];
a[largest]=ex;
maxheapify(a,largest);
}
}
void buildmaxheap(int a[],int n)
{
heapsize=n-1;
for(int t=(n/2-1);t>=0;t--)
maxheapify(a,t);
}
void heapsort(int a[],int q)
{
int change=0;
buildmaxheap(a,q);
for(int j=q-1;j>=1;j--)
{
change=a[0];
a[0]=a[j];
a[j]=change;
heapsize--;
maxheapify(a,0);
}
}
（4）快速排序
快速排序是一种对n个数进行原地排序的算法，但是他的最坏情况运行时间为θ（n^2）.他的平均运行时间是θ（n*lgn）
伪代码如下：
QUICKSORT(A,p,r)
if p<r
then q←PARTITION(A,p,r)
QUICKSORT(A,r,q-1)
QUICKSORT(A,p+1,r)
PARTITION(A,p,r)
x←A[r]
i←p-1
for j←p to r-1
do if A[j]<=x
then i←i+1
exchange A[i]←→A[j]
exchange A[i+1]←→A[r]
return i+1
c语言代码如下：
int partition(int a[],int p,int r)
{
int i=p-1;
int x=a[r];
int ex1=0,ex2=0;
for(int j=p;j<r;j++)
{
if(a[j]<=x)
{
i++;
ex1=a[i];
a[i]=a[j];
a[j]=ex1;
}
}
ex2=a[i+1];
a[i+1]=a[r];
a[r]=ex2;
return i+1;
}
void quicksort(int a[],int p,int r)
{
int q=0;
if(p<r)
{
q=partition(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}
快速排序的随机化伪代码如下：
RANDOMIZED-PARTITION(A,p,r) i←RANDOM(p,r) exchange A[i]←→A[r] reuturn PARTITION(A,p,r) RANDOMIZED-QUICKSORT(A.p,r) if p<r then q←RANDOMZIED-PARTITION(A,p,r) RANDOMZIED-PARTITION(A,p,q-1) RANDOMZIED-PARTITION(A,q+1,r)
c语言代码如下
int partition(int a[],int p,int r)
{
int i=p-1;
int x=a[r];
int ex1=0,ex2=0;
for(int j=p;j<r;j++)
{
if(a[j]<=x)
{
i++;
ex1=a[i];
a[i]=a[j];
a[j]=ex1;
}
}
ex2=a[i+1];
a[i+1]=a[r];
a[r]=ex2;
return i+1;
}
int randomizedpartition(int a[],int p,int r)
{
int ex3=0,i=0;
time_t t;
srand((unsigned) time(&t));
i=rand()%(r-p+1)+p;
ex3=a[i];
a[i]=a[r];
a[r]=ex3;
return partition(a,p,r);
}
void randomzedquicksort(int a[],int p,int r)
{
int q=0;
if(p<r)
{
q=randomizedpartition(a,p,r);
randomzedquicksort(a,p,q-1);
randomzedquicksort(a,q+1,r);
}
}
（5）计数排序
计数排序假定输入树取自集合{0,1,2，...，k}。通过利用数组下标来确定元素的相对次序，该算法可在θ(k+n)时间内完成。
伪代码如下：
COUNTING-SORT(A,B,k)
for i←0 to k
do C[i]←0
for j←1 to length[A]
do C[A[j]]←C[A[j]]+1
//C[j]包含等于i的元素个数
for i←1 to k
do C[i]←C[i]+C[i-1]
//C[i]包含小于或等于i的元素个数
for j←length[A] downto 1
do B[C[A[j]]]←A[j]
C[A[j]]←C[A[j]]-1
c语言代码如下：
int max(int a[],int k)
{
int maax=0;
for(int u=0;u<k;u++)
{
if(maax<a[u])
maax=a[u];
}
return maax;
}
void couningsort(int a[],int k)
{
int m=max(a,k);
int *b=new int[k+1];
int *c=new int[m+1];
for(int j=0;j<k;j++)
b[j]=0;
for(int i=0;i<=m;i++)
c[i]=0;
for( j=0;j<k;j++)
c[a[j]]++;
for( i=1;i<=m;i++)
c[i]=c[i]+c[i-1];
for(j=0;j<k;j++)
{
b[c[a[j]]-1]=a[j];
c[a[j]]--;
}
for(j=0;j<k;j++)
a[j]=b[j];
delete[] b;
delete[] c;
}