【设计要求】:
在给出的代码素材sort.cpp文件中补充main函数中的swtich语句,以及以下排序函数,并比较各种排序方法在对素材文件中的1.data~5.data待排序序列进行排序时所需要的时间。

  void shellsort(int data[],int n);//希尔排序 
  void bubllesort(int data[],int n);//冒泡排序 
  void quicksort(int data[],int n);//快速排序 
  void selectsort(int data[],int n);//简单选择排序 
  void heapsort(int data[],int n);//堆排序 
  void mergesort(int data[],int n);//[合并]^(Merge)排序 
  void radixsort(int data[],int n) ;//基数排序

【代码如下】:

#include<stdio.h>
 #include<stdlib.h>
 #include<time.h>
 #define RADIX_10 10    //整形排序  
 #define KEYNUM_31 10   
 #define SOURCEFILE "4.data"
 const int LineLenght = 20;//控制屏幕打印时,每行元素个数 
 const int MaxSize = 30000;
 void Printdata(int data[], int n);//打印数组中个的各个元素 
 int Getdata(int *data, int &n);
 void creatdata(int &n);//产生n个0~1000之间的[随机]^(Random)整数,并写入source.data  
 void insertsort(int data[], int n);//直接插入排序 
 int Outputdata(int data[], int n);
 void shellsort(int data[], int n);//希尔排序 
 void bubllesort(int data[], int n);//冒泡排序 
 void quicksort(int data[], int n);//快速排序 
 void selectsort(int data[], int n);//简单选择排序 
 void heapsort(int data[], int n);//堆排序 
 void mergesort(int data[], int n);//合并排序
 void radixsort(int data[], int n);//基数排序

 int main()
 {
        int n;
        int data[MaxSize];
        char SORCEFILE[10];
        clock_t start, end;
        printf("输入待排序序列所在文件名,例:1.data:");
        scanf("%s", &SORCEFILE);
        Getdata(data, n); //读取文件的数据存放在data数组中  

        int menu;
        printf("请选择排序方式:\n");
        while (1)
        {

               printf("1.  直接插入排序\n");
               printf("2.  希尔插排序\n");
               printf("3.  冒泡排序\n");
               printf("4.  快速排序\n");
               printf("5.  简单选择插入排序\n");
               printf("6.  堆排序\n");
               printf("7.  归并排序\n");
               printf("8.  基数排序\n");
               scanf("%d", &menu);
               switch (menu)
               {
               case 1:{

                      start = clock();
                      insertsort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               case 2:{

                      start = clock();
                      shellsort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               case 3:{

                      start = clock();
                      bubllesort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               case 4:{

                      start = clock();
                      quicksort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               case 5:{

                      start = clock();
                      selectsort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               case 6:{

                      start = clock();
                      heapsort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               case 7:{

                      start = clock();
                      mergesort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               case 8:{

                      start = clock();
                      radixsort(data, n);
                      end = clock();
                      Printdata(data, n);//输出数据 
                      Outputdata(data, n);
                      printf("排序时间为%d毫秒", end - start);
                      printf("您可以尝试一下其它的排序方法:\n");
                      break;
               }
               default: {
                      printf("没有这种排序方式,请选择正确的排序方法:\n");

               }

               }
        }
        return 0;
 }

 void Printdata(int data[], int n)
 {
        for (int i = 0; i<n; i++)
        {
               printf("%4d", data[i]);
               if (i%LineLenght == LineLenght - 1)
                      printf("\n");
        }
        printf("\n");
        return;
 }
 int Getdata(int data[], int &n)
 {

        FILE *fp;
        if ((fp = fopen(SOURCEFILE, "r")) == NULL) /* 以读方式打开文本文件 */
        {
               printf("Failure to open score.txt!\n");
               return 0;//读数据失败 
        }
        int i = 0;
        fscanf(fp, "%6d", &n);//获取文件中的元素个数 

        while (!feof(fp) && i<n)
        {
               fscanf(fp, "%4d", &data[i]);
               i++;
        }
        fclose(fp);
        return 1;  //成功读数据                          
 }
 void insertsort(int data[], int n)//直接插入排序 
 {
        int i, j, x;
        for (i = 1; i<n; i++)
        {
               x = data[i];
               for (j = i - 1; j >= 0; j--)
               {
                      if (data[j]>x)
                             data[j + 1] = data[j];
                      else break;
               }
               if (j != i) data[j + 1] = x;
        }
 }
 int Outputdata(int data[], int n)
 {
        FILE *fp;
        if ((fp = fopen("out.data", "w")) == NULL) /* 以写方式打开文本文件 */
        {
               printf("Failure to open score.txt!\n");
               return 0;//写数据失败 
        }
        for (int i = 0; i<n; i++)
               fprintf(fp, "%4d", data[i]);
        fclose(fp);
        return 1;

 }
 void shellsort(int data[], int n)//希尔排序 
 {
        int a = n;
        do
        {
               a = a / 3 + 1;
               insertsort(data, a);
        } while (a > 1);
 }
 void bubllesort(int data[], int n)//冒泡排序 
 {
        bool kk = true;//优化
        for (int a = 0; a < n - 1 && kk; a++)
        {
               kk = false;
               for (int b = a + 1; b < n; b++)//从前往后扫描
               {
                      if (data[a] > data[b])//从小到大排序
                      {
                             int temp = data[b];//交换
                             data[b] = data[a];
                             data[a] = temp;
                             kk = true;
                      }

               }
        }
 }

 void Qsort(int a[], int left, int right)
 {
        int i, j, t, temp;
        if (left>right)//结束的条件
               return;

        temp = a[left]; //temp中存的就是基准数 
        i = left;
        j = right;
        while (i != j)
        {
               while (a[j] >= temp && i<j)//先从右边开始找
                      j--;
               while (a[i] <= temp && i<j)//再找左边的 
                      i++;
               if (i<j)//交换两个数在数组中的位置 比基准大的,和比基准小的互换位置
               {
                      t = a[i];
                      a[i] = a[j];
                      a[j] = t;
               }
        }

        a[left] = a[i];
        a[i] = temp;

        Qsort(a, left, i - 1);//继续处理左边的,递归
        Qsort(a, i + 1, right);//继续处理右边的 ,递归
 }
 void quicksort(int data[], int n)///快排
 {
        Qsort(data, 1, n);
 }

 void selectsort(int data[], int n)//简单选择排序 
 {
        int a, b;
        for (b = 1; b < n; b++)
        {
               int min = b;
               for (a = b + 1; a < n; a++)//找最小值
               {
                      if (data[a]<data[min])
                      {
                             min = a;
                      }
               }
               if (b != min)
               {
                      int temp = data[b];
                      data[b] = data[min];
                      data[min] = temp;
               }
        }
 }
 void heapsort(int data[], int n)//堆排序 
 {
        for (int i = n / 2; i >= 0; i--)//建初堆
        {
               int t = data[i];
               int x = data[i];
               int m = i;
               int j = 2 * m;
               bool finished = false;
               while (j <= n&&!finished)
               {
                      if (j + 1 <= n&&data[j]<data[j + 1])
                      {
                             j = j + 1;
                      }
                      if (x >= data[j])
                      {
                             finished = true;
                      }
                      else{
                             data[m] = data[j];
                             m = j;
                             j = 2 * m;
                      }
               }
               data[m] = t;
        }
        for (int i = n - 1; i >= 1; i--)
        {
               int b = data[0];
               data[0] = data[i];
               data[i] = b;
               int t = data[0];//重建堆
               int x = data[0];
               int m = 0;
               int j = 2 * m;
               bool finished = false;
               while (j <= i - 1 && !finished)
               {
                      if (j + 1 <= i - 1 && data[j]<data[j + 1])
                      {
                             j = j + 1;
                      }
                      if (x >= data[j])
                      {
                             finished = true;
                      }
                      else{
                             data[m] = data[j];
                             m = j;
                             j = 2 * m;
                      }
               }
               data[m] = t;
        }
 }

 void Merge(int r1[], int low, int mid, int high, int r2[]){
        int i = low; int j = mid + 1; int k = low;
        while ((i <= mid) && (j <= high))
        {
               if (r1[i] <= r1[j]) { r2[k] = r1[i]; i++; }
               else { r2[k] = r1[j]; j++; }
               k++;
        }
        while (i <= mid)
        {
               r2[k] = r1[i];
               k++;
               i++;
        }
        while (j <= high)
        {
               r2[k] = r1[j];
               k++;
               j++;
        }
 }

 void Msort(int r1[], int low, int high, int r3[])//合并排序
 {
        int *r2;
        r2 = (int *)malloc((high + 1) * sizeof(int));
        if (low == high)
        {
               r3[low] = r1[low];
        }
        else
        {
               int mid = (low + high) / 2;
               Msort(r1, low, mid, r2);
               Msort(r1, mid + 1, high, r2);
               Merge(r2, low, mid, high, r3);
        }
        free(r2);
 }
 void mergesort(int data[], int n)//合并排序
 {
        Msort(data, 0, n - 1, data);/*把函数的实现代码粘贴在此处*/
 }

 int GetNumInPos(int num, int pos)
 {
        int temp = 1;
        for (int i = 0; i < pos - 1; i++)
               temp *= 10;

        return (num / temp) % 10;
 }
 void radixsort(int data[], int n)//基数排序
 {

        int *radixArrays[RADIX_10];    //分别为0~9的序列空间  
        for (int i = 0; i < 10; i++)
        {
               radixArrays[i] = (int *)malloc(sizeof(int)* (n + 1));
               radixArrays[i][0] = 0;    //index为0处记录这组数据的个数  
        }

        for (int pos = 1; pos <= KEYNUM_31; pos++)    //从个位开始到31位  
        {
               for (int i = 0; i < n; i++)    //分配过程  
               {
                      int num = GetNumInPos(data[i], pos);
                      int index = ++radixArrays[num][0];
                      radixArrays[num][index] = data[i];
               }

               for (int i = 0, j = 0; i < RADIX_10; i++)    //收集  
               {
                      for (int k = 1; k <= radixArrays[i][0]; k++)
                             data[j++] = radixArrays[i][k];
                      radixArrays[i][0] = 0;    //复位  
               }
        }
 }

【算法效率】:
编程实现各种排序算法,并对比各种算法的效率