C语言必学的12个排序算法：冒泡排序（第4篇）

亦凉 2023-03-03 15:30 14阅读 0赞

# 基本思想 #

冒泡排序（Bubble Sort），是一类“交换”类排序方法，类似水中冒泡，最大的数据会沉到水底，较小的数会浮上来。很简单，以从小到大排序为例，每一趟排序将“逆序”（前一个元素比后一个元素大）相邻两个数据元素交换，这样就会将最大的元素交换到“最后”的位置，冒泡排序每趟子排序过程都会将当前“最大”元素交换到最后位置，较小的元素会渐渐排到前面。

冒泡排序时间复杂度是O(n^2)，是稳定的排序，当初始序列为从小到大有序时，仅需要进行n-1次关键字比较，不需要移动任何记录，即可完成排序过程；当初始序列从大到小逆序时，需要进行n-1趟排序，进行n(n-1)/2次比较和交换。

举例来说：

例如：给定10个整数：(4,3,1,2,6,5,0,9,8,7) 从小到大排序。

第一趟子排序：针对整个数据记录(4,3,1,2,6,5,0,9,8,7)

3和4 逆序，交换，得到(3,4,1,2,6,5,0,9,8,7)

1和4 逆序，交换，得到(3,1,4,2,6,5,0,9,8,7)

4和2 逆序，交换，得到(3,1,2,4,6,5,0,9,8,7)

4和6 有序，不交换，不变化(3,1,2,4,6,5,0,9,8,7)

6和5 逆序，交换，得到(3,1,2,4,5,6,0,9,8,7)

6和0 逆序，交换，得到(3,1,2,4,5,0,6,9,8,7)

6和9 有序，不交换，不变(3,1,2,4,5,0,6,9,8,7)

9和8 逆序，交换，得到(3,1,2,4,5,0,6,8,9,7)

9和7 逆序，交换，得到(3,1,2,4,5,0,6,8,7,9)

很明显，一趟子排序后，在整个数据记录(4,3,1,2,6,5,0,9,8,7)得到最大的数据元素9，现在的数据记录为(3,1,2,4,5,0,6,8,7,9)。

第二趟子排序：对数据子记录(3,1,2,4,5,0,6,8,7)进行相同的交换过程，注意9可以不参与排序了。

…

直到：一趟排序过程中，没有任何交换数据元素的操作即为有序。

# 代码实现 #

*/
    #include <stdio.h>
    
    void bubble_sort(int a[], int length)
    {
      int i,j,t;
      // 每趟排序需要减少待排序的数据记录长度 
      for(i=length; i>0; i--)
      {
        for(j=1; j<i; j++)
        {
          if(a[j] < a[j-1])
          {
            t = a[j];
            a[j] = a[j-1];
            a[j-1] = t;        
          }
        }
      }
    }
    
    
    int main(void)
    {
        int a[10] = {4,3,1,2,6,5,0,9,8,7};
        bubble_sort(a, 10);
        int i;
        for(i=0; i<10; i++)
          printf("%d ", a[i]);
        return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20230208/3f92494e681a432ba96b04a22dbf117b.png
[format_png 1]: /images/20230208/b6e49a8e65fe4bb2b567782685ce35b1.png