存档:
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 }
运行结果如下: