（1）使用VC++语言编写程序，分别实现以下算法：插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序。

（2）编译运行以上算法程序，在运行过程中观察它们的执行过程和结果，给出比较结果。

编程员:lghgxu

程序源代码：

一、插入排序

#include "stdio.h"

# include "stdlib.h"

# define  OVERFLOW       -2

typedef struct 

{  int * elem;

   int  length;

}SqList;

SqList create(int n)//建立一个顺序表

{  SqList L;

   L.elem = (int *)malloc( n*sizeof(int));

   if(!L.elem) exit(OVERFLOW);

   L.length=n;

for(int j=1;j   { printf("请输入第%d个整数:\\n",j );

     scanf("%d",&L.elem[j]);

   }

   return L;

}

void InsertSort(SqList &L) // 对顺序表L作直接插入排序。

{   int i,j;int count=0;

for (i=2; i if (L.elem[i]    {   count++;

        L.elem[0] = L.elem[i];                      // 复制为哨兵

for (j=i-1; L.elem[0]          L.elem[j+1] = L.elem[j];                    // 记录后移

          L.elem[j+1] = L.elem[0];// 插入到正确位置

          printf("第%d轮排序顺序如下：\\n",count);

for (int k=1; k          printf("%6d",L.elem[k]);

          printf("\\n");

    }

} // InsertSort

void main()

{  SqList T;

   int n=0,flag=0;

   char yes_no;

    do 

    {   do

    {   printf("请输入顺序表的长度(大于0)(第一个存储单元不存数据)：\\n");

        scanf("%d",&n);

}while(n<=0);

     T=create(n);

    InsertSort(T);

     printf("数据排序后如下：\\n");

for(int i=1;i     {printf("%5d",T.elem[i]);}

    printf("\\n");

     do

     {  printf("如果想继续验证请输入Y或y,否则输入N或n：\\n\\n");

        scanf("%s",&yes_no);

     }while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');

   }while(yes_no=='Y'||yes_no=='y');

}

运行结果：

请输入顺序表的长度(大于0)(第一个存储单元不存数据)：

8

请输入第1个整数:

12

请输入第2个整数:

23

请输入第3个整数:

34

请输入第4个整数:

45

请输入第5个整数:

45

请输入第6个整数:

56

请输入第7个整数:

67

数据排序后如下：

   12   23   34   45   45   56   67

如果想继续验证请输入Y或y,否则输入N或n：

二、冒泡排序

#include "stdio.h"

# include "stdlib.h"

# define  OVERFLOW       -2

typedef struct 

{  int * elem;

   int  length;

}SqList;

SqList create(int n)//建立一个顺序表

{  SqList L;

   L.elem = (int *)malloc( n*sizeof(int));

   if(!L.elem) exit(OVERFLOW);

   L.length=n;

for(int j=0;j   { printf("请输入第%d个整数:\\n",j+1 );

     scanf("%d",&L.elem[j]);

   }

   return L;

}

void InsertSort(SqList &L) // 冒泡排序。

{   int i,j,temp;

for (i=1; i { for (j=i; j { if (L.elem[j]    {      temp=L.elem[j-1];

            L.elem[j-1]=L.elem[j];

            L.elem[j]=temp;

    }

    }

     printf("第%d轮排序顺序如下：\\n",i);

for (int k=1; k     printf("%6d",L.elem[k]);

     printf("\\n");

    }

} // InsertSort

void main()

{  SqList T;

   int n=0,k,flag=0;

   char yes_no;

    do 

    {   do

        { printf("请输入顺序表的长度(大于0)：\\n");

         scanf("%d",&n);

}while(n<=0);

     T=create(n);

     InsertSort(T);

     do

     {  printf("如果想继续验证请输入Y或y,否则输入N或n：\\n\\n");

        scanf("%s",&yes_no);

     }while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');

   }while(yes_no=='Y'||yes_no=='y');

}

运行结果：

请输入顺序表的长度(大于0)(第一个存储单元不存数据)：

8

请输入第1个整数:

12

请输入第2个整数:

32

请输入第3个整数:

34

请输入第4个整数:

4

请输入第5个整数:

12

请输入第6个整数:

请输入第7个整数:

56

第1轮排序顺序如下：

     4    12    32    34    12        56

第2轮排序顺序如下：

     4    12    12    32    34        56

第3轮排序顺序如下：

     4    12    12    32    34    56    

数据排序后如下：

    4   12   12   32   34   56   

如果想继续验证请输入Y或y,否则输入N或n：

三、快速排序

#include     "stdio.h"

# include    "stdlib.h"

# define      OVERFLOW       -2

typedef struct 

{  int * elem;

   int  length;

}SqList;

SqList create(int n)//建立一个顺序表

{  SqList L;

   L.elem = (int *)malloc( n*sizeof(int));

   if(!L.elem) exit(OVERFLOW);

   L.length=n;

for(int j=1;j   { printf("请输入第%d个整数:\\n",j );

     scanf("%d",&L.elem[j]);

   }

 printf("输入的数据如下:\\n",j );

for(int k=1;k         printf("%6d",L.elem[k]);

     printf("\\n");

   return L;

}

int Partition(SqList &L, int low, int high)

{  // 交换顺序表L中子序列L.elem[low..high]的记录，使枢轴记录到位，

   // 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它

   int pivotkey;

   L.elem[0] = L.elem[low];      // 用子表的第一个记录作枢轴记录

   pivotkey = L.elem[low];       // 枢轴记录关键字

while (low while (low=pivotkey) --high;

      L.elem[low] = L.elem[high];      // 将比枢轴记录小的记录移到低端

while (low      L.elem[high] = L.elem[low];      // 将比枢轴记录大的记录移到高端

   }

   L.elem[low] = L.elem[0];            // 枢轴记录到位

   return low;                         // 返回枢轴位置

} // Partition

void QSort(SqList &L, int low, int high) { 

  // 对顺序表L中的子序列L.r[low..high]进行快速排序

  int pivotloc;

if (low < high)

  { pivotloc = Partition(L, low, high);  // 将L.elem[low..high]一分为二

    QSort(L, low, pivotloc-1);           // 对低子表递归排序，pivotloc是枢轴位置

    QSort(L, pivotloc+1, high);          // 对高子表递归排序

  }

} // QSort

SqList QuickSort(SqList &L)

{  QSort(L,1,L.length);

   return L;

} 

void main()

{   SqList T;

    int n,low, high;

    char yes_no;

    do 

    {   do

    {   printf("请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：\\n");

        scanf("%d",&n);

}while(n<=0);

     T=create(n);    

     T=QuickSort(T);

     printf("排序后数据如下：\\n");

for(int k=2;k<=n;k++)

         printf("%6d",T.elem[k]);

     printf("\\n");

     do

     {  printf("如果想继续验证请输入Y或y,否则输入N或n：\\n\\n");

        scanf("%s",&yes_no);

     }while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');

   }while(yes_no=='Y'||yes_no=='y');

}

运行结果：

请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：

9

请输入第1个整数:

12

请输入第2个整数:

43

请输入第3个整数:

456

请输入第4个整数:

7

请输入第5个整数:

4

请输入第6个整数:

78

请输入第7个整数:

78

请输入第8个整数:

45

输入的数据如下:

    12    43   456     7     4    78    78    45

排序后数据如下：

     4     7    12    43    45    78    78   456

如果想继续验证请输入Y或y,否则输入N或n：

四、归并排序#include "stdio.h"

# include "stdlib.h"

# define  OVERFLOW       -2

typedef struct 

{  int * elem;

   int  length;

}SqList;

SqList create(int n)//建立一个顺序表

{  SqList L;

   L.elem = (int *)malloc( n*sizeof(int));

   if(!L.elem) exit(OVERFLOW);

   L.length=n;

for(int j=0;j   { printf("请输入第%d个整数:\\n",j+1 );

     scanf("%d",&L.elem[j]);

   }

   return L;

}

void Merge(SqList L,SqList &T, int i, int m, int n) 

{

   // 将有序的L[i..m]和SR[m+1..n]归并为有序的T[i..n]

   int j,k;

for (j=m+1, k=i; i<=m && j<=n; ++k) {

      // 将L中记录由小到大地并入T

if (L.elem[i]      else T.elem[k] = L.elem[j++];

   }

if (i<=m) // T[k..n] = L[i..m]; 将剩余的L[i..m]复制到T

while (k<=n && i<=m) T.elem[k++]=L.elem[i++];

if (j<=n) // 将剩余的L[j..n]复制到T

while (k<=n &&j <=n) T.elem[k++]=L.elem[j++];

} // Merge

void MSort(SqList L,SqList &T, int s, int t) { 

   // 将L[s..t]归并排序为T[s..t]。

   int m;

   SqList w;

       w.elem=(int *)malloc( 20*sizeof(int));

   if(!w.elem) exit(OVERFLOW);

   w.length=20;

   if (s==t) T.elem[t] = L.elem[s];

   else {

      m=(s+t)/2;            // 将L[s..t]平分为L[s..m]和L[m+1..t]

      MSort(L,w,s,m);    // 递归地将L[s..m]归并为有序的W[s..m]

      MSort(L,w,m+1,t);  // 将L[m+1..t]归并为有序的W[m+1..t]

      Merge(w,T ,s,m,t); // 将W[s..m]和TR2[m+1..t]归并到T [s..t]

   }

} // MSort

void MergeSort(SqList &L) { 

  // 对顺序表L作归并排序。

  MSort(L, L, 0, L.length);

} // MergeSort

void main()

{  SqList T;

   int n=0,k,flag=0;

   char yes_no;

    do 

    {   do

    {   printf("请输入顺序表的长度(大于0)：\\n");

        scanf("%d",&n);

}while(n<=0);

     T=create(n);

     MergeSort(T) ;

printf("排序后的顺序如下：\\n");

for(int i=1;i<=T.length;i++)

     {  printf("%5d",T.elem[i]); }

     printf("\\n");

     do

     {  printf("如果想继续验证请输入Y或y,否则输入N或n：\\n\\n");

        scanf("%s",&yes_no);

     }while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');

   }while(yes_no=='Y'||yes_no=='y');

}

运行结果：

请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：

8

请输入第1个整数:

34

请输入第2个整数:

45

请输入第3个整数:

3

请输入第4个整数:

56

请输入第5个整数:

67

请输入第6个整数:

234

请输入第7个整数:

45

输入的数据如下:

    34    45     3    56    67   234    45

排序后数据如下：

     3    34    45    45    56    67   234

如果想继续验证请输入Y或y,否则输入N或n：

五、堆排序

#include "stdio.h"

# include "stdlib.h"

# define  OVERFLOW       -2

typedef struct 

{  int * r;

   int  length;

}SqList;

SqList create(int n)//建立一个顺序表

{  SqList L;

   L.r = (int *)malloc( n*sizeof(int));

   if(!L.r) exit(OVERFLOW);

   L.length=n;

for(int j=0;j   { printf("请输入第%d个整数:\\n",j+1 );

     scanf("%d",&L.r[j]);

   }

   return L;

}

void HeapAdjust(SqList &H, int s, int m) {  // 算法10.10

  // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，

  // 本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆

  // （对其中记录的关键字而言）

  int j;

  int rc;

  rc = H.r[s];

for (j=2*s; j<=m; j*=2)

  { // 沿key较大的孩子结点向下筛选

if (j if (rc >= H.r[j]) break; // rc应插入在位置s上

    H.r[s] = H.r[j];  s = j;

  }

  H.r[s] = rc;  // 插入

} // HeapAdjust

void HeapSort(SqList &H) // 对顺序表H进行堆排序。

{   

   int i;

   int temp;

for (i=H.length/2; i>0; --i) // 把H.r[1..H.length]建成大顶堆

   HeapAdjust( H, i, H.length );

for (i=H.length; i>1; --i)

   {  temp=H.r[i];

      H.r[i]=H.r[1];

      H.r[1]=temp;  // 将堆顶记录和当前未经排序子序列Hr[1..i]中

                       // 最后一个记录相互交换

       HeapAdjust(H, 1, i-1);  // 将H.r[1..i-1] 重新调整为大顶堆

    }

} // HeapSort

void main()

{  SqList T;

   int n;

   char yes_no;

    do 

    {  do

    {   printf("请输入顺序表的长度(大于0)：\\n");

        scanf("%d",&n);

}while(n<=0);

     T=create(n);

     HeapSort(T);

for(int i=0;i<=T.length;i++)

     printf("%6d",T.r[i]);

     printf("\\n");

     do

     {  printf("如果想继续验证请输入Y或y,否则输入N或n：\\n\\n");

        scanf("%s",&yes_no);

     }while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');

   }while(yes_no=='Y'||yes_no=='y');

}

运行结果

请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：

10

请输入第1个整数:

34

请输入第2个整数:

45

请输入第3个整数:

67

请输入第4个整数:

12

请输入第5个整数:

34

请输入第6个整数:

56

请输入第7个整数:

78

请输入第8个整数:

请输入第9个整数:

45

输入的数据如下:

    34    45    67    12    34    56    78        45

排序后数据如下：

    12    34    34    45    45    56    67    78    

如果想继续验证请输入Y或y,否则输入N或n：

六、选择排序

#include     "stdio.h"

# include    "stdlib.h"

# define     OVERFLOW       -2

typedef struct 

{  int * elem;

   int  length;

}SqList;

SqList create(int n)//建立一个顺序表

{  SqList L;

   L.elem = (int *)malloc( n*sizeof(int));

   if(!L.elem) exit(OVERFLOW);

   L.length=n;

for(int j=1;j   { printf("请输入第%d个整数:\\n",j );

     scanf("%d",&L.elem[j]);

   }

   return L;

}

SelectMinKey(SqList &L, int i)

{

void SelectSort(SqList &L)// 对顺序表L作简单选择排序。

 {  int i,j;

for (i=1; i    { j = SelectMinKey(L, i);  // 在L.elem[i..L.length]中选择key最小的记录

     if (i!=j)

     { int temp;              // L.elem[i]←→L.r[j];   与第i个记录交换

       temp=L.elem[i];

       L.elem[i]=L.elem[j];

       L.elem[j]=temp;    

     } 

    }

} // SelectSort

void main()

{  SqList T;

   int n,low, high;

   char yes_no;

    do 

    {   do

    {   printf("请输入顺序表的长度(大于0)：\\n");

        scanf("%d",&n);

}while(n<=0);

     T=create(n);

     printf("请输入low的值：\\n\\n");

     scanf("%d",&low);

     printf("请输入hight的值：\\n\\n");

     scanf("%d",&high);

    T=QSort(T, low,high);

for(int k=0;k         printf("%6d",T.elem[k]);

     printf("\\n");

     do

     {  printf("如果想继续验证请输入Y或y,否则输入N或n：\\n\\n");

        scanf("%s",&yes_no);

     }while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');

   }while(yes_no=='Y'||yes_no=='y');

}

运行结果：

请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：

10

请输入第1个整数:

34

请输入第2个整数:

45

请输入第3个整数:

67

请输入第4个整数:

12

请输入第5个整数:

34

请输入第6个整数:

56

请输入第7个整数:

78

请输入第8个整数:

请输入第9个整数:

45

输入的数据如下:

    34    45    67    12    34    56    78        45

排序后数据如下：

    12    34    34    45    45    56    67    78    

如果想继续验证请输入Y或y,否则输入N或n：