一个测试排序时间的程序
#include<iostream>
#include<iomanip>
using namespace std;
void Sort(int a[], int n);
int main()
{
const int N=100000;
int a[N], i;
srand(time(0));
for(i=0; i<N; i++) a[i] = rand() % 1000;
clock_t t0 = clock();
SelectSort(a, N);
clock_t t = clock();
// for(i=0; i<N; i++) cout << setw(5) << a[i];
cout<<"用时："<<t-t0<<"ms"<<endl;
return 0;
}
//一、插入排序
//1、直接插入排序。
void InsertSort(int a[], int n)
{
int i,j,temp;
for(i=1; i<n; i++)
{
temp = a[i];
j = i-1;
while(j>=0 && a[j]>temp)
{ a[j+1] = a[j]; j--; }
a[j+1] = temp;
}
}
//2、改进的插入排序（加上哨兵）
void InsertSort2(int a[], int n)
{
int i,j;
for (i=2; i<n; i++)
{
a[0] = a[i];
j = i-1;
while(a[j]>a[0]) { a[j+1] = a[j]; j--; }
a[j+1] = a[0];
}
}
//3、折半插入排序
void BinaryInsertSort(int a[], int n)
{
for (int i = 1; i < n; i++)
{
int temp = a[i];
int low = 0, high = i - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (temp < a[mid]) high = mid - 1;
else low = mid + 1;
}
for (int j = i-1; j >= low; j--) { a[j+1] = a[j]; }
a[low] = temp;
}
}
//4、希尔排序（缩小增量排序）
void ShellSort(int a[], int n)
{
int d = n/2;
while(d >= 1)
{
for(int i=d; i<n; i++)
{
int temp = a[i];
int j = i-d;
while(j>=0 && a[j]>temp)
{ a[j+d] = a[j]; j = j-d; }
a[j+d] = temp;
}
d = d/2;
}
}
-----
//5.插入排序
#include<iostream.h>
void isort(int*a,int size);
int main()
{
int array[]={55,2,6,4,32,12,9,73,26,37};
int len=sizeof(array)/sizeof(int); //元素个数
for(int i=0;i<size;i++) //原始顺序输出
cout<<a[i]<<",";
cout<<endl<<endl;
isort(array,len); //调用排序函数
}
isort(int a[],int size) //插入排序
{
int inserter,index;
for(int i=1;i<size;i++) //共执行 size-1 轮
{
inserter=a[i];
index=i-1;
while(index>=0&&inserter<a[index]) //寻找插入点
{
a[index+1]=a[index]; //后挪一个位置
index--;
}
a[index+1]=inserter; //插入
for(int j=0;j<size;j++) //比较一轮后就输出
{
cout<<a[j]<<",";
if(j==i) //已排序与为排序的分界线
cout<<'|';
}
cout<<endl;
}
}
//6.插入排序
template<class T> //插入
void Insert(const T&e,T*a,int i)
{
a[0]=e;
while(e<a[i])
{
a[i+1]=a[i];
i--;
}
a[i+1]=e;
}
template<class T> //排序
void TnsertionSort(T*a,const int n)
{
for(int j=2;j<=n;j++)
{
T temp=a[j];
Insert(temp,a,j-1);
}
}
//二、选择排序
//1、直接选择排序。
void SelectSort(int a[], int n)
{
int i,j,k,m;
for(i=0; i<n-1; i++)
{ m = a[i];
k = i;
for(j=i+1; j<n; j++)
if(a[j] < m)
{ m = a[j]; k = j; }
a[k] = a[i];
a[i] = m;
}
}
//3、堆排序
void HeapAjust(int a[], int s, int m)
{ //把数组a从s到m进行调整
int j = 2*s+1;
int x = a[s];
while( j <= m )
{ if( (j+1<=m) && (a[j+1] > a[j]) ) j++;
if( x >= a[j] ) break;
else
{ a[s] = a[j];
s = j;
j = 2*s + 1;
}
}
a[s] = x;
}
void HeapSort(int a[], int n)
{
for(int i=(n-2)/2; i>=0; i--) HeapAjust(a,i,n-1);
for(int i=n-1; i>0; i--)
{ int t = a[0]; a[0] = a[i]; a[i] = t;
HeapAjust(a,0,i-1);
}
}
//三、交换排序（从前往后）。
//1、冒泡排序。
void bubble(int a[], int n)
{ int i,j,t;
for(i=1; i<n; i++) //此行可写为 for(i=n-1; i>0; i--)
{
for(j=0; j<n-i; j++) //对应上面的改动，此行要改为 for(j=0; j<n; j++)
if( a[j]>a[j+1] )
{ t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
}
//2、冒泡排序（从后往前）。
void bubble2(int a[], int n)
{ int i,j,t;
for(i=0; i<n-1; i++)
{
for(j=n-1; j>i; j--)
if( a[j-1]>a[j] )
{ t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
}
}
//3、改进的冒泡排序（加上一标志flag）。
void bubble3(int a[], int n)
{ int i, flag=1, t;
for(i=1; i<n && flag==1; i++)
{ flag = 0;
for(int j=0; j<n-i; j++)
if( a[j]>a[j+1] )
{ t = a[j];
a[j] = a[j+1];
a[j+1] = t;
flag = 1;
}
}
}
//4、改进的冒泡排序（）。
void bubble4(int a[], int n)
{ int k=1, m=n-1;
while(k!=0)
{ k = 0;
for(int j=0; j<m; j++)
if( a[j]>a[j+1] )
{ int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
k = j;
}
m = k;
}
}
//5、改进的冒泡排序（双向起泡、摇动排序）。
void ShakeSort(int a[], int n)
{
int j, k=0, low=0, high=n-1, t;
while(low < high)
{
for(j=low; j<h; j++)
if( a[j]>a[j+1] )
{ t = a[j]; a[j] = a[j+1]; a[j+1] = t; k=j; }
high = k;
for(j=h; j>l; j--)
if( a[j-1]>a[j] )
{ t = a[j-1]; a[j-1] = a[j]; a[j] = t; k=j; }
low = k;
}
}
//6、希尔排序（缩小增量排序）
void ShellSort2(int a[], int n)
{
int d = n/2;
bool flag;
while(d >= 1)
{
do
{ flag = false;
for(int i=0; i<n-d; i++)
{
int j = i+d;
if(a[i]>a[j])
{ int t = a[i]; a[i] = a[j]; a[j] = t;
flag = 1;
}
}
}while(flag);
d = d/2;
}
}
//7、快速排序
int Partition(int a[], int low, int high)
{
int x=a[low];
while(low < high)
{
while(low<high && a[high]>=x) high--;
if(low<high)
{ a[low] = a[high]; low++; }
while(low<high && a[low]<=x) low++;
if(low<high)
{ a[high] = a[low]; high--; }
}
a[low] = x;
return low;
}
void QSort(int a[], int low, int high)
{
if(low<high)
{
int mid = Partition(a,low,high);
QSort(a, low, mid-1);
QSort(a, mid+1, high);
}
}
void QuickSort(int a[], int n)
{
QSort(a, 0, n-1);
}
//8、快速排序（另一分区算法）
int Partition2(int a[], int low, int high)
{
int i=low, j=high+1, x=a[low], t;
while(i < j)
{
do i++; while(a[i]<x);
do j--; while(a[j]>x);
if(i<j)
{ t=a[i]; a[i]=a[j]; a[j]=t; }
}
a[low] = a[j]; a[j] = x;
return j;
}
//8、快速排序（另一分区算法）
int Partition3(int a[], int low, int high)
{
int k=low, x=a[low];
for(i=low+1; i<=high; i++)
if(a[i]<x)
{ k++; swap(a[k], a[i]); }
swap(a[low], a[k]);
return k;
}
//9、归并排序（非递归形式）
void Merge(int a[], int b[], int l, int m, int n)
{ //将a[l]…a[m]和a[m+1]…a[n]合并到b[l]…b[n]
int i=l, j=m+1, k=l;
while(i<=m && j<=n)
if(a[i]<=a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
while(i<=m) b[k++] = a[i++];
while(j<=n) b[k++] = a[j++];
}
void MergePass(int a[], int b[], int n, int len)
{
int i=0;
while( i+2*len-1 < n )
{ Merge(a,b,i,i+len-1,i+2*len-1);
i += 2*len;
}
if( i+len < n )
Merge(a,b,i,i+len-1,n-1);
else
for(int j=i; j<n; j++) b[j] = a[j];
}
void MergeSort(int a[], int n)
{
int b[n], len=1;
while(len<n)
{ MergePass(a,b,n,len); len *=2;
MergePass(b,a,n,len); len *=2;
}
}
//9、归并排序（递归形式）
void Merge(int a[], int b[], int l, int m, int n)
{ //将a[l]…a[m]和a[m+1]…a[n]合并到b[l]…b[n]
int i=l, j=m+1, k=l;
while(i<=m && j<=n)
if(a[i]<=a[j]) b[k++] = a[i++];
else b[k++] = a[j++];
while(i<=m) b[k++] = a[i++];
while(j<=n) b[k++] = a[j++];
}
void Msort( int a[], int b[], int s, int t )
{ // 将a[s..t]进行2-路归并排序，利用b数组。
if (s==t) return;
int m = (s+t)/2; // 将a[s..t]平分为a[s..m]和a[m+1..t]
Msort(a, b, s, m);
Msort(a, b, m+1, t);
Merge(a, b, s, m, t); // 将a[s..m]和a[m+1..t]归并到b[s..t]
for(int i=s; i<=t; i++) a[i] = b[i];
}
void MergeSort(int a[], int n)
{
int b[n];
Msort(a, b, 0, n-1);
}
例：比较计数法排序
void ComparisonCountingSort(int a[], int n)
{
int *count = new int[n];
int *b = new int[n];
for(int i=0; i<n; i++) count[i]=0;
for(int i=0; i<n-1; i++)
for(int j=i+1; j<n; j++)
if(a[i]>a[j]) count[i]++;
else count[j]++;
for(int i=0; i<n; i++) b[count[i]]=a[i];
for(int i=0; i<n; i++) a[i]=b[i];
}
例：分布排序
void DistributionCountingSort (int a[], int n, int l, int u)
{ //分布计数法排序，对n个值为l～u的数进行排序
int i, j;
int *d = new int[u-l+1];
int *b = new int[n];
for(j=0; j<=u-l; j++) d[j] = 0;
for(i=0; i<n; i++) d[a[i]-l]++;
for(j=1; j<=u-l; j++) d[j] = d[j-1] + d[j];
for(i=n-1; i>=0; i--)
{ j = a[i] - l;
b[d[j]-1] = a[i];
d[j]--;
}
for(int i=0; i<n; i++) a[i] = b[i];
}