1.实验步骤：先定义顺序表的结点：typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SqList;然后定义一个随机取数的函数，存到顺序表中：void CreateList(SqList &L,int n)然后定义一个显示顺序表的函数，将顺序表中的数据显示出来：void ListTraverse(SqList L)然后通过排序函数，将所有的数据按照从大到小的顺序排列：void BubbleSort(SqList &L)实验结果：测试数据：38 86 9 88 29 18 58 27排序后：9 18 27 29 38 58 86 88BubbleSort排序方法中数据的比较次数为：27疑难小结：这个程序的难点在于排序函数，总是把从第几个数开始排序以及怎样循环弄错。

源代码：#include<iostream>using namespace std;#include<time.h>typedef int KeyType;typedef char * InfoType;typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SqList;int CmpNum;void CreateList(SqList &L,int n){int i;L.R=new ElemType[n+1];srand(time(0));for(i=1;i<=n;i++){L.R[i].key=rand()%100;}L.length=n;}void ListTraverse(SqList L){int i;for(i=1;i<=L.length;i++)cout<<L.R[i].key<<'\t';cout<<endl;}void BubbleSort(SqList &L){int m,flag,i;m=L.length-1;flag=1;while(m>0&&flag){flag=0;for(i=1;i<=m;i++){CmpNum++;if(L.R[i].key>L.R[i+1].key){flag=1;L.R[0]=L.R[i+1];L.R[i+1]=L.R[i];L.R[i]=L.R[0];}}m--;}}void main(){SqList L;CreateList(L,8);cout<<"测试数据："<<endl;ListTraverse(L);BubbleSort(L);cout<<"排序后："<<endl;ListTraverse(L);cout<<"BubbleSort排序方法中数据的比较次数为："<<CmpNum<<endl; }2实验步骤：先声明一个结点：typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SqList;然后建立一个建表函数：void CreateList(SqList &L)，将十个关键字输入到表中。

建立一个遍历函数void ListTraverse(SqList L)用以显示排序前后的数据。

分别建立四个排序方法：（1）直接插入排序：void InsertSort(SqList &L)（2）折半插入排序void InsertSort(SqList &L)（3）希尔排序：void ShellSort(SqList &L , int dt[] , int t) void ShellInsert(SqList &L , int dk)（4）快速排序：int Partition(SqList &L , int low, int high) void QSort(SqList &L , int low, int high) void QuickSort(SqList &L)实验结果：测试数据：1. 增量为2 ，该算法执行3趟测试数据：12 2 16 30 28 10 16 20 6 18排序后：2 6 10 12 16 16 18 20 28 30该算法比较的次数为：21 次Process returned 0 (0x0) execution time : 0.203 sPress any key to continue.2.测试数据：12 2 16 30 28 10 16 20 6 18排序后：2 6 10 12 16 16 18 20 28 30Process returned 0 (0x0) execution time : 0.016 sPress any key to continue.3.疑难小结，我感觉，希尔排序，和快速排序很难理解。

尤其是快速排序，枢轴换来换去，感觉很乱。

