冒泡排序(C++)算法详解

冒泡排序是按升序或降序排列数据的简单方法。按升序对数据进行排序意味着按照从低到高的顺序排列数据；而按降序排序则意味着按从高到低的顺序排列。可以通过比较数组中的每个元素和它的相邻值来进行冒泡排序，如果它们不是所需的顺序，则让它们交换位置。

现在来看一看它是如何按升序排列下面的数组元素的：

冒泡排序是通过比较数组中的前两个元素开始的。如果 Element 0 大于 Element 1，则交换它们。交换后，数组显示如下：

这个过程重复应用于 Element 1 和 Element 2。如果 Element 1 大于 Element 2，则它们被交换。所以该数组现在显示如下：

接下来，比较 Element 2 和 Element 3。但是，在这个数组中，这两个元素已经按照正 确的顺序排列（Element2 小于 Element3)，所以不发生交换。

随着循环的继续，Element 3 和 Element 4 进行比较。这次又出现了两个元素已经在正确顺序位置的情况，所以没有必要交换。但是，当比较 Element 4 和 Element 5 时，必须进行交换，因为 Element 4 大于 Element 5。所以数组现在的显示如下：

此时，整个数组已被扫描，这就是所谓的第一趟。请注意，现在最大的值正确放置在最后一个数组元素中。但是，数组的其余部分尚未排序。所以排序重新开始 Element 0 和 Element 1。因为它们在正确的顺序，没有进行交换。接下来 Element 1 和 Element 2 进行比较，但是再一次没有发生交换。这继续下去，直到 Element 3 和 4 进行比较。因为 Element 3 大于 Element 4，所以它们被交换。该数组现在显示如下：

可以发现，数组元素经过第二趟排序之后，已经将第二大的数字放在最后一个数组元素的旁边。这个过程将继续进行，重复地对该数组排序，并且在每个过程中至少交换一个数字，直到数组被完全排序。最终，数组将显示如下：

以下是冒泡排序的伪代码。注意它使用了一对嵌套循环。外循环是一个 do-while 循环，每次排序一趟就迭代一次。内循环（for 循环）包含了在一趟排序期间执行的所有比较和交 换所需的代码。

Do
    Set madeAswap flag to false
    For count = 0 to the next-to-last array, subscript
        If array[count] is greater than array[count + 1]
            Swap the contents of array[count] and array[count + 1]
            Set madeAswap flag to true
        End If
    End For
While the madeAswap flag is true

可以看到，do-while 循环中的第一个语句设置了一个名为 madeAswap 的标记变量，并将其值设置为 false。这是因为在刚开始的时候，尚未进行过交换。当在一趟排序过程中发现了不符合顺序的元素时，内循环即交换两个值的位置，并将 madeAswap 设置为 true。

do-while 循环底部的测试条件将检查 madeAswap 是否为 true。如果为 true，则继续进行循环迭代。但是，如果它检查并发现 madeAswap 仍然是 false，那么它就知道直到这一趟结束都未进行过交换，这意味着该数组现在已经完全排序，无须进行更多的遍历，于是循环退出。

以下 C++ 代码实现了冒泡排序功能。形参 array 引用一个需要进行排序的整数数组。形参 size 包含的是 array 中元素的数量。

void sortArray(int array[], int size)
{
    int temp;
    bool madeAswap;
    do
    {
        madeAswap = false;
        for (int count = 0; count < (size 一 1); count++)
        {
            if (array[count] > array[count + 1])
            {
                temp = array[count];
                array[count] = array[count + 1];
                array[count +1] = temp;
                madeAswap = true;
            }
        }
    } while (madeAswap) ;    //如果出现交换则再次循环
}

现在来仔细看一看在一趟排序过程中处理比较和交换的 for 循环。以下是它的起始行：

for (int count = 0; count < (size – 1); count++)

变量 count 保存数组下标。它从零开始，只要小于 size-1 就递增。size 的值是数组中元素的数量，只要 count 值满足条件（count < (size -1))，以下语句就会将每个元素与跟在它后面的一个元素进行比较：

if (array[count] > array[count + 1])

当 array[count] 是倒数第二个元素时，它将与最后一个元素进行比较。在比较完成之后，count 递增 1，测试条件（count < (size-1)）不成立，于是循环退出，这样就有效地避免了数组中最后一个元素与数组之外的值进行比较的情况。

以下是 if 语句的全部内容：

if (array[count] > array[count + 1])
{
    temp = array[count];
    array[count] = array[count + 1];
    array[count +1] = temp;
    madeAswap = true;
}

如果 array[count] 大于 array[count + 1]，则必须交换这两个元素。首先，将 array[count] 的内容复制到变量 temp 中，然后将 array[count + 1] 的内容复制到 array[count] 中。当 temp（保存了 array[count] 的前一个内容）复制到 array [count +1] 时，交换完成。最后，madeAswap 标记变量被设置为 true，这表明交换已经完成。

下面的程序演示了一个完整程序中的冒泡排序函数：

// This program uses the bubble sort algorithm to sort an array of integers in ascending order.
#include <iostream>
using namespace std;

// Function prototypes
void sortArray(int [], int);
void showArray(const int [], int);

int main()
{
    const int SIZE = 6;
    // Array of unsorted values
    int values[SIZE] = {7, 2, 3, 8, 9, 1};
    // Display the values
    cout <<"The unsorted values are :/n";
    showArray(values, SIZE);
    // Sort the values sortArray(values, SIZE);
    // Display them again
    cout << "The sorted values are: /n";
    showArray(values, SIZE);
    return 0;
}

void sortArray(int array[], int size)
{
    int temp;
    bool swap;
    do
    {
        swap = false;
        for (int count = 0; count < (size - 1); count++)
        {
            if (array[count] > array[count + 1])
            {
                temp = array[count];
                array[count] = array[count + 1];
                array[count +1] = temp;
                swap = true;
            }
        }
    } while (swap); // Loop again if a swap occurred on this pass.
}

void showArray(const int array[], int size)
{
    for (int count = 0; count < size; count++)
        cout << array [count] << " ";
    cout << endl;
}

程序输出结果：

The unsorted values are :
7 2 3 8 9 1
The sorted values are:
7 2 3 8 9 1