如何在冒泡排序无交换时退出循环？C++代码优化问询

这个优化点能显著提升冒泡排序的效率，尤其是当数组接近有序的时候。核心思路就是用一个标志位跟踪每轮内层循环是否发生了元素交换——如果某一轮完全没交换，说明数组已经是有序状态了，直接跳出外层循环就行。

具体实现步骤 #

• 在外层循环初始化一个交换标志位，默认设为false
• 每次内层循环里发生元素交换时，把标志位改成true
• 每轮内层循环结束后，检查标志位：如果还是false，立即终止外层循环
• 额外小优化：每轮外层循环后，末尾的i个元素已经是有序的，所以内层循环的上限可以改为size-1-i，减少不必要的比较次数

修改后的完整代码 #

#include<iostream>
using namespace std;
int main() {
    const int size=4;
    int arr[size];
    int i,j,temp;
    for(i=0;i<size;i++) {
        cout<<"arr["<<i<<"]: ";
        cin>>arr[i];
    }
    // 优化后的外层循环
    for(i=0;i<size;i++) {
        bool swapped = false; // 初始化交换标志位
        // 内层循环优化：只比较到size-1-i的位置
        for(j=0;j<size-1-i;j++) {
            if(arr[j]>arr[j+1]) {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                swapped = true; // 发生交换，标志位置为true
            }
        }
        // 如果这一轮没有任何交换，说明数组已经有序，直接退出循环
        if(!swapped) {
            break;
        }
    }
    for(i=0;i<size;i++) {
        cout<<"arr["<<i<<"]: "<<arr[i]<<endl;
    }
    return 0;
}

关键代码解释 #

• bool swapped = false;：每轮排序前重置标志位，用来记录本轮是否有元素交换
• j < size-1-i：冒泡排序每轮都会把当前最大的元素“冒”到末尾，所以后面的i个元素已经是有序的，不需要再比较
• swapped = true;：每次交换元素时更新标志位，告诉程序本轮有排序操作
• if(!swapped) break;：如果本轮没有交换，说明数组已经完全有序，不需要继续循环，直接退出

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