概述

冒泡排序是一种极其简单的排序算法，它重复地走访过要排序的元素，依次比较相邻两个元素，如果它们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。尽管冒泡排序是最容易了解和实现的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。

算法描述

1.比较相邻的元素，如果前一个比后一个大，就把它们两个对调位置。

2.对排序数组中每一对相邻元素做同样的工作，直到全部完成，此时最后的元素将会是本轮排序中最大的数。

3.对剩下的元素继续重复以上的步骤，直到没有任何一个元素需要比较。

代码实现

void Swap(int arr[], int i, int j)
{
    int temp=arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

/**
* 冒泡排序
* 最差时间复杂度 O(n^2)
* 最优时间复杂度 O(n)
* 平均时间复杂度 O(n^2)
* 空间复杂度    O(1)
* 稳定性       稳定
* 效率         对于少数元素之外的数列排序是很没有效率的
* @param arr 数组
* @param n 长度
*/
void BubbleSort(int arr[], int n) {
    for (int i=0;i<n-1;i++)//每次最大元素就像气泡一样浮到数组的最后
    {
        for(int j=0;j<n-1-i;j++) //依次比较相邻的两个元素，使较大的那个向后移
        {
            if(arr[j]>arr[j+1]) //如果条件改为arr[j] >= arr[j+1] 则变为不稳定的排序算法
            {
                Swap(arr, j, j + 1);
            }
        }
    }
}

上述代码对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行冒泡排序的实现过程如下

使用冒泡排序为一列数字进行排序的过程如右图所示：

掌握本节内容