冒泡排序和快速排序
（1）实验描述
我们学习到排序是将一个无序序列整理成按值非递减顺序排列的有序序列。
排序可以在不同的存储结构上实现。
基本排序是在顺序存储的线性表中实现的；二叉排序树利用二叉树的链式存储结构实现无序表的有序化。
本实验将进行冒泡排序和快速排序的基本操作，以实现冒泡排序和快速排序的熟练掌握和应用。
（2）实验过程
冒泡排序：
1) 从表头开始向后扫描，依次比较相邻元素。
如果为“逆序”，进行互换。
一次扫描后，最大元素排到表末端；
2)从后先前扫描剩下的线性表，依次比较相邻元素，如有“逆序”，进行互换。
一次扫描后，最小元素排到表前端；
3)对剩下的线性表重复过程(1)(2)，直到消除了所有的逆序。
输入：无序序列
快速排序：
1）在表的第一个、中间一个与最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到P(k)的位置上。
2）设置两个指针i和j分别指向表的起始与最后的位置。
反复作以下两步：
(1)将j逐渐减小，并逐次比较P(j)与T，直到发现一个
P(j)＜T为止，将P(j)移到P(i)的位置上。
(2)将i逐渐增大，并逐次比较P(i)与T，直到发现一个
P(i)＞T为止，将P(i)移到P(j)的位置上。
上述两个操作交替进行，直到指针i与j指向同一个位置（即i＝j）为止，此时将T移到P(i)的位置上。
输入：待排序的子表
（3）实验结果及分析
冒泡排序:
输出：有序序列
快速排序
输出：有序子表
（4）实验结论
冒泡排序最坏情况下的时间复杂度（工作量）为 (n(n-1)/2).
快速排序在最坏情况下需要(n(n-1)/2).次比较，但实际上排序效率要比冒泡排序高的多。
程序//代码:
//bub.h
template<class T>
void bub(T p[],int n)
{
int m,k,j,i;
T d;
k=0;m=n-1;
while(k<m)
{
j=m-1;m=0;
for(i=k;i<=j;i++)
if(p[i]>p[i+1])
{d=p[i];p[i]=p[i+1];p[i+1]=d;m=i;}
j=k+1;k=0;
for(i=m;i>=j;i--)
if(p[i-1]>p[i])
{d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}
}
return;
}
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
int i,j;
double p[50],r=1.0;
for(i=0;i<50;i++)
{
r=2053.0*r+13849.0;j=r/65536.0;
r=r-j*65536.0;p[i]=r/65536.0;
}
for(i=0;i<50;i++)
p[i]=100.0+200.0*p[i];
cout<<"排序前的序列："<<endl;
for(i=0;i<10;i++)
{
for(j=0;j<5;j++) cout<<setw(10)<<p[5*i+j];
cout<<endl;
}
bub(p+10,30);
cout<<"排序后的序列："<<endl;
for(i=0;i<10;i++)
{
for(j=0;j<5;j++) cout<<setw(10)<<p[5*i+j];
cout<<endl;;
}
return 0;
}
//quk.h
#include''bub.h''
Template<class T>
procedure split(P，m，n，i)
选取P(k) 其中m≤k≤n
T＝P(k)；P(k)＝P(m)
i＝m；j＝n
while(i≠j) do
{ while(P(j)≥T)and(i＜j) do j＝j－1
if (i＜j) then
{ P(i)＝P(j)；i＝i＋1
while (P(i)≥T)and(i＜j))
do i＝i＋1
if (i＜j)
then
{ P(j)＝P(i)；j＝j－1 }
}
}
P(i)＝T
return
Template<class T>
static int split(ET *p,int m,int n) /*返回分界线位置*/ {
int i,j,k,u;
ET t;
i=m-1; j=n-1; k=(i+j)/2;
if ((p[i]>=p[j])&&(p[j]>=p[k]))
u=j; /*选取一个元素*/
else if ((p[i]>=p[k])&&(p[k]>=p[j]))
u=k;
else
u=i;
t=p[u]; p[u]=p[i];
while (i!=j) {
while ((i＜j)&&(p[j]>=t)) j=j-1;
if (i＜j) {
p[i]=p[j]; i=i+1;
while ((i＜j)&&(p[i]＜=t)) i=i+1;
if (i＜j){
p[j]=p[i]; j=j-1;
}
}
}
p[i]=t;
return(i);
}。