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

时间:2022-12-29 19:52:29

直接上代码:

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

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