C语言排序算法之冒泡排序_冒泡排序c语言

---

一、冒泡排序概述

冒泡排序重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

二、冒泡排序算法分析

1.图像分析原理

我们每一次冒泡都是把这些的数其中最大的数放在这些数的最后,直到完成排序。
我们先来通过图像去分析

程序是先从第一个开始判断的,首先比较第一个数和第二个数,从图中很明显看出5>1,我们是把大的数往后冒泡的,所以这时5和1应该交换位置变成

然后我们这时比较5和3了，因为5>3,所以5和3交换位置。

我们在继续比较5和2，明显5>2，5和2交换位置，5来到了这些数的最后面，所以就完成了第一次排序。

接着我们比较1和3 ，3>1，所以不用交换，我们就比较3和2，3>2，3和2交换

因为5在之前比较过来，所以我们就把5给排除了，在剩下的数中，3就来到了最后（这里的最后是指除5之外剩下的），所以这时我们完成了第二次排序。

虽然我们可以明显看出1<2，以为不用再一次比较了，但是计算机没有你这么聪明，万一那个不是1而是4呢，那不就出错了吗，所以我们还得比较一次
1<2，不用换，这时我们就完成了第3次排序，也是完成了所有这些数的冒泡排序。

2.冒泡排序算法代码详解

既然我们知道了原理，那我们结合一下代码来理解吧。

下面是冒泡代码的主要部分，下面有注释。
我是将冒泡排序算法写成了一个函数，函数名是bubbleSort()，当然函数名也可以是其他名字。

 void bubbleSort( int data[] ,int n )//data[]是传过来的数组，n是数组中那些数的个数
{
 /*----begin------*/
 for(int i=0;i<n-1;i++)//这里是外循环，有n个数就比较n-1次
 {
    for(int j=0;j<n-1-i;j++)//这是内循环，每轮比较n-1-（上一轮的除去的数的个数）
    {
      if(data[j]>data[j+1])//判断如果左边的数大于右边的数，就把大的数往右移
      {
        //这个是交换不用第三方变量的方式，当然也可以借用第三方变量来交换
        data[j]=data[j]+data[j+1];
        data[j+1]=data[j]-data[j+1];
        data[j]=data[j]-data[j+1];
      }
    }
 }
 /*-----end------*/
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

你们注意到了吗，该算法使用到了双循环，为什么是双循环呢？
你想想，在上面我举得例子中刚开始是5和其他的数一直不断的循环比较直到找出一个最大值，在这个过程中就是一个循环，这个循环中5是不是和其他数一共比较了3次，因为他们就一共4个数，所以就比较了4-1次，然后到排除5，剩下3个数，就比较3-1次
刚开始的数是：（5 1 3 2）
第一轮 有4个数 比较了4-1次，5排到括号里的最后，然后把5排除剩下3个数
得到了：（ 1 3 2 ）5
第二轮 有3个数 比较了3-1次，3排到括号里的最后，然后把3排除剩下2个数
得到了：（1 2 ）3 5
第三轮 有2个数 比较了2-1次，2排到括号里的最后，然后把5排除剩下1个数
得到了：（1 ）2 3 5
然后就结束了排序，我们从中看出一共比较了3轮，每轮都比较了几次，所以我们可以明显看出比较了几轮的是外面的循环，每轮比较了几次的是内循环，这不就头脑清晰了吗？
我们再来捋一捋：
一共有4个数，所以比较了4-1=3轮
第一轮比较了4-1-0=3次
第二轮比较了4-1-1=2次
第三轮比较了4-1-2=1次
得知：
（1）有n个数就比较n-1轮
（2）有n个数，每轮比较n-1-（上一轮的除去的数的个数），
比如第一轮比较的次数就是n-1-0（上一轮是第0轮,除去的数的个数为0，所以减0）
第二轮比较的次数就是n-1-1（上一轮是第1轮,除去的数的个数为1，所以减1）
第三轮比较的次数就是n-1-2（上一轮是第2轮,除去的数的个数为2，所以减2）
再次结合上面的代码就可以写出冒泡排序了。

---

三、总代码

#include <stdio.h>
#include <stdlib.h>

//冒泡排序
void bubbleSort( int data[] ,int n )//data[]是传过来的数组，n是数组中那些数的个数
{
 /*----begin------*/
 for(int i=0;i<n-1;i++)//这里是外循环，有n个数就比较n-1次
 {
    for(int j=0;j<n-1-i;j++)//这是内循环，每轮比较n-1-（上一轮的除去的数的个数）
    {
      if(data[j]>data[j+1])//判断如果左边的数大于右边的数，就把大的数往右移
      {
        //这个是交换不用第三方变量的方式，当然也可以借用第三方变量来交换
        data[j]=data[j]+data[j+1];
        data[j+1]=data[j]-data[j+1];
        data[j]=data[j]-data[j+1];
      }
    }
    print(data,n);//输出每一轮排序后的数
 }
 /*-----end------*/
}

//输出数组元素
void print(int data[] ,int n)
{
 for(int i=0;i<n;i++)
   printf("%d ",data[i]);
 printf("\n");//输出后换行
}
//主函数
int main()
{
	int data[]={5,1,3,2};//数组元素
    bubbleSort(data,4);//调用冒泡排序函数
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

这是运行后的图：

然后就结束了。