6大排序算法比较

  1 #include"stdio.h"
  2 #include"stdlib.h"
  3 #include"string.h"
  4 #include"time.h"
  5 
  6 #define LIST_INIT_SIZE 50000
  7 int bj1,yd1,bj2,yd2,bj3,yd3,bj4,yd4,bj5,yd5,bj6,yd6,n;//yd,bj为记录关键字比较和移动的次数 
  8 
  9 struct ElemType
 10 {
 11     int key;
 12 };
 13 
 14 struct SqList//线性表
 15 {
 16     ElemType *elem;
 17     int length;
 18 };
 19 
 20 
 21 void Createlist(SqList &L)//初始化顺序表的，确定输入数据个数n 
 22 {
 23     int flags = 1;
 24     while(flags)
 25     {
 26         printf("请输入数据个数:");
 27         scanf("%d",&n);
 28         if(n>50000)
 29         {
 30             printf("超出范围重新输入!!!\n");
 31         }else flags = 0;//跳出循环
 32     }
 33     L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配内存
 34     if(!L.elem)exit(0);
 35 }
 36 
 37 void Random(SqList &L)//随机数产生程序 
 38 {
 39     L.length=0;//数据初始为0
 40     srand(time(0));//使输入相同个数时每次产生的随机数不同 
 41 
 42     for(int i=1;i<n+1;i++)
 43     {
 44         L.elem[i].key=rand();//产生随机数
 45         while(L.elem[i].key>50000)L.elem[i].key=rand();//保证数据早50000以内
 46         L.length++;//数据个数+1
 47     }
 48 }
 49 
 50 void Memory(SqList &M,SqList &L)//记录L,使每个排序算法都用一组相同的随机数 
 51 {
 52     int i = 1 ;
 53     M.length=0;//顺序表M初始长度为0
 54     while(i<=L.length)//顺序表L中的元素赋给顺序表M中
 55     {
 56         M.elem[i].key=L.elem[i].key;
 57         M.length++;
 58         i++;
 59     }
 60 }
 61 
 62 void BubbleSort(SqList &L)//冒泡排序 
 63 {
 64     int i,j;
 65     for(i=1;i<L.length;i++)
 66     { 
 67         for(j=1;j<L.length-i+1;j++)
 68         {
 69             bj1++;//比较次数+1
 70             if(L.elem[j].key>L.elem[j+1].key)//关键字交换
 71             {
 72                 L.elem[0].key=L.elem[j].key;
 73                 L.elem[j].key=L.elem[j+1].key;
 74                 L.elem[j+1].key=L.elem[0].key;
 75                 yd1+=3;//关键字交换次数+3
 76             }
 77         }
 78     }
 79 }
 80 
 81 void InsertSort(SqList &L)//直接插入排序 
 82 {
 83     int i,j;
 84     for(i=2;i<=L.length;i++)
 85     {
 86         if(L.elem[i].key<L.elem[i-1].key)
 87         {
 88             L.elem[0].key=L.elem[i].key;
 89             yd2++;//比较次数+1
 90             j=i-1;
 91             bj2++;//交换次数+1
 92             while(L.elem[0].key<L.elem[j].key)
 93             {
 94                 L.elem[j+1].key=L.elem[j].key;
 95                 j--;
 96                 yd2++;//比较次数+1
 97                 bj2++;//交换次数+1
 98             }
 99             L.elem[j+1].key=L.elem[0].key;
100             yd2++;//比较次数+1
101         }
102     }
103 }
104 
105 
106 
107 void SelectSort(SqList &L)//选择排序 
108 {
109     int i,j,k;
110     for(i=1;i<L.length;i++)
111     {
112         k=i;
113         for(j=i+1;j<=L.length;j++)
114         {
115             bj3++;//比较次数+1
116             if(L.elem[j].key<L.elem[k].key)k=j;
117         }
118         if(i!=k)
119         {
120             L.elem[0].key=L.elem[i].key;
121             L.elem[i].key=L.elem[k].key;
122             L.elem[k].key=L.elem[0].key;
123             yd3+=3;//交换次数+3
124         }
125     }
126 }
127 
128 
129 int Partition(SqList &L,int low,int high)//快速排序 
130 {
131     int pivotkey;
132     L.elem[0]=L.elem[low];
133     yd4++;//交换次数+1
134     pivotkey=L.elem[low].key;
135     while (low<high)
136     {
137         yd4++;//交换次数+1
138         while(low<high&&L.elem[high].key>=pivotkey)
139             high--;
140             L.elem[low]=L.elem[high];
141             bj4++;//比较次数+1
142             yd4++;//交换次数+1
143         while (low<high&&L.elem[low].key<=pivotkey)
144             low++;
145             L.elem[high]=L.elem[low];
146             bj4++;//比较次数+1
147             yd4++;//交换次数+1
148     }
149     L.elem[low]=L.elem[0];
150     yd4++;//交换次数+1
151     return low;
152 }
153 void QSort(SqList &L,int low,int high)//对顺序表的子序列作快速排序 
154 {
155     int pivotloc;
156     if(low<high)
157     {
158         pivotloc=Partition(L,low,high);
159         QSort(L,low,pivotloc-1);
160         QSort(L,pivotloc+1,high);
161     }
162 }
163 
164 void QuickSort(SqList &L)//对顺序表L作快速排序 
165 {
166     QSort(L,1,L.length);
167 }
168 
169 
170 void ShellSort(SqList &L)//希尔排序 
171 {
172     int dh,i,j;
173     dh=L.length/2;
174     while(dh>=1){
175         for( i=dh;i<=L.length;i++){
176             L.elem[0].key=L.elem[i].key;
177             yd5+=1;//交换次数+1
178             j=i-dh;
179             while(j>=0&&L.elem[j].key>L.elem[0].key){
180                 L.elem[j+dh].key =  L.elem[j].key;
181                 bj5+=1;//比较次数+1
182                 yd5+=1;//交换次数+1    
183                 j-=dh;
184             }
185             L.elem[j+dh].key =  L.elem[0].key;
186             yd5+=1;//交换次数+1    
187         }
188         dh/=2;
189     }
190 }
191 
192 /*
193 *调整数组A中以K为根的子序列为堆，其中最大的元素下标为m
194 *假设以2k,2k+1为根的左右子树均是堆
195 */
196 void HeapAdjust(SqList &L,int k,int m)
197 {
198     int i,j,x;
199     int finished = 0;
200 
201     x =L.elem[k].key;//临时保存当前根植
202     yd6+=1;//交换次数+1
203     i = k;//指示空位
204     j = 2*i;//j先指向其左孩子结点
205     while(j<=m &&!finished)//确定i结点不是叶子节点且搜索未结束
206     {
207         if((j<m)&&(L.elem[j].key<L.elem[j+1].key))
208         {
209             j++;//让j指向左右孩子中的最大者
210             bj6++;//比较次数+1
211         }
212         if(x>=L.elem[j].key)finished = 1;//若原根最大，置搜索和帅选结束标志
213         else{
214             L.elem[i].key = L.elem[j].key;//大的孩子结点值上移
215             yd6+=1;//交换次数+1
216             i = j;//继续往下帅选：i指示新的空位，j相应改变
217             j*=2;
218         }
219     }
220     L.elem[i].key = x;//将原根值填充到所搜索到的当前的空位置中
221     yd6+=1;//交换次数+1
222 }
223 
224 
225 void HeapSort(SqList &L)
226 {
227     int i;
228 
229     for(i=L.length/2;i>=1;i--)
230     {
231         HeapAdjust(L,i,n);//建初始堆
232     }
233     for(i=L.length;i>=2;i--)//控制排序过程
234     {
235         
236         L.elem[0] = L.elem[1];
237         L.elem[1] = L.elem[i];
238         L.elem[i] = L.elem[0];
239         yd6+=3;//交换次数+3
240         HeapAdjust(L,1,i-1);//调整子序列Array[1]~Array[i-1]为堆
241     }
242     
243 }
244 
245 void  print(SqList &L)//输出顺序表重元素
246 {
247     int i;
248     for(i=1;i<=L.length;i++)
249     {
250         printf("%d  ",L.elem[i]);
251         if(i%5==0)printf("\n");
252     }
253     printf("\n");
254 }
255 
256 int  main()
257 {
258 
259     int a,flags  = 1;
260     while(flags)
261     {
262         printf(" -------------内部排序------------------\n");
263         printf("|-------------欢迎使用------------------|\n");
264         printf("|-----------(1)运行程序-----------------|\n");
265         printf("|-----------(0)退出系统 ----------------|\n");
266         printf("请选择:");
267         scanf("%d",&a);
268         while(a!=0&&a!=1)
269         {
270             printf("输入有误,请输入0|1:");
271             scanf("%d",&a);
272         }
273         switch(a)
274         {
275         case 0:
276             printf("谢谢使用!\n");
277             flags = 0;
278             break;
279         case 1:
280             system("cls");//清屏
281             SqList L,M;
282             M.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
283             if(!M.elem)exit(0);
284             bj1=0,yd1=0,bj2=0,yd2=0,bj3=0,yd3=0,bj4=0,yd4=0,bj5=0,yd5=0,bj6=0,yd6=0;
285             Createlist(L);
286             Random(L);//产生数据
287 
288             Memory(M,L);
289             BubbleSort(M);//冒泡排序
290 
291             Memory(M,L);
292             InsertSort(M);//插入排序
293 
294             Memory(M,L);
295             SelectSort(M);//选择排序
296 
297             Memory(M,L);
298             QuickSort(M);//快速排序
299 
300             Memory(M,L);
301             ShellSort(M);//希尔排序
302 
303             Memory(M,L);
304             HeapSort(M);//堆排序
305 
306             printf("         比较次数      移动次数\n");
307             printf("冒泡排序:%d\t\t%d\n",bj1,yd1);
308             printf("直接插入:%d\t\t%d\n",bj2,yd2);
309             printf("简单选择:%d\t\t%d\n",bj3,yd3);
310             printf("快速排序:%d\t\t%d\n",bj4,yd4);
311             printf("希尔排序:%d\t\t%d\n",bj5,yd5);
312             printf("堆排序:  %d\t\t%d\n",bj6,yd6);
313             break;
314         }
315     }
316     return 0;    
317 }