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

Question

#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);
    }

Answer 1

冒泡排序逆序速度快于乱序的原因是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选项的执行结果

debug选项的执行结果