[cpp]
template
void insertionSort(vector& a)
{
int j;
for(int p=1;p
{
Comparable tmp=a[p];
for(j=p;j>0&&tmp
a[j]=a[j-1];
a[j]=tmp;
}
}
有R个逆序，因此运行时间为O(R+N)。若逆序数为O(N)，则以线性时间运行。R为N(N-1)/4，因此为Ω(N^2).
2.希尔排序（有时也叫缩减增量排序）
a.希尔排序（基于插入排序，使用希尔增量）
[cpp]
template
void shellsort(vector& a)
{
for(int gap=a.size()/2;gap>0;gap/=2)
for(int i=gap;i
{
Comparable tmp=a[i];
int j=i;
for(;j>=gap&&tmp
a[j]=a[j-gap];
a[j]=tmp;
}
}
b.希尔排序（基于简单交换排序，使用希尔增量）
[cpp]
void shellsort(int v[],int n)//based on simple exchange sort
{
int gap,i,j,temp;
for(gap=n/2;gap>0;gap/=2)
for(i=gap;i
for(j=i-gap;j>=0&&v[j]>v[j+gap];j-=gap){
temp=v[j];
v[j]=v[j+gap];
v[j+gap]=temp;
}
}
使用希尔增量的希尔排序每一趟排序是插入排序或简单交换排序，因此最坏是O(N^2)的。
3.堆排序
[cpp]
inline int leftChild(int i)//root index is 0
{
return 2*i+1;
}
template
void percDown(vector& a,int i,int n)
{
int child;
Comparable tmp;
for(tmp=a[i];leftChild(i)
{
child=leftChild(i);
if(child!=n-1&&a[child]
child++;
if(tmp
a[i]=a[child];
else
break;
}
a[i]=tmp;
}
template
void heapsort(vector& a)
{
for(int i=a.size()/2;i>=0;i--)//buildHeap
percDown(a,i,a.size());
for(int j=a.size()-1;j>0;j--) //deleteMax
{
swap(a[0],a[j]);//通过最大堆将数组以递增序排列，可节省一个辅助数组。
percDown(a,0,j);
}
}
构建堆花费O(N)，然后执行N次deleteMax操作，每次花费O(log N)。因此总运行时间为O(N log N)。
4.归并排序
[cpp]
template
void merge(vector& a,vector&tmpArray,int leftPos,int rightPos,int rightEnd)
{
int leftEnd=rightPos-1;
int tmpPos=leftPos;
int numElements=rightEnd-leftPos+1;
while(leftPos<=leftEnd&&rightPos<=rightEnd)
{
if(a[leftPos]
tmpArray[tmpPos++]=a[leftPos++];
else
tmpArray[tmpPos++]=a[rightPos++];
}
while(leftPos<=leftEnd)
tmpArray[tmpPos++]=a[leftPos++];
while(rightPos<=rightEnd)
tmpArray[tmpPos++]=a[rightPos++];
for(int i=0;i
a[rightEnd]=tmpArray[rightEnd];
}
template
void mergeSort(vector& a,
vector& tmpArray,int left,int right)
{
if(left
{
int center=(left+right)/2;
mergeSort(a,tmpArray,left,center);
mergeSort(a,tmpArray,center+1,right);
merge(a,tmpArray,left,center+1,right);
}
}
template
void mergeSort(vector& a)
{
vector tmpArray(a.size());
mergeSort(a,tmpArray,0,a.size()-1);//单参驱动多参函数
}
O(N log N)。
5.快速排序
从左向右依次判断，取中间索引为分划枢纽：
[cpp]
//order v ascendent
void qsort(int v[],int left,int right)
{
int i,last;
void swap(int v[],int i,int j);
if(left>=right)
return;
swap(v,left,(left+right)/2);//the element to depart
last=left;//to v[0]
for(i=left+1;i<=right;i++)//depart