新的家园

原理：n个元素的数组：第一轮从头开始两两比较，如果前一个大于（或小于）后一个，则交换，然后比较下一个，直到最大的数（或最小的数）移到末尾。第二轮重复第一轮操作，比较的数目为比上轮少1（因为已经定位到1个最大值）；继续比较直到比较的数据为0； 冒泡排序实现：

void bubble_sort(int array[], int length) {

for (int i = 1; i<length; ++i) {
    for (int j = 0; j < length -i; ++j) {
        if (array\[j\] > array\[j + 1\]) {
            int const temp = array\[j\];
            array\[j\] = array\[j + 1\];
            array\[j + 1\] = temp;
        }
    }
}

cout << "冒泡排序：" << endl;
for (int i = 0; i<length; i++) {
    cout << array\[i\] << endl;
}

}

优化：因为在经过m（0<m<n）轮比较后，如果在新的一轮比较中无任何交换，说明数组已经是排好序的了，即可终止循环。

void bubble_sort_2(int array[], int length) {

//标记是否交换
int isSwap; 
for (int i = 1; i<length; ++i) {
    isSwap = 0;

    for (int j = 0; j < length -i; ++j) {
        if (array\[j\] > array\[j + 1\]) {
            int const temp = array\[j\];
            array\[j\] = array\[j + 1\];
            array\[j + 1\] = temp;

            isSwap = 1;
        }
    }

    if (isSwap == 0) break;

}

cout << "冒泡排序2：" << endl;
for (int i = 0; i<length; i++) {
    cout << array\[i\] << endl;
}

}

冒泡排序的时间复杂度为 o(n^2)

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 xue_huashan@163.com