排序算法的实现(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 }