1.冒泡排序：n*n。 俩个for循环决定其时间复杂度为n^2
template <class T> void Swap(T A[], int i, int j)
{
T tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
//冒泡法bubble sort
template<class T> void BubSort(T A[], int n)
{
for (int i=0; i<n; ++i)
{
for (int j=i+1; j<n; ++j)
{
if (A[i] < A[j])
Swap(A, i, j);
}
}
}
2.选择排序：n*n。 同样，俩个for循环决定其时间复杂度为n^2。
template <class T> void Swap(T A[], int i, int j)
{
T tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
template<class T> void SelSort(T A[], int n)
{
for (int i=0; i<n; ++i)
{
int largIndex = i; //largIndex存储元素值大的下标
for (int j=i+1; j<n; ++j)
{
if (A[largIndex] < A[j])
largIndex = j; //发现了较大的元素，记录下它的下标
}
Swap<T>(A, i, largIndex); //只进行最后一次交换
}
}
3.直接插入排序：n*n。 俩个for循环。
// 1->插入排序
void InsertSort(int array[], int length)
{
int i, j, key;
for (i = 1; i < length; i++)
{
key = array[i];
// 把i之前所有大于array[i]的数据向后移动
for (j = i - 1; j >= 0 && array[j] > key; j--)
{
array[j + 1] = array[j];
}
// 在合适位置安放当前元素
array[j + 1] = key;
}
}
template <class T> void Swap(T A[], int i, int j)
{
T tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
template<class T> void InsSort(T A[], int n)
{
for (int i=1; i<n; ++i) //i为什么要初始化为1？因为在i的前面至少有一个元素，才能比较。
{
for (int j=i; (j>0) && (A[j]>A[j-1]); --j)//总是与它的前一个元素比较，j>0是为了保证j-1不会溢出
{
Swap<T>(A, j, j-1);
}
}
}
归并排序算法思想的 c实现：
//July/设计/整理/测试/06.06/。
//1.分而治之排序算法的伪代码
//算法中子集合的数目为2，A中含有n/k个元素。
template void sort( T E, int n)
{
//对E中的n 个元素进行排序， k为全局变量
if (n >= k)
{
i = n/k;
j = n-i;
令A 包含E中的前i 个元素
令B 包含E中余下的j 个元素
sort(A,i) ;
sort(B,j) ;
merge(A,B,E,i,j,); //把A 和B 合并到E
}
else
使用插入排序算法对E 进行排序
}
//------------------------------------------------------------------------------
//2.根据网络上的算法提示，写出以下代码：
#include <iostream.h>
void MergePass(int x[],int y[],int s,int n);
void Merge(int c[], int d[], int l, int m, int r);
//首先将每两个相邻的大小为1的子序列归并，
//然后对上一次归并所得到的大小为2的子序列进行相邻归并，
//如此反复，直至最后归 并到一个序列，归并过程完成。
//通过轮流地将元素从a 归并到b 并从b 归并到a，可以虚拟地消除复制过程。
//...二路归并排序算法见程序14-3。
//14-3.二路归并排序
void MergeSort(int a[],int n)
{
//使用归并排序算法对a[0:n-1] 进行排序
int* b=new int [n];
int s=1; // 段的大小
while(s<n)
{
MergePass(a,b,s,n); // 从a归并到b
s+=s;
MergePass(b,a,s,n); // 从b 归并到a
s+=s;
}
}
//14-4 MergePass函数
void MergePass(int x[],int y[],int s,int n)
{
// 归并大小为s的相邻段
int i=0;
while(i<=n-2*s)
{
// 归并两个大小为s的相邻段
Merge(x,y,i,i+s-1,i+2*s-1);
i=i+2*s;
}
// 剩下不足2个元素
if(i+s<n)
Merge(x,y,i,i+s-1,n-1);
else
for(int j=i;j<=n-1;j++)
// 把最后一段复制到y
y[j] = x[j];
}
//...函数MergePass（见程序14-4）仅用来确定欲归并子序列的左端和右端，
//...实际的归并工作由函数Merge(见程序14-5 )来完成。
//...函数Merge要求针对类型T定义一个操作符<=。
//14-5。Merge函数
void Merge(int c[], int d[], int l, int m, int r)
{
// 把c[l:m]] 和c[m:r] 归并到d [ l : r ] .
int i=l; // 第一段的游标
int j=m+1; // 第二段的游标
int k=l; // 结果的游标
//只要在段中存在i和j，则不断进行归并
while ((i<=m)&&(j<=r))
{
if(c[i]<=c[j])
d[k++]=c[i++];
else
d[k++]=c[j++];
}
// 考虑余下的部分
if(i>m)
{
for(int q=j;q<=r;q++)
d[k++]=c[q];
}
else
{
for(int q=i;q<=m;q++)
d[k++]=c[q];
}
}
int main()
{
int str[7]={49,38,65,97,76,13,27};
MergeSort(str,7);
for(int i=0;i<7;i++)
printf("%d
",str[i]);
return 0;
}
//-----------------------------------------------------------------------------------
//3...森林大哥的写法，测试下，无误。：
#include <stdio.h>
#define N 100
void sort(int str[],int n)
{
int guop_1[N],guop_2[N];
if(1==n)
{
return;
}
if(2==n)
{
if(str[0]>str[1])
{
int tmp=str[0];
str[0]=str[1];
str[1]=tmp;
}
return;
}
for(int i=0;i<N;i++)
{
guop_1[i]=guop_2[i]=0;
}
int k=n/2;
for(i=0;i<k;i++)
{
guop_1[i]=str[i];
}
for(i=k;i<n;i++)
{
guop_2[i-k]=str[i];
}
sort(guop_1,k);
sort(guop_2,n-k);
int j;
for(i=0,j=0;i<k;i++)
{
for(;j<n-k;j++)
{
if(guop_1[i]<=guop_2[j])
{
str[i+j]=guop_1[i];
break;
}
else
{
str[i+j]=guop_2[j];
}
}
if(n-k==j)
{
for(;i<k;i++)
{
str[i+j]=guop_1[i];
}
}
}
if((k==i)&&(j<n-k))
{
for(;j<n-k;j++)
{
str[i+j]=guop_2[j];
}
}
}
int main()
{
int str[7]={49,38,65,97,76,13,27};
sort(str,7);
for(int i=0;i<7;i++)
printf("%d
",str[i]);
return 0;
}