数据结构之常用排序算法的对比分析

数据结构之常用排序算法的对比分析

1．实验题目

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。

2．需求分析

本程序用C++编写，完成了记录表的随机生成，输出记录了表的功能，各种内部排序算法的实现，计算每种排序中关键字的移动次数和比较次数。

①输入的形式和输入值的范围：本程序不支持用户的自定义输入，程序中定义开始的循序表的长度为100，1000，10000，100000,1000000。表中的关键字由随机函数随机生成。

②输出的形式：分别输出当前数量级以及各种排序方法的排序时间、移动次数、比较次数。

③程序所能达到的功能：计算每种排序所执行的时间、关键字移动的次数、关键字比较的次数。

④测试数据：由随机产生器决定。

3．概要设计

1）为了实现上述程序功能，需要定义待排序记录表的抽象数据类型：

ADT RedList{

数据对象：D={ri|ri∈sq，i=1，2，⋯，n，n≥0}

数据关系：R={<ri,ri+1>|ri,ri+1∈D}

基本操作：

CreateNum()

操作结果：创建一个随机数生成的数组。

sq init()

初始条件：存在一个随机数生成的数组。

操作结果：创建一个顺序表，并将随机函数生成的数组值赋值给关键字。

InsertSort(sq &L)

初始条件：顺序表L存在

操作结果：将顺序表用直接插入排序拍成有序序列，输出关键字移动次数，比较次数。

ShellInsert(sq &L,int dk)

初始条件：顺序表L，增量dk存在

操作结果：将全部记录分成dk个组，所有间隔为dk的记录分到同一组，各组内为有序序列，记录关键字的涌动次数各比较次数。

ShellSort(sq &L,int t)

初始条件：顺序表L存在，增量的个数t存在，ShellInsert(sq &L,int dk)函数存在。

操作结果：将无序表用希尔排序排列为有序序列，记录关键字的移动次数，比较次数Partition(sq &L,int low,int high)

初始条件：顺序表L存在，low和high存在

操作结果：返回顺序表L中子表r[low..high]的枢轴位置，记录关键字移动次数，比次数，枢轴前的关键字小于枢轴关键字，枢轴后的关键字大于枢轴关键字QSort(sq &L,int low,int high)

初始条件：顺序表L存在，low和high存在，Partition(sq &L,int low,int high)函数存在。

操作结果：将无序表排列为有序表。

QuickSort(sq &L)

初始条件：Partition(sq &L,int low,int high)，QSort(sq &L,int low,int high)函数存在，顺序表L存在。

操作结果：无序表为有序表。

BubbleSort(sq &L)

初始条件：顺序表L存在

操作结果：将无序表用冒泡排序法排序为有序序列，记录关键字移动次数，比较次数SelectSort(sq &L)

初始条件：顺序表L存在

操作结果：将无序表用简单选择排序法排序为有序序列，记录关键字移动次数，比较次数

HeapAdjust(sq &L,int s,int m)

初始条件：顺序表L存在，整数s，m存在。

操作结果：将r[s..m]调整为以r[s]为根的大根堆。记录关键字移动次数，比较次数。CreatHeap(sq &L)

初始条件：顺序表L存在，HeapAdjust(sq &L,int s,int m)函数存在。

操作结果：将无序序列调整为大根堆

HeapSort(sq &L)

初始条件：顺序表L存在，HeapAdjust，CreatHeap两个函数存在。

操作结果：将顺序表L进行堆排序，排序为有序序列，记录关键字移动次数，比较次数。show(sq L)

初始条件：顺序表L存在

操作结果：输出顺序表L

}

2）本程序包含14个函数：

①主函数main()

②随机数函数CreateNum()

③构造顺序表函数 init()

④直接插入排序函数InsertSort（）

⑤增量为dk的希尔排序ShellInsert()

⑥增量为d[t]的希尔插入排序函数ShellSort()

⑦返回顺序表L中的子表r[low..high]枢轴函数Partition()

⑧对顺序表L中的子序列L.r[low..high]做快速排序函数QSort()

⑨对顺序表L做快速排序函数QuickSort()

⑩冒泡排序函数BubbleSort()

⑪简单选择排序函数SelectSort()

⑫筛选法调整堆函数HeapAdjust（）

⑬初建堆函数CreatHeap（）

⑭堆排序函数HeapSort（）

