Li_Chi 2023-03-20 23:10 采纳率: 100%
浏览 161
已结题

关于#C语言冒泡排序型#的问题,如何解决?

#C语言冒泡排序时间求救!
为什么最差的逆序在冒泡排序中的运行时间比随机数冒泡排序的运行时间还短?!

#include <stdio.h>
#include <time.h>
#define MAXN 30000
void swap1(int *px,int *py){
    int temp;
    temp=*px;
    *px=*py;
    *py=temp;
}
void bubble(int a[],int n){
    int i;
    int j;
    int flag=0; 
    for(i=1;i<n;i++){
        for(j=0;j<n-i;j++){
            if(a[j]>a[j+1]){
                swap1(&a[j],&a[j+1]);
            }
        }
    }
}

void swap2(int a[],int n){
    int half;
    half=n/2;
    int i;
    for(i=0;i<half;i++){
        swap1(&a[i],&a[n-i-1]);
    }
}
int main()
{
    int a[MAXN];
    int i;
    srand((unsigned)time(NULL));    //给随机数种子 
    for(i=0;i<MAXN;i++){
        a[i]=rand();
    }
    clock_t start_time=clock();    
    //clock_t 是 一种数据类型,通常用于表示程序运行的时间。    它是由 time.h 库中的 clock() 函数返回的 CPU 时钟周期数的数据类型。
    bubble(a,MAXN);
    clock_t end_time = clock();
    for(i=0;i<20;i++){
        printf("%3d ",a[i]);
    }
    double elapsed_time = (double) (end_time - start_time) / CLOCKS_PER_SEC;
    printf("\nRandom Bubble Running Time:为 %.3f 秒。\n", elapsed_time);
    swap2(a,MAXN);
    for(i=0;i<20;i++){
        printf("%3d ",a[i]);
    }
    start_time = clock();
    bubble(a,MAXN);
    end_time = clock();
    elapsed_time = (double) (end_time - start_time) / CLOCKS_PER_SEC;
    printf("\nWorst Bubble Running Time:为 %.3f 秒。\n", elapsed_time);
    }

img

  • 写回答

9条回答 默认 最新

  • ksgpjhqf 2023-03-21 01:31
    关注

    冒泡排序逆序速度快于乱序的原因是CPU的流水线和分支预测技术。参考这篇文章:冒泡排序乱序速度慢于逆序探究
    我自己也测试了一下,与编译器优化有关,在release选项下,无论是先乱序还是先逆序,无论数组开多大,无论数组有没有重复值,平均下来逆序总是比乱序时间短。而在debug选项下,逆序比乱序时间长。下面是我测试的代码,在你的代码的基础上做了一些改动。

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define MAXN 100000
    #define swap(a,b) (a^=b,b^=a,a^=b)
    
    void bubble(int a[], int n) {
        int i, j;
        int flag = 0;
        for (i = n - 1; i > 0; i--) {
            flag = 0;
            for (j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a[j], a[j + 1]);
                    flag = 1;
                }
            }
            if (flag == 0)break;
        }
    }
    
    double bubbletime(int a[], int n) {
        static int starttime, endtime;
        starttime = clock();
        bubble(a, n);
        endtime = clock();
        return (double)(endtime - starttime) / CLOCKS_PER_SEC;
    }
    
    int main() {
        int a[MAXN], b[MAXN];
        int i, j;
        srand(time(NULL));    //给随机数种子
        for (i = 0; i < MAXN; i++) {
            a[i] = i;
        }
        //随机打乱
        for (i = 0; i < MAXN; i++) {
            j = i + rand() % (MAXN - i);
            swap(a[i], a[j]);
            b[i] = a[i];
        }
        printf("\nRandom Bubble Running Time:为 %.3f 秒。\n", bubbletime(a, MAXN));
        for (i = 0; i < MAXN; i++)a[i] = MAXN - i - 1;
        printf("\nWorst Bubble Running Time:为 %.3f 秒。\n", bubbletime(a, MAXN));
        printf("\nRandom Bubble Running Time:为 %.3f 秒。\n", bubbletime(b, MAXN));
        return 0;
    }
    

    release选项的执行结果

    img


    debug选项的执行结果

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(8条)

报告相同问题?

问题事件

  • 系统已结题 3月30日
  • 已采纳回答 3月22日
  • 赞助了问题酬金15元 3月20日
  • 创建了问题 3月20日

悬赏问题

  • ¥15 关于#51单片机#的问题:运算放大电路
  • ¥15 电路原理(关键词-工作原理)
  • ¥15 yolov5s模型下载就卡住,没有运行结果
  • ¥15 请问代码技术们,云梦建站的这个坑你们踩过吗?
  • ¥20 androidstudio工具问题
  • ¥15 想问一些关于计量的问题
  • ¥15 关于c++外部库文件宏的问题,求解
  • ¥15 office打开卡退(新电脑重装office系统后)
  • ¥300 FLUENT 火箭发动机燃烧EDC仿真
  • ¥15 【Hadoop 问题】Hadoop编译所遇问题hadoop-common: make failed with error code 2