冒泡排序最大次数？

Question

我正在尝试创建一个使用冒泡排序对 100 个随机数进行排序的函数。但是，我想我可能做错了什么。让我先向您展示我的代码：

#define MAXVALUE 100

void sortera_nummer(int slumptal[]){
int i,j,temp,k=0;


for(i=0;i<MAXVALUE;i++){
    for(j=MAXVALUE-1;j>i;j--){
        if(slumptal[j-1]>slumptal[j]){
            temp=slumptal[j-1];
            slumptal[j-1]=slumptal[j];
            slumptal[j]=temp;
            k++;
        }
    }
}
printf("K = %d",k);
}

所有数字都是从低到高排序的，所以排序有效。但是我得到 K = 一个出乎意料的高数字。（它一直在 2300 到 2700 之间。）

所以现在我想知道 - 对于 100 个元素，正常工作的冒泡排序最多可以运行多少次？它的计算公式是什么？

(第一次post来这里，如有错误请见谅。) 提前致谢。

Answer 1

最坏的情况是输入数组按降序排序。第一个循环执行 99 次，接下来的 98 次，接下来的 97 次......等于 "sum(n) from n=99 to n=1" ，这意味着最坏的情况是 n(n+1)/2，在你的情况下 n=99那是 4950.

冒泡排序最大次数？

Bubble sorting max number of times?

math

bubble-sort