这篇文章包含了插入排序，希尔排序，堆排序，归并排序和快速排序，是前几篇文章的集合。
一共包括三个文件
sort.h
sort.cpp
main.cpp
1.main.cpp
#include <iostream>
#include "sort.h"
using namespace std; int main()
{
\\test code
return ;
}
2.sort.h
#ifndef SORT_H_
#define SORT_H_
void intersort(int *nums,int n);
void shellsort(int *nums,int n);
void percdown(int *num,int p,int n);
void heapsort(int *nums,int n);
void mergesort(int *nums,int n);
void msort(int *nums,int*tmp,int lp,int rp);
void merge(int *nums,int *tmp,int lp,int rp,int over);
void swap(int &m,int &n);
int mid3(int *nums,int left,int right);
void qs(int*nums,int left,int right);
void quicksort(int *nums,int n);
#endif // SORT_H_
3.sort.cpp
#include "sort.h"
#include<iostream> void intersort(int *nums,int n)
{
int i,j;
int tmp;
for(i=;i<n;i++)
{
tmp=nums[i];
for(j=i;j>&&tmp<nums[j-];j--)
nums[j]=nums[j-];
nums[j]=tmp;
}
} void shellsort(int *nums,int n)
{
int gap,i,j;
int tmp;
for(gap=n/;gap>;gap/=)
{
for(i=gap;i<n;i++)
{
tmp=nums[i];
for(j=i;j>;j-=gap)
if(tmp<nums[j-gap])
nums[j]=nums[j-gap];
else
break;
nums[j]=tmp;
}
}
} void heapsort(int *nums,int n)
{
int i;
for(i=n/;i>=;i--)
percdown(nums,i,n);
for(i=n-;i>;i--)
{
nums[]^=nums[i];
nums[i]^=nums[];
nums[]^=nums[i];
percdown(nums,,i);
}
}
void percdown(int *nums,int p,int n)
{
int tmp;
int child;
for(tmp=nums[p];*p+<n;p=child)
{
child=*p+;
if(*p+!=n&&nums[*p+]>nums[child])
child++;
if(nums[child]>tmp)
nums[p]=nums[child];
else
break;
}
nums[p]=tmp; } void mergesort(int *nums,int n)
{
int *tmp=new int[n];
if(tmp)
{
msort(nums,tmp,,n-);
delete[]tmp;
}
}
void msort(int *nums,int*tmp,int lp,int rp)
{
int center=(lp+rp)/;
if(lp<rp)
{
msort(nums,tmp,lp,center);
msort(nums,tmp,center+,rp);
merge(nums,tmp,lp,center+,rp);
}
}
void merge(int *nums,int *tmp,int lp,int rp,int over)
{
int i=lp,j=rp,p=lp;
while(i<rp&&j<=over)
{
if(nums[i]<nums[j])
tmp[p++]=nums[i++];
else
tmp[p++]=nums[j++];
}
while(i<=rp-)
tmp[p++]=nums[i++];
while(j<=over)
tmp[p++]=nums[j++];
while(lp<=over)
{
nums[lp]=tmp[lp];
lp++;
}
} void quicksort(int *nums,int n)
{
qs(nums,,n-);
}
void qs(int*nums,int left,int right)
{
int pv;
int i,j;
int cutoff=;
if(left+cutoff<=right)
{
pv=mid3(nums,left,right);
i=left;
j=right-;
while()
{
while(nums[++i]<pv);
while(nums[--j]>pv);
if(i<j)
swap(nums[i],nums[j]);
else
break;
}
swap(nums[i],nums[right-]);
qs(nums,left,i);
qs(nums,i+,right);
}
else
intersort(nums+left,right-left+);
}
int mid3(int *nums,int left,int right)
{
int center=(left+right)/;
if(nums[left]>nums[center])
swap(nums[left],nums[center]);
if(nums[left]>nums[right])
swap(nums[left],nums[right]);
if(nums[center]>nums[right])
swap(nums[center],nums[right]);
swap(nums[center],nums[right-]);
return nums[right-];
}
void swap(int &m,int &n)
{
m^=n;
n^=m;
m^=n;
}