冒泡排序算法的C++实现

直接上代码：

#include <iostream>
using namespace std;

void BubbleSort(int arr[],int n){

    while(n-->0)    //在本例中，第1次执行while时，n的值为9，即（n-1）
    for(int i=0;i<n;i++){
        //如果当前元素比后面相邻的元素大，则交换相邻元素数值
        if(arr[i]>arr[i+1])
            swap(arr[i],arr[i+1]);

    }
}

int main(){

    int a[10]={10,9,8,7,6,5,4,3,2,1};
    BubbleSort(a,10);
    for(int i=0;i<10;i++){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

考虑一下，如果冒泡法在执行期间，执行到某个元素（不是最后一个元素），此时如果序列已经有序，那么算法会停下来吗？答案当然是否定的，只有遍历完整个待排序序列算法才会停下来。那么后面剩余元素的遍历就成了徒劳的浪费时间，因此，我们可以为我们的算法立个flag来标记一下，以确定它不会执行多余操作。

那么冒泡排序算法结束的条件就是：在一趟排序过程中没有发生元素的交换。

所以我们可以对关键代码做以下优化

---

 

void BubbleSort(int arr[],int n){

    int flag;    //标记
    while((n--)>0){
        flag=0;        //标记初始值为0
    for(int i=0;i<n;i++){
        if(arr[i]>arr[i+1]){
          swap(arr[i],arr[i+1]);
          flag=1;        //如果发生交换，标记就重置为1
        }
    }
    if(flag==0)        //如果标记还是初始值，那么证明这一趟没有发生数值交换，即完成排序
        return;
}
}

对于冒泡排序，一趟排序后能确保一个关键字到达其最终位置。