qq_39677327 2022-06-09 13:50 采纳率: 94.9%
浏览 260
已结题

数据结构排序算法程序求解惑

A数组中存储500个2000以内的随机整数,完成以下操作:
(1)对A数组中的元素进行直接插入排序,显示排序所用时间;
(2)对A数组中的元素进行希尔排序,显示排序所用时间;
(3)对A数组中的元素进行起泡排序,显示排序所用时间;
(4)对A数组中的元素进行快速排序,显示排序所用时间。

  • 写回答

3条回答 默认 最新

  • 关注

    500个数据基本出来的都是0秒。
    下面是5000个数据出来的结果:

    img

    代码:

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAXLEN 5000
    
    //生成随机数组
    void createSjArray(int a[])
    {
        for (int i = 0; i < MAXLEN; i++)
            a[i] = rand() % 2000;
    }
    
    
    //冒泡排序
    void Bubblesort(int* num, int n)
    {
        int i, j, t;
        for (i = 0; i < n - 1; i++)
        {
            for (j = 0; j < n - 1 - i; j++)
            {
                if (num[j] > num[j + 1])  //从小到大,升序
                {
                    t = num[j];
                    num[j] = num[j + 1];
                    num[j + 1] = t;
                }
            }
        }
    }
    
    //选择排序,升序
    void SelectSort(int* num, int n)
    {
        int i, j;
        int minindex, tmp;
        for (i = 0; i < n - 1; i++)
        {
            minindex = i;
            //找出第i小的数所在的位置
            for (j = i + 1; j < n; j++)
            {
                if (num[j] < num[minindex])
                    minindex = j;
            }
    
            //将第i小的数放在第i个位置
            if (i != minindex)
            {
                tmp = num[i];
                num[i] = num[minindex];
                num[minindex] = tmp;
            }
        }
    
    }
    
    //插入排序
    void InsertSort(int* nums, int numsSize)
    {
        int i, j, temp;
        for (i = 1; i < numsSize; i++)
        {
            {
                if (nums[i] < nums[i - 1])
                {
                    temp = nums[i];
                    for (j = i - 1; j >= 0; j--)
                    {
                        if (nums[j] > temp)
                            nums[j + 1] = nums[j];
                        else
                            break;
                    }
                    nums[j + 1] = temp;
                }
            }
        }
    }
    
    //希尔排序
    void shellSort(int* a, int len)
    {
        int i, j, k, tmp, gap;  // gap 为步长
        for (gap = len / 2; gap > 0; gap /= 2) {  // 步长初始化为数组长度的一半,每次遍历后步长减半,
            for (i = 0; i < gap; ++i) { // 变量 i 为每次分组的第一个元素下标 
                for (j = i + gap; j < len; j += gap) { //对步长为gap的元素进行直插排序,当gap为1时,就是直插排序
                    tmp = a[j];  // 备份a[j]的值
                    k = j - gap;  // j初始化为i的前一个元素(与i相差gap长度)
                    while (k >= 0 && a[k] > tmp) {
                        a[k + gap] = a[k]; // 将在a[i]前且比tmp的值大的元素向后移动一位
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }
    }
    
    
    //显示数组
    void showArray(int* num, int n)
    {
        for (int i = 0; i < n; i++)
        {
            if ((i + 1) % 10 == 0)
                printf("%d\n", num[i]);
            else
                printf("%d ", num[i]);
        }
        printf("\n");
    }
    
    //快速排序
    void QuickSort(int  nums[], int L, int R) {
        int i, j = L, temp, k = nums[R];
        if (L < R) {
            for (i = L; i < R; i++) {
                if (nums[i] < k) {
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                    j++;
                }
            }
            temp = nums[R];
            nums[R] = nums[j];
            nums[j] = temp;
            QuickSort(nums, L, j - 1);
            QuickSort(nums, j + 1, R);
        }
        return;
    }
    
    //归并排序
    void merge(int* nums, int L, int M, int R) {
        int LEFT_SIZE = M - L;
        int RIGHT_SIZE = R - M + 1;
        int* left = (int*)malloc(LEFT_SIZE * sizeof(int));
        int* right = (int*)malloc(RIGHT_SIZE * sizeof(int));
        int i, j, k;
        for (i = L; i < M; i++) left[i - L] = nums[i];
        for (i = M; i <= R; i++) right[i - M] = nums[i];
        i = 0, j = 0, k = L;
        while (i < LEFT_SIZE && j < RIGHT_SIZE) {
            if (left[i] < right[j]) {
                nums[k] = left[i];
                i++;
                k++;
            }
            else {
                nums[k] = right[j];
                j++;
                k++;
            }
        }
        while (i < LEFT_SIZE) {
            nums[k] = left[i];
            k++;
            i++;
        }
        while (j < RIGHT_SIZE) {
            nums[k] = right[j];
            k++;
            j++;
        }
    }
    void mergesort(int* nums, int L, int R) {
        //L为数组的开始下表,R为数组的结束下标,以[1,2,3,4]为例,L=0,R=3
        if (L == R)return;
        else {
            int M = (R + L) / 2;
            mergesort(nums, L, M);
            mergesort(nums, M + 1, R);
            merge(nums, L, M + 1, R);
        }
    }
    
    //堆排序 // 从小到大排序
    void swap(int array[], int x, int y) {
        int key = array[x];
        array[x] = array[y];
        array[y] = key;
    }
    
    void Down(int array[], int i, int n) { // 最后结果就是大顶堆
        int parent = i;                    // 父节点下标
        int child = 2 * i + 1;            // 子节点下标
        while (child < n) {
            if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大,大的与父节点比较
                child++;
            }
            if (array[parent] < array[child]) { // 判断父节点是否小于子节点
                swap(array, parent, child);     // 交换父节点和子节点
                parent = child;                 // 子节点下标 赋给 父节点下标
            }
            child = child * 2 + 1; // 换行,比较下面的父节点和子节点
        }
    }
    
    void BuildHeap(int array[], int size) {
        for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆,必须从下往上比较
            Down(array, i, size);                 // 否则有的不符合大顶堆定义
        }
    }
    
    void HeapSort(int array[], int size) {
        BuildHeap(array, size); // 初始化堆
    
        for (int i = size - 1; i > 0; i--) {
            swap(array, 0, i); // 交换顶点和第 i 个数据
            // 因为只有array[0]改变,其它都符合大顶堆的定义,所以可以从上往下重新建立
            Down(array, 0, i); // 重新建立大顶堆        
        }
    }
    
    
    //重置数组
    void ResetArray(int dst[], int src[])
    {
        for (int i = 0; i < MAXLEN; i++)
            dst[i] = src[i];
    }
    
    
    
    
    int main()
    {
        int a[MAXLEN], b[MAXLEN];
        double tms[7] = { 0 }; //记录三种情况下,每种算法的时间
        clock_t start, stop;
        int i = 0, j;
    
        const char* alth[] = { "选择排序","冒泡排序","插入排序","希尔排序","快速排序","归并排序","堆排序" };
    
        srand((unsigned int)time(0)); //生成随机数种子
    
    
        createSjArray(a);
    
        //showArray(a, MAXLEN);
    
        //统计每种算法的排序时间
        ResetArray(b, a); //用b备份a
        start = clock();
        SelectSort(a, MAXLEN); //调用选择排序算法
        stop = clock();
        tms[0] = (double)(stop - start)/ CLOCKS_PER_SEC;
    
        ResetArray(a, b); //还原a
        start = clock();
        Bubblesort(a, MAXLEN); //调用冒泡排序算法
        stop = clock();
        tms[1] = (double)(stop - start) / CLOCKS_PER_SEC;
    
        ResetArray(a, b); //还原a
        start = clock();
        InsertSort(a, MAXLEN); //调用插入排序算法
        stop = clock();
        tms[2] = (double)(stop - start) / CLOCKS_PER_SEC;
    
        ResetArray(a, b); //还原a
        start = clock();
        shellSort(a, MAXLEN); //调用希尔排序算法
        stop = clock();
        tms[3] = (double)(stop - start) / CLOCKS_PER_SEC;
    
        ResetArray(a, b); //还原a
        start = clock();
        QuickSort(a, 0, MAXLEN - 1); //调用快速排序算法
        stop = clock();
        tms[4] = (double)(stop - start) / CLOCKS_PER_SEC;
    
        ResetArray(a, b); //还原a
        start = clock();
        mergesort(a, 0, MAXLEN - 1); //调用归并排序算法
        stop = clock();
        tms[5] = (double)(stop - start) / CLOCKS_PER_SEC;
    
        ResetArray(a, b); //还原a
        start = clock();
        HeapSort(a, MAXLEN); //调用堆排序算法
        stop = clock();
        tms[6] = (double)(stop - start) / CLOCKS_PER_SEC;
    
    
    
        printf("耗时统计:\n\n");
    
        for (i = 0; i < 7; i++)
        {
            if (i < 6)
                printf("%8s   ", alth[i]);
            else
                printf("%8s\n", alth[i]);
        }
    
        for (j = 0; j < 7; j++)
        {
            if (j < 6)
                printf("%-8.4lf   ", tms[j]);
            else
                printf("%-8.4lf\n", tms[j]);
        }
    
    
        system("pause");
        return 0;
    }
    
    
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 6月10日
  • 已采纳回答 6月10日
  • 创建了问题 6月9日

悬赏问题

  • ¥15 TLS1.2协议通信解密
  • ¥40 图书信息管理系统程序编写
  • ¥15 7-1 jmu-java-m02-使用二维数组存储多元线性方程组
  • ¥20 Qcustomplot缩小曲线形状问题
  • ¥15 企业资源规划ERP沙盘模拟
  • ¥15 树莓派控制机械臂传输命令报错,显示摄像头不存在
  • ¥15 前端echarts坐标轴问题
  • ¥15 ad5933的I2C
  • ¥15 请问RTX4060的笔记本电脑可以训练yolov5模型吗?
  • ¥15 数学建模求思路及代码