源代码：#include<iostream>using namespace std;int a = 0;typedef int KeyType;typedef char * InfoType;typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SqList;void CreateList(SqList &L){L.R=new ElemType[11];L.R[1].key=12;L.R[2].key=2;L.R[3].key=16;L.R[4].key=30;L.R[5].key=28;L.R[6].key=10;L.R[7].key=16;L.R[8].key=20;L.R[9].key=6;L.R[10].key=18;}void ListTraverse(SqList L){int i;for(i=1;i<=10;i++)cout<<L.R[i].key<<'\t';cout<<endl;}void InsertSort(SqList &L){int i,j;for( i=2;i<10;++i){if(L.R[i].key<L.R[i-1].key){L.R[0] = L.R[i];L.R[i] = L.R[i-1];for(j=i-2;L.R[0].key<L.R[j].key;--j) L.R[j+1] = L.R[j];L.R[j+1] = L.R[0];}a++;}}int main(){SqList L;CreateList(L);cout<<"测试数据："<<endl;ListTraverse(L);InsertSort(L);cout<<"排序后："<<endl;ListTraverse(L);cout<<"该算法比较的次数为："<<a <<" 次"<<endl;return 0;}//============================================ #include<iostream>using namespace std;int a = 0;typedef int KeyType;typedef char * InfoType;typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SqList;void CreateList(SqList &L){L.R=new ElemType[11];L.R[1].key=12;L.R[2].key=2;L.R[3].key=16;L.R[4].key=30;L.R[5].key=28;L.R[6].key=10;L.R[7].key=16;L.R[8].key=20;L.R[9].key=6;L.R[10].key=18;}void ListTraverse(SqList L){int i;for(i=1;i<=10;i++)cout<<L.R[i].key<<'\t';cout<<endl;}void InsertSort(SqList &L){int i , j , high, low , m;for( i =2 ; i<=10 ; i++){L.R[0] = L.R[i];low=1 , high=i-1;while(low<=high){m=(low+high)/2;if(L.R[0].key<L.R[m].key)high = m-1;else low = m+1;}for(j=i-1 ; j>=high+1;j--)L.R[j+1] = L.R[j];L.R[high+1]=L.R[0];a++;}}int main(){SqList L;CreateList(L);cout<<"测试数据："<<endl;ListTraverse(L);InsertSort(L);cout<<"排序后："<<endl;ListTraverse(L);cout<<"该算法比较的次数为："<<a <<" 次"<<endl;return 0;}//==================================================#include<iostream>using namespace std;int a = 0;typedef int KeyType;typedef char * InfoType;typedef struct{KeyType key;InfoType otherinfo;}ElemType;typedef struct{ElemType *R;int length;}SqList;void CreateList(SqList &L){L.R=new ElemType[11];L.R[1].key=12;L.R[2].key=2;L.R[3].key=16;L.R[4].key=30;L.R[5].key=28;L.R[6].key=10;L.R[7].key=16;L.R[8].key=20;L.R[9].key=6;L.R[10].key=18;}void ListTraverse(SqList L){int i;for(i=1;i<=10;i++)cout<<L.R[i].key<<'\t';cout<<endl;}void ShellInsert(SqList &L , int dk){int i,j;for(i = dk+1 ; i<=10 ; ++i){if(L.R[i].key<L.R[i-dk].key){L.R[0] = L.R[i];for(j=i-dk ; j>0&& L.R[0].key < L.R[j].key ; j-=dk) {L.R[j+dk] = L.R[j];}L.R[j+dk] = L.R[0];}a++;}}void ShellSort(SqList &L , int dt[] , int t){int k;for(k = 0 ; k<t ; ++k){ShellInsert(L,dt[k]);}}int main(){SqList L;int t;int dt[3]={5,3,1};t=3;cout << "增量为2 ，该算法执行3趟"<<endl<<endl;CreateList(L);cout<<"测试数据："<<endl;ListTraverse(L);ShellSort(L,dt,t);cout<<"排序后："<<endl;ListTraverse(L);cout<<"该算法比较的次数为："<<a <<" 次"<<endl;return 0;}//============================================== #include<iostream>using namespace std;int a = 0;typedef int KeyType; typedef char * InfoType; typedef struct{KeyType key;InfoType otherinfo; }ElemType;typedef struct{ElemType *R;int length;}SqList;void CreateList(SqList &L) {L.R=new ElemType[11]; L.R[1].key=12;L.R[2].key=2;L.R[3].key=16;L.R[4].key=30;L.R[5].key=28;L.R[6].key=10;L.R[7].key=16;L.R[8].key=20;L.R[9].key=6;L.R[10].key=18;}void ListTraverse(SqList L){int i;for(i=1;i<=10;i++)cout<<L.R[i].key<<'\t';cout<<endl;}int Partition(SqList &L , int low, int high){KeyType pivotkey;L.R[0] = L.R[low];pivotkey = L.R[low].key;while(low<high){while(low<high && L.R[high].key>pivotkey) --high; L.R[low] = L.R[high];while(low<high && L.R[low].key<=pivotkey) ++low; L.R[high]=L.R[low];}L.R[low] = L.R[0];return low;}void QSort(SqList &L , int low, int high){KeyType pivotloc;if(low<high){pivotloc = Partition(L,low,high);QSort(L, low ,pivotloc-1);QSort(L,pivotloc+1,high);}}void QuickSort(SqList &L){QSort(L,1,L.length);}int main(){SqList L;L.length = 10;CreateList(L);cout<<"²âÊÔÊý¾Ý£º"<<endl;ListTraverse(L);QuickSort(L);cout<<"ÅÅÐòºó£º"<<endl;ListTraverse(L);return 0;}。