4．详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法。对主程序和其他模块也都需要写出伪码算法。

1) 结点类型和指针类型

1  typedef struct{
2 
3     int len;
4 
5     ElemType *r；
6 
7 }sq;//顺序表

2）其他模块伪码算法

  1 void CreateNum(){
  2 
  3        srand((unsigned)time(NULL));//产生随机数
  4 
  5        for(int i=1;i<=maxn;i++){
  6 
  7         N[i]=rand()%MAXN;对一个数组进行赋值}
  8 
  9 }//随机数函数
 10 
 11 sq init(){
 12 
 13       sq L;
 14 
 15       L.len=maxn;//对顺序表中的key进行赋值
 16 
 17       L.r=new ElemType[maxn+1];
 18 
 19       for(int i=1;i<=maxn;i++){
 20 
 21         L.r[i].key=N[i];}
 22 
 23       return L;
 24 
 25 }//构造顺序表
 26 
 27 void InsertSort(sq &L){
 28 
 29       int j;
 30 
 31       将第一关键字作为有序序列，分别将之后的关键字插入到该序列中，插入到最后一个大于它的关键字前。
 32 
 33       有key的比较L.r[i].key<L.r[i-1].key就产生一次关键字的比较InsertComp++;
 34 
 35       有对顺序表中赋值语句L.r[i].key=L.r[j].key;出现就有关键字移动。
 36 
 37 用for语句将所有关键字进行排序。
 38 
 39 }
 40 
 41 void ShellInsert(sq &L,int dk){
 42 
 43       int i,j;
 44 
 45       用for循环进行分组   
 46 
 47 ShellComp++;与所有排序函数中一样，出现L.r[i].key<L.r[i-dk].key，关键字比较次数增加一次
 48 
 49       分组时进行组内排序，记录关键字移动次数和比较次数
 50 
 51 }//希尔插入排序
 52 
 53   void ShellSort(sq &L,int t){//5 3 1 -> t=3   7 5 3 1 -> t=4
 54 
 55       int dt[100];
 56 
 57 用for循环和dt[j]=-2*j+t+2语句取出所有的增量。
 58 
 59       用for取遍所有增量的希尔排序
 60 
 61 }//增量为dt[t]的希尔插入排序
 62 
 63 int Partition(sq &L,int low,int high){
 64 
 65      对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置
 66 
 67 用子表的第一个记录做枢轴记录
 68 
 69 枢轴记录关键字保存在pivotkey中
 70 
 71 从表的两端交替地向中间扫描
 72 
 73 将比枢轴记录小的记录移到低端
 74 
 75 将比枢轴记录大的记录移到高端
 76 
 77 重新定义枢轴记录，用子表的第一个记录做枢轴记录
 78 
 79 返回枢轴位置
 80 
 81 }//Partition
 82 
 83  void QSort(sq &L,int low,int high){
 84 
 85 调用前置初值：low=1; high=L.length;
 86 
 87 对顺序表L中的子序列L.r[low..high]做快速排序
 88 
 89 将L.r[low..high]一分为二，pivotloc是枢轴位置
 90 
 91       对左子表递归排序
 92 
 93       对右子表递归排序
 94 
 95 }  
 96 
 97 void QuickSort(sq &L){
 98 
 99     //对顺序表L做快速排序
100 
101     QSort(L,1,L.len);
102 
103  }
104 
105 void BubbleSort(sq &L){
106 
107     for(int i=1;i<L.len;i++){
108 
109         for(int j=1;j<=L.len-i;j++){
110 
111             BubbleComp++;
112 
113             if(L.r[j+1].key<L.r[j].key) {
114 
115                 swap(L.r[j+1],L.r[j]);
116 
117                 BubbleMove+=2;
118 
119             }
120 
121         }
122 
123     }  
124 
125 }//冒泡排序
126 
127 void SelectSort(sq &L)
128 
129 {
130 
131     在L.r[i..L.len]中选择关键字最小的的记录
132 
133 将记录表的第一个元素与最小记录元素位置互换，直到排序完毕
134 
135 }//简单选择排序
136 
137 void HeapAdjust(sq &L,int s,int m)//筛选法调整堆
138 
139 { 假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大堆根
140 
141 沿key较大的孩子结点向下筛选
142 
143 if(j<m&&L.r[j].key<L.r[j+1].key) ++j;//j为key较大的记录的下标
144 
145     HeapComp++;
146 
147     if(rc.key>=L.r[j].key) break;        //rc应插入在位置s上
148 
149     L.r[s]=L.r[j];
150 
151     HeapMove++;
152 
153     s=j;                                
154 
155     L.r[s]=rc;
156 
157     HeapMove++;     //插入
158 
159 }
160 
161 void CreatHeap(sq &L)                       //建初堆
162 
163 {  
164 
165 反复调用HeapAdjust，将无序序列建成大根堆
166 
167 }
168 
169 void HeapSort(sq &L)        //堆排序
170 
171 {
172 
173       CreatHeap(L);           //建成大堆根
174 
175       用for循环交换堆定元素和最后一个记录。
176 
177       将堆顶记录和当前未经排序子序列L.r[1..i]中最后一个记录互换
178 
179       HeapAdjust(L,1,i-1);//重新调整为大根堆
180 
181     }
182 
183 void show(sq L){
184 
185      for(int i=1;i<=L.len;i++)
186 
187      cout<<L.r[i].key<<' ';
188 
189      puts("");输出记录的关键字
190 
191 }//输出函数

