实验7： 内部排序算法比较

实验7： 内部排序算法比较

一、问题描述

程序对以下4种内部排序（冒泡排序、直接插入排序、简单选择排序、快速排序）算法进行实测比较，测试各种算法在对同样的数据排序时的比较次数和移动次数。

二、输入与输出

输入：根据用户需要输入待排表的表长（100至1000）和不同测试数据的组数 （8至18），不输入则按照默认值进行测试

输出：每次测试完毕，列表显示各种比较指标值：比较次数和移动次数

二、需求分析

1.本演示程序对以下4种常见的内部排序算法进行实测比较：冒泡排序、直接插入

排序、简单选择排序、快速排序

2.待排序表的元素的关键字为整数。用正序、逆序和不同乱序程度的不同数据做测

试比较。比较的指标为由关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）

3.演示程序以用户和计算机的对话方式执行，即在计算机终端上菜单，根据用户需

要输入待排表的表长（100至1000）和不同测试数据的组数（8至18），不输入则按照默认值进行测试。 四、开发工具与环境

硬件设备：微型计算机系统

软件环境：操作系统Windows，开发工具Devc++ 五、功能分析

存储结构 typedef int Typekey; typedef struct { Typekey key; }Type; typedef struct { Type r[MAXSIZE+1];//顺序表 int length; }PList;//排序表

常用软件课程设计

非线性系统描述为

函数一览表

int OneTimeSqCreate(PList &L) /*手动输入创建排序序列函数*/

int ManyTimeSqCreate(PList &L,int m) /*自动生成排序序列函数*/

void BubbleSort(PList &L) /*冒泡排序*/

void InsertSort(PList &L) /*插入排序*/

void SelectSort(PList &L) /*简单选择排序*/

int Partition(PList &L,int low,int high) /*一次快速排序*/

void QSort(PList &L,int low,int high) /*递归形式的快速排序算法*/

void QuickSort(PList &L) /*快速排序*/

六、程序代码

#include #include #include #include

#define MAXSIZE 10000 using namespace std; typedef int Typekey;

int compCount; //关键字的比较次数 int shiftCount; //关键字的移动次数

typedef struct { Typekey key; }Type;

typedef struct { Type r[MAXSIZE+1];//顺序表 int length; }PList;//排序表

常用软件课程设计

非线性系统描述为

int OneTimeSqCreate(PList &L){//手动输入创建排序序列函数 int x,h; for ( x=1; 1; x++) { cin>>h; L.r[x].key=h ; if(getchar()=='\\n'){//只读入一行，换行则终止 break; } } L.length=x; }

int ManyTimeSqCreate(PList &L,int m){//自动生成排序序列函数 L.length=m; for (int x=1; x<=m; x++) { L.r[x].key= rand() % m;//随机数的取值范围为0~k } return 1; }

void BubbleSort(PList &L) {//冒泡排序 int i,j,l,m=0,n=0; for(i=1;i<=L.length-1;++i){//只需要比较length-1次 for(j=1;j<=L.length-i;++j){//内层循环所谓的冒泡，将最大值放到末尾 ++m;//比较次数 if(L.r[j].key>L.r[j+1].key){ l=L.r[j].key; L.r[j].key=L.r[j+1].key; L.r[j+1].key=l; n+=3;//关键字移动次数 } } } cout<void InsertSort(PList &L){//插入排序 int i,j,m=0,n=0;//m是比较次数，n是交换次数 cout<常用软件课程设计

非线性系统描述为

L.r[0]=L.r[i];//设置哨兵 L.r[i]=L.r[i-1];//后移一位 for(j=i-2;L.r[0].keyvoid SelectSort(PList &L) { //简单选择排序 int l,i,j,m=0,n=0;//m是比较次数，n是移动次数 cout<L.r[j].key){//表明j处key值更小 l=j;//记录下j的值 L.r[0]=L.r[j]; } } if(l!=i){//需要交换位置 n+=3;//移动次数加3，按实验报告要求一次交换代表3次移动 L.r[l]=L.r[i]; L.r[i]=L.r[0]; } } cout<<\" 简单选择排序:\"; cout<<\"比较次数:\"<int Partition(PList &L,int low,int high){//一次快速排序 int pivotkey;//中间轴 L.r[0]=L.r[low];//记录轴元素 pivotkey=L.r[low].key;//轴取low while(low=pivotkey){ ++compCount;//比较次数加1 --high;//high左移 } shiftCount+=3;//移动次数加3，按实验报告要求一次交换代表3次移动

常用软件课程设计

非线性系统描述为

L.r[low]=L.r[high];//此时应当交换位置 while(lowvoid QSort(PList &L,int low,int high){//递归形式的快速排序算法 int Piv;//轴元素位置 if(lowvoid QuickSort(PList &L){//快速排序 int i; QSort(L,1,L.length); cout<<\" 快速排序:\"; cout<<\"比较次数:\"<int main(){ int i,k,h,n,m; PList L,alist,blist,clist,dlist; cout<<\"————————排序模式选择————————\"<>h; if(h==1){//手动输入模式 OneTimeSqCreate(L); alist=blist=clist=dlist=L; BubbleSort(L); InsertSort(alist); SelectSort(blist); QuickSort(clist); cout<<\"排序后序列：\"; for(i=1;i<=L.length;i++) cout<<\" \"<常用软件课程设计

非线性系统描述为

}

}

cout<<\"输入想要排序的测试组数n和表长m，程序会帮你生成随机序列:\"; cin>>n>>m; k=1;

while(k++<=n){ cout<return 0;

七、运行测试

1、手动输入递增序列 1 2 3 4 5 6 7 8 9

图的创建 1、手动输入递减序列 9 8 7 6 5 4 3 2 1

常用软件课程设计

非线性系统描述为

3. 生成随机序列8组，每一个测试序列的表长度为100

1

得到测试结果如下表所示

2

3

4

组数 排序算法 冒泡排序 直接插入排序 简单选择排序 快速排序

比较次数 交换次数 比较次数 交换次数 比较次数 交换次数 比较次数 交换次数

4950 2609 4950 587

7827 273 282 984

4950 21 4950 660

7623 276 282 948

4950 2310 4950 669

6930 270 285 930

4950 2469 4950 675

7407 285 291 930

常用软件课程设计

非线性系统描述为

组数 排序算法 冒泡排序 直接插入排序 简单选择排序 快速排序

5 6 7 8

比较次数 交换次数 比较次数 交换次数 比较次数 交换次数 比较次数 交换次数

4950 24 4950 596

7467 291 273 924

4950 2218 4950 623

66 279 273 918

4950 2398 4950 630

7194 288 285 978

4950 2493 4950 677

7479 285 273 9

可以得到4种排序算法的平均比较和移动次数如下表

排序算法 冒泡排序 直接插入排序 简单选择排序 快速排序

平均比较次数

4950 2398 4950 633

关键字平均移动次数

7216 282 279 936

可以看出快速排序的平均比较次数最少，而直接插入排序和简单选择排序的平均移动次数最少，综合看来对于一般的无序序列，快速排序是这4种算法里面性能最优的一种。

常用软件课程设计

非线性系统描述为

八、实验总结

排序算法各有其适用的情况，应该具体问题具体分析。

冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。选择排序的主要思想：首先找到数组中最小的那个元素，其次，将它和第一个元素交换。接下来找第二小和第二个交换。运行时间和输入无关，数据移动最少。当数据量较小的时候适用。直接插入排序时间复杂度为O(n^2)，数据量小时使用。并且大部分已经被排序。快速排序是最快的通用排序算法，在大多数实际情况中，快速排序是最佳选择。

常用软件课程设计

非线性系统描述为

常用软件课程设计