交换排序的设计与实现.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;j<i;j++)
{
if(a[j]>a[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<j)
{
while(i<j&&r[j]>=x)
{
j--;
k++;
}
r[i]=r[j];
while(i<j&&r[i]<=x)
{
i++;
k++;
}
r[j]=r[i];
k++;
}
r[i]=t;
return i;
}
//快速排序算法-----------------------------------------------
void QuickSort(int low,int high,int r[])
{
if(low<high)
{
int k_1;
k_1=Partition(low,high,r);
QuickSort(low,k_1-1,r);
QuickSort(k_1+1,high,r);
k=k+3;
}
}
全代码：
#include<iostream>
#include<ctime>
#include<cstdlib>
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;i<MAX;i++)
{
a[i]=int(random(0,10000));
}
//选择排序方法----------------------------------------------------------
cout<<"which do you change(1-冒泡排序，2-双向冒泡排序，3-快速排序算法)"<<endl;
cin>>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<MAX;i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"计算次数："<<k<<endl;
return 1;
}
//产生随机数算法----------------------------------------------------------
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;j<i;j++)
{
if(a[j]>a[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<j)
{
while(i<j&&r[j]>=x)
{
j--;
k++;
}
r[i]=r[j];
while(i<j&&r[i]<=x)
{
i++;
k++;
}
r[j]=r[i];
k++;
}
r[i]=t;
return i;
}
//快速排序算法-----------------------------------------------
void QuickSort(int low,int high,int r[])
{
if(low<high)
{
int k_1;
k_1=Partition(low,high,r);
QuickSort(low,k_1-1,r);
QuickSort(k_1+1,high,r);
k=k+3;
}
}
4. 程序运行结果
选择输入

选择1的输出结果

选择2的输出结果

选择3的输出结果

5. 有关技术的讨论
1. 对于这次的设计使用的是C++语言。在设计之中运用了C++中的数组结构，选择结构，输入输出，数组在函数中的调用，几种循环语句的运用。
2. 在做几个函数使a[i]在函数的的调用的时候老是出错，后来去查阅了C语言的书中，知道了函数名可以传递数组的头地址在函数中去 从而改变原数组的值，然后才有了这几个算法函数的使用。
3. 对于各种算法的方法，我查阅了数据结构的课件，然后将其中的算法用C++语言翻译出来得到实现。
6. 设计体会

感觉这次设计让我更加了解了C++和排序的各种算法 收获很大，克服了很多困难，学会了自己查阅资料

参考文献：C语言程序设计
数据结构课件

11