5．调试分析

将计算比较次数语句放在了if语句前，否则会忽略if语句中在不满足条件时一次关键字比较

6．使用说明

系统随机产生数据，并进行各项排序。

7．测试结果

8．附代码

  1 // 实验六.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 
  6 
  7 #include<iostream>
  8 using namespace std;
  9 
 10 #include   <stdlib.h>    
 11 #include   <time.h> //随机数的头文件
 12 #define MAXN 100000000
 13 int maxn;
 14 int N[MAXN+5];
 15 //        Compare 比较次数          Move 移动次数 
 16 long long InsertMove,InsertComp,
 17     BInsertMove,BInsertComp,
 18     QComp,QMove,
 19     BubbleComp,BubbleMove,
 20     ShellComp,ShellMove,
 21     SelectComp,SelectMove,
 22     HeapComp,HeapMove;
 23  
 24 typedef struct{
 25     int key;
 26     //int m;
 27 }ElemType;//记录类型
 28  
 29 typedef struct{
 30     int len;
 31     ElemType *r;//*r 与 r[MAXNSIZE]有区别
 32 }sq;//顺序表
 33  
 34 void CreateNum(){
 35     srand((unsigned)time(NULL));
 36     for(int i=1;i<=maxn;i++){
 37         N[i]=rand()%MAXN;
 38     }
 39 }//随机数函数
 40  
 41 sq init(){
 42     sq L;
 43     L.len=maxn;
 44     L.r=new ElemType[maxn+1];
 45     for(int i=1;i<=maxn;i++){
 46         L.r[i].key=N[i];
 47     }
 48     return L;
 49 }//构造顺序表
 50  
 51 void InsertSort(sq &L){
 52     int j;
 53     for(int i=2;i<=L.len;i++){
 54         InsertComp++;
 55         if(L.r[i].key<L.r[i-1].key){
 56             L.r[0].key=L.r[i].key;
 57             InsertMove++;
 58             for(j=i-1;L.r[j].key>L.r[0].key;j--,InsertComp++){
 59                 L.r[j+1].key=L.r[j].key;
 60                 InsertMove++;
 61             }
 62             L.r[j+1].key=L.r[0].key;
 63             InsertMove++;
 64         }
 65     }
 66 }//直接插入排序，两个关键字的比较不等式出现 比较次数加1，有关键字的赋值语句就有一次移动。
 67  
 68 /*void BInsertSort(sq &L){
 69     int j,l,r,temp;
 70     for(int i=2;i<=L.len;i++){
 71         temp=L.r[i].key;
 72         l=1,r=i-1;
 73         while(l<=r){
 74             int m=(l+r)/2;
 75             if(temp<L.r[m].key) r=m-1;
 76             else l=m+1;
 77             BInsertComp++;
 78         }
 79         for(j=i;j>=l+1;j--) {
 80             L.r[j].key=L.r[j-1].key;//L.r[j]=L.r[j-1];
 81             BInsertMove++;
 82         }
 83         L.r[l].key=temp;
 84         BInsertMove++;
 85     }
 86 }//折半插入排序*/
 87  
 88 void ShellInsert(sq &L,int dk){
 89     int i,j;
 90     for(i=dk+1;i<=L.len;i++){
 91         ShellComp++;
 92         if(L.r[i].key<L.r[i-dk].key){
 93             L.r[0]=L.r[i];
 94             ShellMove++;
 95             for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk,ShellComp++){
 96                 L.r[j+dk]=L.r[j];
 97                 ShellMove++;
 98             }        
 99             L.r[j+dk]=L.r[0];
100             ShellMove++;
101         }
102     }
103 }//希尔插入排序
104  
105 void ShellSort(sq &L,int t){//5 3 1 -> t=3   7 5 3 1 -> t=4
106     int dt[100];
107     for(int j=0;j<t;j++){ 
108     /*
109     3 0 5 5
110     3 1 3 5
111     3 2 1 5
112     */
113         dt[j]=-2*j+t+2;
114     }
115      for(int i=0;i<t;i++)
116          ShellInsert(L,dt[i]);
117 }//增量为dt[t]的希尔插入排序
118  
119 int Partition(sq &L,int low,int high){
120     //对顺序表L中的子表r[low..high]进行一趟排序，返回枢轴位置
121     int pivotkey;
122     L.r[0]=L.r[low];                        //用子表的第一个记录做枢轴记录
123     pivotkey=L.r[low].key;                       //枢轴记录关键字保存在pivotkey中
124     while(low<high)    {                                        //从表的两端交替地向中间扫描
125         while(low<high&&L.r[high].key>=pivotkey) --high,QComp++;
126         L.r[low]=L.r[high],QMove++;                //将比枢轴记录小的记录移到低端
127         while(low<high&&L.r[low].key<=pivotkey) ++low,QComp++;
128         L.r[high]=L.r[low],QMove++;                    //将比枢轴记录大的记录移到高端
129         
130     }//while
131     L.r[low]=L.r[0];                        //枢轴记录到位
132     return  low;                            //返回枢轴位置
133 }//Partition
134  
135 void QSort(sq &L,int low,int high){    //调用前置初值：low=1; high=L.length;
136     //对顺序表L中的子序列L.r[low..high]做快速排序
137     int pivotloc;
138     if(low<high){                                        //长度大于1
139        pivotloc=Partition(L,low,high);         //将L.r[low..high]一分为二，pivotloc是枢轴位置
140        QSort(L,low,pivotloc-1);                //对左子表递归排序
141        QSort(L,pivotloc+1,high);            //对右子表递归排序
142     }
143 }                                            //QSort
144  
145 void QuickSort(sq &L){
146     //对顺序表L做快速排序
147    QSort(L,1,L.len);
148 }                                            //QuickSort
149  
150 void BubbleSort(sq &L){
151     for(int i=1;i<L.len;i++){
152         for(int j=1;j<=L.len-i;j++){
153             BubbleComp++;
154             if(L.r[j+1].key<L.r[j].key) {
155                 swap(L.r[j+1],L.r[j]);
156                 BubbleMove+=2;
157             }
158         }
159     }    
160 }//冒泡排序
161  
162 void SelectSort(sq &L)
163 {
164     for(int i=1;i<L.len;i++)
165     {
166         int k=i;
167         for(int j=i+1;j<=L.len;j++)
168         {
169             SelectComp++;
170             if(L.r[j].key<L.r[k].key)
171             {
172                 k=j;
173             }
174         }
175         if(k!=i)
176         {
177             ElemType t=L.r[i];
178             L.r[i]=L.r[k];
179             L.r[k]=t;
180             SelectMove+=2;
181         }
182     }
183 }//简单选择排序
184 
185 void HeapAdjust(sq &L,int s,int m)//筛选法调整堆
186 {//假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大堆根
187     ElemType rc=L.r[s];
188     for(int j=2*s;j<=m;j*=2)                 //沿key较大的孩子结点向下筛选
189     {
190         HeapComp++;
191         if(j<m&&L.r[j].key<L.r[j+1].key) ++j;//j为key较大的记录的下标
192         HeapComp++;
193         if(rc.key>=L.r[j].key) break;        //rc应插入在位置s上
194         L.r[s]=L.r[j];
195         HeapMove++;
196         s=j;                                 
197     }
198     L.r[s]=rc;
199     HeapMove++;     //插入
200 }
201 
202 void CreatHeap(sq &L)                       //建初堆
203 {//将无序序列建成大根堆
204     int n=L.len;
205     for(int i=n/2;i>0;--i)
206     {
207         HeapAdjust(L,i,n);                //反复调用HeapAdjust
208     }
209 }
210 
211 void HeapSort(sq &L)        //堆排序
212 {
213     CreatHeap(L);           //建成大堆根
214     for(int i=L.len;i>1;--i)
215     {
216         ElemType x=L.r[i];   //将堆顶记录和当前未经排序子序列L.r[1..i]中最后一个记录互换
217         L.r[1]=L.r[i];
218         L.r[i]=x;
219         HeapMove+=2;
220         HeapAdjust(L,1,i-1);//重新调整为大根堆
221     }
222 }
223 
224 void show(sq L){
225     for(int i=1;i<=L.len;i++)
226         cout<<L.r[i].key<<' ';
227     puts("");
228 }//输出函数
229  
230 int main(){
231     int temp=100;
232     for(int i=1;i<=5;i++)
233     {//100~1000000
234         InsertMove=0,InsertComp=0,
235         BInsertMove=0,BInsertComp=0,
236         QComp=0,QMove=0,
237         BubbleComp=0,BubbleMove=0,
238         ShellComp=0,ShellMove=0; 
239         maxn=temp;
240         cout<<"当前数量级是"<<temp<<endl;  
241         CreateNum();//生成一组随机数
242         sq L=init();
243         double s=clock();//C++里面提供了一个clock()函数(它被<time.h>头文件收录)可以用于计算程序某个环节运行时间
244         InsertSort(L);
245         double e=clock();
246         if(temp==100)
247             show(L);
248         cout<<"直接插入排序时间是"<<e-s<<"ms"<<endl;
249         cout<<"直接插入移动次数是"<<InsertMove<<endl;
250         cout<<"直接插入比较次数是"<<InsertComp<<endl<<endl;
251         
252        /* L=init();//还原无序的顺序表
253         s=clock();
254         BInsertSort(L);
255         e=clock();
256         cout<<"二分插入排序时间是"<<e-s<<"ms"<<endl;
257         cout<<"二分插入移动次数是"<<BInsertMove<<endl;
258         cout<<"二分插入比较次数是"<<BInsertComp<<endl<<endl;*/
259         
260         L=init();//还原无序的顺序表
261         s=clock();
262         QuickSort(L);
263         e=clock();
264         if(temp==100)
265             show(L);
266         cout<<"快排时间是"<<e-s<<"ms"<<endl;
267         cout<<"快排移动次数是"<<QMove<<endl;
268         cout<<"快排比较次数是"<<QComp<<endl<<endl;
269         
270         L=init();
271         s=clock();
272         ShellSort(L,3);// dt 5 3 1 -> 3
273         e=clock();
274         if(temp==100)
275             show(L);
276         cout<<"希尔排序时间是"<<e-s<<"ms"<<endl;
277         cout<<"希尔排序移动次数是"<<ShellMove<<endl;
278         cout<<"希尔排序比较次数是"<<ShellComp<<endl<<endl;
279         
280         L=init();
281         s=clock();
282         BubbleSort(L);
283         e=clock();
284         if(temp==100)
285             show(L);
286         cout<<"冒泡排序时间是"<<e-s<<"ms"<<endl;
287         cout<<"冒泡排序移动次数是"<<BubbleMove<<endl;
288         cout<<"冒泡排序比较次数是"<<BubbleComp<<endl<<endl;
289 
290         L=init();
291         s=clock();
292         SelectSort(L);
293         e=clock();
294         if(temp==100)
295             show(L);
296         cout<<"简单选择排序时间是"<<e-s<<"ms"<<endl;
297         cout<<"简单选择排序移动次数是"<<BubbleMove<<endl;
298         cout<<"简单选择排序比较次数是"<<BubbleComp<<endl<<endl;
299         
300         L=init();
301         s=clock();
302         HeapSort(L);
303         e=clock();
304         if(temp==100)
305             show(L);
306         cout<<"堆排序时间是"<<e-s<<"ms"<<endl;
307         cout<<"堆排序移动次数是"<<BubbleMove<<endl;
308         cout<<"堆排序比较次数是"<<BubbleComp<<endl<<endl;
309         
310         temp*=10;
311         cout<<"------------------------------------------"<<endl;
312     }
313     return 0;
314 }

View Code