浅析冒泡排序算法

冒泡排序（Bubble sort）是最经典的排序算法

一、算法描述

他的排序思想是这样的，依次比较相邻的数据，将小数据放在前，大数据放在后；即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，以此类推第一趟将最大的数"滚动"到最后一个位置；第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。

例如：我们将 [ 5 9 3 6 1 4 ]这些数字按照从小到大的顺序排序。

步骤

两两比较相邻的数字，左边比右边大就把这两个数字进行交换。

1.比如一开始排序的时候我们拿5和9进行比较，因为5比9小所以不做交换。

2.接下来我们对数字9和3做比较，因为9大于3所以我们对他进行交换，变成 [ 5 3 9 6 1 4 ]

3.接下来我们对9和6进行比较，因为9大于6所以我们对他进行交换，变成 [ 5 3 6 9 1 4 ]

4.接下来我们对9和1进行比较，因为9大于1所以我们对他进行交换，变成 [ 5 3 6 1 9 4 ]

5.最后一次我们对剩下的9和4进行比较，因为9大于4所以我们对他进行交换，变成 [ 5 3 6 1 4 9 ]

这就完成了一趟排序，一趟用就是把当前的最大值放在最后面，我们不能保证前面五位数的顺序，但是能保证最大的数一定排在最后。

所以一趟排序我们能把最大数字放在最后。依次我们对前5个数字做排序，再对前4个数字做排序，一直这样最后就可以对整个数组进行从小到大的顺序排序。

二、算法实现

下面进行代码：

#include <stdio.h>void bubble(int arr[], int n){
  int i;
  int temp;
  for (i=0; i<n-1; i++){
    if (arr[i] > arr[i+1]){
      temp = arr[i];
      arr[i] = arr[i+1];
      arr[i+1] = temp;
    }
  }
} 

void bubbleSort(int arr[], int n){
  int i;
  for (i=n; i>=1; i--){
    bubble(arr,i);
  }
}

int main(){
  int arr[] = {5,9,3,6,1,4};
  int i;
  bubbleSort(arr,6);
  for (i=0; i<6; i++){
    printf("%d\n",arr[i]);
  }
}

输出：

三、算法分析

平均时间复杂度：O(n2)

空间复杂度：O(1) (用于交换)

稳定性：稳定（在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式）

四、适用场景

冒泡排序适用于数据量很小的排序场景，因为冒泡的实现方式较为简单。

关注下方公众号，分享硬核知识