冒泡排序(bubble sort)

适用组别：入门组
难度系数：3

算法描述
步骤一、从第一个元素开始，比较相邻的元素。如果第一个比第二个大，就交换它们两个；
步骤二、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
步骤三、针对所有的元素重复以上的步骤一、二，除了最后一个；（一趟下来，最大的那个数就排在了最后面，那么下一趟对前n-1个数做同样的操作）

注：冒泡排序的交换次数(swap)就是数组中逆序对的个数。

代码实现一：

/****************************************************************
 * bubble sort by C++ version
 * author : ALex Li
 * date : 2023-5
 * verston: 1.5
****************************************************************/

#include <iostream>
using namespace std;
int main() {
    int a[1000] = {0};
    int i = 0,n;
    cin>>n; 
    do {
        cin >> a[i];
        i++;
        } while (i <n);
        
        for (int k = 0; k <n-1 ; ++k) {
            for (int j = 0; j <n-1-k; ++j) {
                if(a[j]>a[j+1]){
                   swap(a[j],a[j+1]);
                }
            }
        }
        
    for (int i = 0; i < n; i++) {
        cout<<a[i]<<' ';
    }
return 0;    
}

代码实现二：

/**************************************************************** 
 * Description: bubble sort by C++
 * Author: Alex Li
 * Date: 2023-06-17 23:11:39
 * LastEditTime: 2023-06-17 23:22:19
****************************************************************/


#include <iostream>
using namespace std;
 int a[1000];
int main() {
    bool swapped;
    int i = 0,n;
    cin>>n; 
    do {
        cin >> a[i];
        i++;
        } while (i <n);
        
        for (int k = 0; k <n-1 ; ++k) {
            swapped=false;
            for (int j = 0; j <n-1-k; ++j) {
                if(a[j]>a[j+1]){
                   swap(a[j],a[j+1]);
                   swapped=true;
                }
            }
            if(swapped==false)break;
            //如果没有发生过交换，中断循环，说明数组已经是有序数组
            //if no two elements were swapped,  then break.
        }
        
    for (int i = 0; i < n; i++) {
        cout<<a[i]<<' ';
    }
return 0;    
}

方法三：(优化pro)

/**************************************************************** 
 * Description: bubble sort pro by C++
 * Author: Alex Li
 * Date: 2023-06-17 23:11:39
 * LastEditTime: 2023-06-19 17:47:17
****************************************************************/


#include <iostream>
#include <cmath>
using namespace std;
 int a[1000];
int main() {
    int j= 0,n,k,flag;
    cin>>n; 
    do {
        cin >> a[j];
        j++;
        } while (j <n);
    flag=n;
    /*用flag标识最后一次交换的位置，下次循环的时候，只需要循环到flag的位置，
    因为在最后一次交换后面的元素都是已经排好序列的。*/
    while(flag>1){
        k=flag;
        flag=1;
       for (int i = 0; i <k-1; i++){
        if(a[i]>a[i+1]){
            swap(a[i],a[i+1]);
             flag=i+1;
           }
       
       }
    }    
    for (int i = 0; i <n; i++){
        cout<<a[i];
    }
    
return 0;    
}

Quizzes

小测验-冒泡排序

Previous Topic

Back to Lesson

Next Quiz

数据结构与算法

冒泡排序(bubble sort)