以上排序都属于内部排序， 希尔排序属于插入排序，堆排序属于选择排序，
对排序的各种实现：直接上代码：
#include <iostream>
#include <stdio.h>
using namespace std;
int a[1000];
long sum=0;
void swap(int x,int y)
{
int temp;
temp=a[x];
a[x]=a[y];
a[y]=temp;
}
void merge(int x,int y)//归并
{
int mid=(x+y)/2;int k=x;
int left[505];
int right[505];
int n1=mid-x+1;
int n2=y-mid;
for (int i=0;i<n1;i++)
{
left[i]=a[x++];
}
for (int j=0;j<n2;j++)
{
right[j]=a[x++];
}
i=j=0;
while(i<n1&&j<n2)
{
if (left[i]<right[j])
{
a[k++]=left[i++];
}
else
{
a[k++]=right[j++];
sum+=n1-i;//此处可以记录交换的次数
}
}
while (i<n1)
{
a[k++]=left[i++];
}
while (j<n2)
{
a[k++]=right[j++];
}
}
void mergesort(int x,int y)//时间复杂度是O(nlogn)
{
if (x<y)
{
int mid=(x+y)/2;
mergesort(x,mid);
mergesort(mid+1,y);
merge(x,y);
}
}
void insertsort(int n)//时间复杂度O(n^2)
{
int i,j,temp;
for (i=0;i<n;i++)
{
temp=a[i];
for (j=i;j>0&&a[j-1]>temp;j--)//在i元素前的所有比i大的元素向后移动一个位置 为i空出一个位置
{
a[j]=a[j-1];
}
a[j]=temp;
}
}
void quicksort(int x,int y)//时间复杂度O(nlogn)
{
if (x>=y) return ;
int sign=a[y];
int low=x-1;
int high=y;
while(low<high)
{
while (low<y&&a[++low]<sign);//low指针向后找到第一个比sign小的
while (high>0&&a[--high]>sign);//high指针向前找到第一个比sign大的
if (low<high) swap(low,high);
}
swap(y,low);
quicksort(x,low-1);
quicksort(low+1,y);
}
//堆是完全二叉树，子节点的父节点是(i-1)/2
//父节点的子节点是i*2+1,i*2+2
void heap(int x,int y)
{
int i,j;
int temp=a[x];
while (x<y/2)
{
int k=2*x+1;
if (k+1<y&&a[k]<a[k+1]) ++k;//在子节点中找一个大的与根值互换
if (temp>a[k]) break;
a[x]=a[k];
x=k;
}
a[x]=temp;
}
//堆的一个性质：最大元素在根处，最小元素是某个叶节点
void heapsort(int n)//最坏的情况下，时间复杂度O(nlogn)
{
int i;
int x=n/2-1;
for (i=x;i>=0;i--)//更新所有的根节点，使形成堆
{
heap(i,n);
}
for (i=n-1;i>0;i--)//堆排序 每次更新到最下面的是最大的树
{
swap(0,i);//0-i是具有堆性质
heap(0,i);
}
}
void shillsort(int n)
{
int i,j;
int t=1;
while (t<n/4) t=t*2+1;//设置增量
while (t>0)
{
for (i=t;i<n;i++)//对每一块排序
{
j=i;
int d=a[i];
while(j>=t&&a[j-t]>d)
{
a[j]=a[j-t];
j-=t;
}
a[j]=d;
}
t/=2;//增量变小(即合并过程)
}
}
int length(int n)
{
int i,l=1,p=10;
for (i=0;i<n;i++)
{
while(a[i]>=p)
{
p*=10;
l++;
}
}
return l;
}
//基数排序是稳定排序
void radixsort(int n)
{
int i,flag=1,j,k;
int len=length(n);//确定关键字的个数
int temp[1005];
int cnt[10];
for (i=0;i<len;i++)
{
for (j=0;j<10;j++)
{
cnt[j]=0;
}
for (j=0;j<n;j++)//按尾数确定分组(桶)
{
k=(a[j]/flag)%10;
cnt[k]++;
}
for(j=1;j<10;j++)
{
cnt[j]=cnt[j]+cnt[j-1];
}
for (j=n-1;j>=0;j--)//根据桶确定新的顺序
{
k=(a[j]/flag)%10;
cnt[k]--;
temp[cnt[k]]=a[j];
}
for (j=0;j<n;j++)
{
a[j]=temp[j];
}
flag*=10;//第一次从个位数排序，然后对十位数，以此类推、、、
}
}
int main()
{
//freopen("Input.txt","r",stdin);
int n;
while(cin>>n)
{
for (int i=0;i<n;i++)
{
cin>>a[i];
}
//mergesort(0,n-1);对两个有序序列进行归并的排序
//insertsort(n);把比i小的元素前移一个位置，然后插入i
//quicksort(0,n-1);左边都比右边小
//heapsort(n);确定堆，更新堆底元素
//shillsort(n); 以增量为分组排序
//radixsort(n);以关键字排序
for (int j=0;j<n;j++)
{
cout<<a[j]<<" ";
}
}
return 0;
}
注：选择排序在最好的情况下的时间复杂度是O(N)
关于几种排序的一个形象效果图地址：
http://www.cnblogs.com/wangfupeng1988/archive/2011/12/26/2302216.html