排序算法的实现(C/C++实现)详解编程语言

 1 #include <iostream> 
 2 #include <stdlib.h> 
 3 #include <sort.h> 
 4 #define maxsize 20 
 5 using namespace std; 
 6 int main() 
 7 { 
 8     sqlist l; 
 9     int num; 
10     init(l); 
11     create(l); 
12     show(l); 
13     cout<<"*******************************************"<<endl; 
14     cout<<"1.直接插入排序"<<endl; 
15     cout<<"2.冒泡排序"<<endl; 
16     cout<<"3.简单选择排序"<<endl; 
17     cout<<"4.输出表信息"<<endl; 
18     cout<<"5.生成新的关键字序列"<<endl; 
19     cout<<"6.退出"<<endl; 
20     cout<<"*******************************************"<<endl; 
21     cout<<"请输入您的选择:"<<endl; 
22     cin.clear(); 
23     cin>>num; 
24     while(1) 
25     { 
26         switch(num) 
27         { 
28             case 1: 
29                 insertsort(l); 
30                 break; 
31             case 2: 
32                 bubblesort(l); 
33                 break; 
34             case 3: 
35                 selectsort(l); 
36                 break; 
37             case 4: 
38                 show(l); 
39                 break; 
40             case 5: 
41                 create(l); 
42                 break; 
43             case 6: 
44                 exit(0); 
45                 break; 
46             default: 
47                 cout<<"输入错误!"; 
48         } 
49         cout<<endl; 
50         cout<<"请重新输入您的选择:"<<endl; 
51         cin>>num; 
52     } 
53     return 0; 
54 }

  1 typedef struct 
  2 { 
  3     int key; 
  4     char *otherinfo; 
  5 }elemtype;//数据元素类型  
  6 typedef struct 
  7 { 
  8     elemtype r[maxsize];//存储空间的基地址  
  9     int length;//顺序表长度  
 10 }sqlist;//顺序表类型  
 11 void init(sqlist &l)//初始化  
 12 { 
 13     l.length=0; 
 14 } 
 15 void create(sqlist &l)//创建表  
 16 { 
 17     int i,n; 
 18     cout<<"请输入数据个数,不超过"<<maxsize<<"个."<<endl; 
 19     cin>>n;//输入数据元素  
 20     cout<<"请输入待排序的数据:"<<endl; 
 21     while(n>maxsize) 
 22     { 
 23         cout<<"个数超过上限,不能超过"<<maxsize<<",请重新输入"<<endl; 
 24         cin>>n; 
 25     } 
 26     for(i=1;i<=n;i++) 
 27     { 
 28         cin>>l.r[i].key; 
 29         l.length++; 
 30     }  
 31 } 
 32 void show(sqlist l)//输出显示  
 33 { 
 34     int i; 
 35     for(i=1;i<=l.length;i++) 
 36         cout<<l.r[i].key<<"  "; 
 37     cout<<endl; 
 38 } 
 39 void insertsort(sqlist l)//直接插入排序 
 40 { 
 41     int i,j; 
 42     for(i=2;i<=l.length;i++) 
 43     { 
 44         if(l.r[i].key<l.r[i-1].key)//"<",需将r[i]插入有序子表  
 45         { 
 46             l.r[0]=l.r[i];//将待插入的记录暂存到监视哨中  
 47             l.r[i]=l.r[i-1];//r[i-1]后移  
 48             for(j=i-2;l.r[0].key<l.r[j].key;j--)//从后向前寻找插入位置  
 49                 l.r[j+1]=l.r[j];//记录逐个后移,直到找到插入位置  
 50             l.r[j+1]=l.r[0];//将r[0]即原r[i],插入到正确位置  
 51         } 
 52         cout<<"第"<<i-1<<"趟排序结果:"; 
 53         show(l); 
 54     } 
 55     cout<<"直接插入排序最终结果为:"; 
 56     show(l); 
 57 } 
 58 void bubblesort(sqlist l)//冒泡排序  
 59 { 
 60     int m,j,flag; 
 61     elemtype t; 
 62     m=l.length-1;//共n-1趟冒泡  
 63     flag=1;//flag用来标记某一趟排序是否发生交换,1表示交换,0表示未交换  
 64     while((m>0)&&(flag==1)) 
 65     { 
 66         flag=0;//flag置为0,如果本趟排序没有发生交换,则不会执行下一趟排序  
 67         for(j=1;j<=m;j++) 
 68         { 
 69             if(l.r[j].key>l.r[j+1].key) 
 70             { 
 71                 flag=1;//flag置为1,表示本趟排序发生了交换  
 72                 t=l.r[j]; 
 73                 l.r[j]=l.r[j+1]; 
 74                 l.r[j+1]=t;//交换前后两个记录  
 75             } 
 76         } 
 77         cout<<"第"<<l.length-m<<"趟排序结果:"; 
 78         show(l); 
 79         m--; 
 80     } 
 81     cout<<"冒泡排序最终结果为:"; 
 82     show(l);     
 83 } 
 84 void selectsort(sqlist l)//简单选择排序  
 85 { 
 86     int i,j,k; 
 87     elemtype t; 
 88     for(i=1;i<l.length;i++) 
 89     { 
 90         k=i;//在l.r[i...l.length]中选择关键字最小的记  
 91         for(j=i+1;j<=l.length;j++) 
 92         { 
 93             if(l.r[j].key<l.r[k].key) 
 94             { 
 95                 k=j;//k指向此趟排序中关键字最小的记  
 96             } 
 97         } 
 98         if(k!=i)//交换r[i]与r[k]  
 99         { 
100             t=l.r[i]; 
101             l.r[i]=l.r[k]; 
102             l.r[k]=t; 
103         } 
104         cout<<"第"<<i<<"趟排序结果:"; 
105         show(l); 
106     } 
107     cout<<"简单选择排序最终结果为:"; 
108     show(l); 
109 }