交换排序的设计与实现.doc

交换排序的设计与实现

摘要：该程序主要部分有：
（1）随机产生1000个整数
（2）实现冒泡排序、双向冒泡排序和快速排序
（3）比较各种交换排序的优劣
关键字：随机数，冒泡排序，双向冒泡排序，快速排序，交换排序的优劣。

0. 引言：随着现在社会的不断发展，人们的各种社会信息量变的越来越多，数字也随之变的越来越杂乱无序，那么 我们就设计这个程序来进行数字的排序，让我们的信息变的有序方便。
1. 需求分析：①学校考试成绩排名 ②排序算法的比较 如何才是最适合你的排序算法 ③各种信息数字整理排序。
2. 数据结构设计
void BubbleSort(int a[]);
--------冒泡排序算法
void DblPPSort(int L[],int low,int high);
--------双向冒泡排序算法
int Partition (int i,int j,int r[]);
--------第一趟快速排序
void QuickSort (int low,int high,int r[]);
--------快速排序算法
double random(double,double);
--------产生随机数
int k=0;
-----记录计算次数
int a[MAX];
-----记录1000个随机数字
3. 算法设计
//产生随机数算法----------------------------------------------------------
double random(double start, double end)
{
return start+(end-start)*rand()/(RAND_MAX + 1.0);
}
//冒泡排序算法------------------------------------------------------------
void BubbleSort(int a[])
{
int i,j,t;
i=MAX;
do{
for(j=0;ja[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
k=k+3;
}
}
i--;
}while(i>1);
}
//双向冒泡算法----------------------------------------------------------------------
void DblPPSort(int L[],int low,int high)
{
int i,t,fini = 0;
while (low < high) {
fini = 1;
for (i = low; i<=high; i++)
if (L[i] > L[i+1]) {
t = L[i];
L[i] = L[i+1];
L[i+1] = t;
fini = 0;
k=k+3;
}
if (fini) break;
high--;
for (i = high; i>=low; i--)
if (L[i] > L[i+1]) {
t = L[i];
L[i] = L[i+1];
L[i+1] = t;
fini = 0;
k=k+3;
}
if (fini) break;
low++;
}
}
//一趟快速排序算法----------------------------
int Partition(int i,int j,int r[])
{
int t,x;
t=x=r[i];
while(i=x)
{
j--;
k++;
}
r[i]=r[j];
while(i//快速排序算法-----------------------------------------------
void QuickSort(int low,int high,int r[])
{
if(low
#include
#include
using namespace std;
#define MAX 1000
void BubbleSort(int a[]);
void DblPPSort(int L[],int low,int high);
int Partition (int i,int j,int r[]);
void QuickSort (int low,int high,int r[]);
double random(double,double);
int k=0;
//主程序--------------------------------------------------------------
int main()
{
int a[MAX];
int i,s;
//产生随机数----------------------------------------------------------
srand(unsigned(time(0)));
for(i=0;i3-快速排序算法)"<>s;
switch(s)
{
//冒泡排序--------------------------------------------------------------
case 1:BubbleSort(a);break;
//双向冒泡排序算法------------------------------------------------------
case 2:DblPPSort(a,0,MAX-1);break;
//快速排序算法--------------------------------------------
case 3:QuickSort (0,MAX-1,a);break;
default:printf("error\n");return 0;
}
for(i=0;i double end)
{
return start+(end-start)*rand()/(RAND_MAX + 1.0);
}
//冒泡排序算法------------------------------------------------------------
void BubbleSort(int a[])
{
int i,j,t;
i=MAX;
do{
for(j=0;ja[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
k=k+3;
}
}
i--;
}while(i>1);
}
//双向冒泡算法----------------------------------------------------------------------
void DblPPSort(int L[],int low,int high)
{
int i,t,fini = 0;
while (low < high) {
fini = 1;
for (i = low; i<=high; i++)
if (L[i] > L[i+1]) {
t = L[i];
L[i] = L[i+1];
L[i+1] = t;
fini = 0;
k=k+3;
}
if (fini) break;
high--;
for (i = high; i>=low; i--)
if (L[i] > L[i+1]) {
t = L[i];
L[i] = L[i+1];
L[i+1] = t;
fini = 0;
k=k+3;
}
if (fini) break;
low++;
}
}
//一趟快速排序算法----------------------------
int Partition(int i,int j,int r[])
{
int t,x;
t=x=r[i];
while(i=x)
{
j--;
k++;
}
r[i]=r[j];
while(i if(low