算法 | 编程实现各种排序算法，并对比各种算法的效率

【设计要求】:
在给出的代码素材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);//合并排序 
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之间的随机整数，并写入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;    //复位  
        }
    }
}

【算法效率】: