冒泡排序法及其优化_std::list 冒泡算法如何提高速度-CSDN博客

本文链接：https://blog.csdn.net/pbzhang_csdn/article/details/94389413

本文介绍冒泡排序法及其四种优化版本的C/C++实现，包括基本冒泡排序、提前结束循环、减少无用比较和双向冒泡排序。通过对比不同长度数组的排序效果，展示优化策略的有效性。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

冒泡排序法及其优化， C/C++ 版. 如有错误，欢迎指正。
注：本人非计算机专业，纯属业余，欢迎拍砖。呵呵。

直接上代码：

#include <iostream>
#include <utility>
#include <ctime>
#include <cstdlib>

using std::cout;
using std::endl;

//冒泡排序函数
std::pair<int, int> bubbleSort(int[], const int);
std::pair<int, int> bubbleSort2(int[], const int);
std::pair<int, int> bubbleSort3(int[], const int);
std::pair<int, int> bubbleSort4(int[], const int);

//生成随机数函数
int getRandom();

int main(int argc, char *argv[])
{     
const unsigned int LEN = 10;
int arr[LEN], arr2[LEN], arr3[LEN], arr4[LEN];
for(int i = 0; i < LEN; ++i){
    arr[i] = getRandom();
    arr2[i] = arr3[i] = arr4[i] = arr[i];
   
    //等待随机数更新
    for(long j = 0; j < 100000000; ++j){
        j * j;
    }
}
unsigned int len = sizeof(arr)/sizeof(arr[0]);
std::pair<int, int> cnts_pair;

cnts_pair = bubbleSort(arr, len);
cout <<"bubbleSort compare times: " << cnts_pair.first << ",swap times:"
     << cnts_pair.second << endl;
for(auto const &elem : arr){
    cout << elem << " ";
}
cout << endl;

cnts_pair = bubbleSort2(arr2, len);
cout <<"bubbleSort2 compare times: " << cnts_pair.first << ",swap times:"
     << cnts_pair.second << endl;
for(auto const &elem : arr2){
    cout << elem << " ";
}
cout << endl;

cnts_pair = bubbleSort3(arr3, len);
cout <<"bubbleSort3 compare times: " << cnts_pair.first << ",swap times:"
     << cnts_pair.second << endl;
for(auto const &elem : arr3){
    cout << elem << " ";
}
cout << endl;

cnts_pair = bubbleSort4(arr4, len);
cout <<"bubbleSort4 compare times: " << cnts_pair.first << ",swap times:"
     << cnts_pair.second << endl;
for(auto const &elem : arr4){
    cout << elem << " ";
}
cout << endl;

return 0;
}

//一般写法
std::pair<int, int> bubbleSort(int a[], const int len){
int i, j, tmp;
int cnts1 = 0; //记录比较次数
int cnts2 = 0; //交换
for(i = 0; i < len - 1; ++i){
    for(j = 0; j < len - 1 - i; ++j){
        ++cnts1;
        if(a[j] > a[j+1]){
            tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
            ++cnts2;
        }
    }
}
return std::pair<int, int>(cnts1, cnts2);
}

//优化一：如果某一趟排序没任何交换，则序列已经全部有序,此时就可以中断循环，不用再比较
std::pair<int, int> bubbleSort2(int a[], const int len){
int i, j, tmp;
bool flag = true; //子列有序标志
int cnts1 = 0; //记录比较次数
int cnts2 = 0; //交换
for(i = 0; i < len - 1; ++i){
    flag = true;
    for(j = 0; j < len - 1 - i; ++j){
        ++cnts1;
        if(a[j] > a[j+1]){
            tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
            flag = false;
            ++cnts2;
        }

    }
    // 如果上一次循环没有发生交换，则说明序列已经全部有序，退出循环
    if(flag){
        break;
    }
}
return std::pair<int, int>(cnts1, cnts2);
}

//优化二：每次循环，发生交换的最后位置的后面的序列实际已经有序,不必再比较
std::pair<int, int> bubbleSort3(int a[], const int len){
int i, j, tmp;
int boderRight, posn;
bool flag = true;
int cnts1 = 0; //记录比较次数
int cnts2 = 0; //交换
posn = 0; //记录交换位置
boderRight = len -1;

for(i = 0; i < len - 1; ++i){
    flag = true;
    for(j = 0; j < boderRight; ++j){
        ++cnts1;
        if(a[j] > a[j+1]){
            tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
            flag = false;
            posn = j; //本次交换最后位置
            ++cnts2;
        }
    }
    // 如果上一次扫描没有发生交换，则说明数组已经全部有序，退出循环
    if(flag){
        break;
    }
    boderRight = posn;
}
return std::pair<int, int>(cnts1, cnts2);
}

//优化三：上面的循环中，每次对整个数据循环我们都只找出了最大值，并且放到了最后的位置
//如果每次循环既寻找最大值又最小值，并把最大值放到最后，最小值放到最前的位置，就可以进一步优化了
std::pair<int, int> bubbleSort4(int a[], const int len){
int cnts1 = 0; //记录比较次数
int cnts2 = 0; //交换
int bordenRight = len -1; //右边界初始值
int bordenLeft = 0;//左边界初始值
int lastPosn = 0;//记录右边界的值
int prePosn = 0;//记录左边界的值
bool flag = true;
for(int i = 0; i < len - 1; ++i) {
    flag = true;
    //正向找出最大值,放在后面
    for(int j = bordenLeft; j < bordenRight; ++j) {
        ++cnts1;
        if(a[j] > a[j+1]){
            auto tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
            flag = false;
            lastPosn = j;
            ++cnts2;
        }
    }
    //逆向找出最小值，放在前面
    for(int j = bordenRight; j > bordenLeft; --j) {
        ++cnts1;
        if(a[j-1] > a[j]) {
            auto tmp = a[j-1];
            a[j-1] = a[j];
            a[j] = tmp;
            flag = false;
            prePosn = j;
            ++cnts2;
        }
    }
    if(flag) {
        break;
    }
    bordenRight = lastPosn;
    bordenLeft = prePosn;
}

return std::pair<int, int>(cnts1, cnts2);
}

int getRandom(){
std::srand((unsigned)std::time(0));
return std::rand()%6; //产生[0-6)的随机数
}

测试结果：
当LEN= 10
bubbleSort compare times: 45,swap times:16
2 2 2 2 5 5 5 5 5 5
bubbleSort2 compare times: 35,swap times:16
2 2 2 2 5 5 5 5 5 5
bubbleSort3 compare times: 27,swap times:16
2 2 2 2 5 5 5 5 5 5
bubbleSort4 compare times: 36,swap times:16
2 2 2 2 5 5 5 5 5 5
当LEN=100
bubbleSort compare times: 4950,swap times:2129
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
bubbleSort2 compare times: 4830,swap times:2129
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
bubbleSort3 compare times: 4642,swap times:2129
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
bubbleSort4 compare times: 3308,swap times:2129
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5