嘿，你的标准冒泡排序确实有不少可以优化的地方——每次都从头到尾遍历整个数组完全没必要，毕竟每一轮冒泡都会把当前最大的元素“推”到数组末尾，这些已经排好的元素根本不用再碰。咱们来一步步改，直接把比较次数砍半：

核心优化思路 #

• 缩小内层循环范围：每完成一轮排序，数组末尾的i个元素已经是有序的最大值，所以下一轮只需要比较到roz - i的位置。这一步直接就能把总比较次数减少约一半。
• 提前终止机制：加个交换标志位，如果某一轮遍历下来没发生任何交换，说明数组已经完全有序了，直接跳出循环就行，避免做无用功。

修改后的完整代码 #

void optimized_bubble_sort(int* tab, int roz) {
    int test;
    int swapped; // 标记本轮是否发生交换
    for (int i = 0; i < roz; i++) {
        swapped = 0; // 每轮开始前重置交换状态
        // 内层循环只遍历未排序的部分：到 roz - i 就停
        for (int j = 1; j < roz - i; j++) {
            if (tab[j - 1] > tab[j]) {
                // 交换相邻元素
                test = tab[j - 1];
                tab[j - 1] = tab[j];
                tab[j] = test;
                swapped = 1; // 标记发生了交换
            }
        }
        // 本轮没交换=数组已完全有序，直接结束排序
        if (!swapped) {
            break;
        }
    }
}

为啥能减少一半比较次数？ #

你看你的标准实现里，外层循环跑roz次，每次内层都做roz-1次比较，总次数是roz*(roz-1)。而优化后的版本，内层循环的次数每轮都会减少：第一次roz-1次，第二次roz-2次，直到最后一轮只做1次比较，总次数是(roz-1)+(roz-2)+...+1 = roz*(roz-1)/2——刚好是原来的一半，完美达到你的需求！

内容的提问来源于stack exchange，提问作者JimPanse