冒泡排序是一种比较简单的排序算法，它循环走过需要排序的元素，依次比较相邻的两个元素，如果顺序错误就交换，直至没有元素交换，完成排序。
 若对n个人进行排序，我们需要n-1次比较，所以第k次比较需要进行n-k次比较。排序算法通过以数据对象的两两比较作为关键，所以可以得出，冒泡排序需要进行的
 比较次数为：(n-1) + (n-2) + … + 1 = n*(n-1) / 2，因此冒泡排序的时间复杂度为O(n^2)
 
 以js实现为例：
 
   //1.冒泡排序-s--两两比较，大的和小的换位置
   let dataList=[12,2,3,46,1,2,8];
   let hasSort=[];
  //第一遍循环 n-1 次  (n=dataList.length)
   for(let i=0;i<dataList.length;i++){
  //第二遍循环 n-i-1 次
         for(let j=0;j<i;j++){
           if(dataList[i]>dataList[j]){
            let _data = dataList[i]
            dataList[i] = dataList[j]
            dataList[j]=_data
           }
         }
         hasSort.push(dataList[i]);
   }
   console.log("hasSort:"+hasSort)
   //1.冒泡排序-end

以下是本节涉及的知识点：
 
冒泡排序法
交换数组元素
二重循环
其他常用排序法
 
本节是贸大95%学生的噩梦。其实我觉得，之所以是噩梦，可能只是老师没讲清楚，自己上课没认真听，ppt也没说清楚导致的。所以我在这里会尽可能地简单地把冒泡排序法拆解成一个一个的小步骤。希望各位能尽可能地理解。
 
当然实在理解不了也没问题。本来排序法就不是考试的重点，只有一个比较小的概率会出成程序大题。但是如果理解了的话，会对自己编程能力有很大提升。
 
首先还是说说排序法为什么很重要。
 
排序是很常见的操作
 我们在很多情况下都需要对数据进行排序，比如考试成绩出来了，我们想看自己排在第几名，亦或是玩牌的时候对自己抽到的牌按自己希望的顺序排列，都需要用到排序。
排序是很复杂的操作
 把东西按照自己希望的顺序去排列，即使在现实中也是一个相当大的工程量（请自行想象把一个考室所有学生的卷子打乱，再让你按学号从小到大顺序排列）图书管理员为图书辛辛苦苦编号，分门别类排列，就只为减少排序和查找的工作量。
 
排序的方法有很多种，我们现阶段可能接触得到有冒泡排序法、选择排序法、插入排序法和快速排序法。它们都是以排序方法的基本思路命名的。就我个人而言，我在现实中对什么文件进行排序的话，我都是用的插入排序法（下面会介绍其基本思路）。
 


 
文章目录
 
冒泡排序法基本原理
冒泡排序法的代码实现
定义并初始化数组
交换变量的值
实现两元素间调整顺序
第一遍走访数组的情况
第i次走访数组的情况
走访N-2次数组
最后是输出
小结
  
为什么我的代码和PPT上的不太一样？
后话：冒泡排序的可视化
后话：别的排序方法呢？

 
冒泡排序法基本原理
 
冒泡排序法是排序法里面最低级，最低效，但也是最简单的一种排序法，因为其对元素的排序过程像是水中的气泡在上浮，所以被称为冒泡排序法。
 
其基本思路是这样的：逐个比较相邻元素，如果有顺序不对的，就把它们调换，使得顺序正确。只走访一次数组，基本上不能完成排序。但只要我们不断重复走访数组，不断地找到顺序有误的相邻元素，不断地纠正其顺序，就可以实现让数组按顺序排列。
 
比如下面是一个例子，我们试图把下面的数组按从小到大顺序排列：
 5 1 4 2 3
 对于这个数组，我们首先比较其头两个元素，发现5和1的顺序反了，1应该在5的前面，所以我们把5和1调换位置，得到
 1 5 4 2 3
 接下来我们比较第2个和第3个元素，发现5和4的顺序依旧反了，所以我们让5和4调换位置，得到
 1 4 5 2 3
 接下来是第3个和第4个元素，发现5和2的顺序依旧反了（事实上，直到5被放到最后之前，都一直是5和其他数比较），所以我们让5和2调换位置，得到
 1 4 2 5 3
 接下来是第4个和第5个元素，发现5和3的顺序依旧反了，所以我们让5和3调换位置，得到
 1 4 2 3 5
 到这里，我们已经成功走访了一次数组，并实现了4次调换。会发现此时的数组已经开始稍微有点顺序了。
 此时在数学上可以证明：数组中最大的元素已经被我们移到数组末尾，不论它原先在什么位置。
 
但数组还没有实现完全的按顺序排列。所以我们重新开始比较头两个元素：
 1 4 2 3 5
 其头两个元素，1和4的顺序是正确的，所以我们不调换其位置。下面比较第2和第3个元素：
 1 4 2 3 5
 我们发现4和2的顺序反了，所以我们把4和2交换顺序，得到：
 1 2 4 3 5
 下面比较第3和第4个元素，发现4和3的顺序反了，所以我们把4和3交换顺序，得到：
 1 2 3 4 5
 因为前一次走访中，我们已经让最大的元素移到了第5号位置，所以此时无需再比较第4和第5个元素，因为第5个元素必然是最大的。
 由于这个操作和前一次走访数组是一样的，所以同理也有这个性质：数组中第二大的元素已经被我们移到了倒数第二的位置，不论它原先在什么位置。
 
当然此时已经把数组排好序了，但如果顺序依旧不对的话，也是这样做。让第三大的元素排到倒数第3号位，直至数组实现完全从小到大顺序排列。
 
至此，数组排序完毕。
 我们可以发现，元素5在第一次走访数组的时候，从数组的第一号位置，逐渐移到最后一号位置，其行为就像是一个石头逐渐下沉（或者一个气泡逐渐上浮），这就是冒泡排序法的名字由来。
 
用数学化的语言来说，冒泡排序法就是这样的：
 
 
对于一个长度为N的数组：
 
  
对于其第1到第N-1个元素，我们逐一比较这个元素与其之后的元素的大小顺序，若相反，则交换他们次序，使得这两个元素顺序正确。
走访第一遍以后，我们可以确保最大的元素已经在最后的位置了。
 
 
然后我们就只需要对数组的前面1到N-1个元素进行排列：
 
  
排列的方法是一样的，不过现在我们走访只需要走访其第1到第N-2个元素了。
当此次走访完后，我们可以确保原数组里面倒数第二大的元素已经在倒数第二个位置。也就是说数组的第N-1和第N个元素已经实现了有序排列。
 
 
接下来是对数组的前面1到N-2个元素进行排列：
 
  
排列的方法是一样的，不过现在我们走访只需要走访其第1到第N-3个元素了。
当此次走访完后，我们可以确保原数组里面倒数第三大的元素已经在倒数第三个位置。也就是说数组的第N-2到第N个元素已经实现了有序排列。
 
 
接下来就不断重复这个操作，需要排序的部分越来越短，后面已经排好序的部分越来越长。
 
 
直到需要排序的部分长度为1时，此时就不需要再进行任何排序。
 
 
此时这个数组在数学上就已经可以被证明是有序排列的了。
 
 
冒泡排序法的代码实现
 
首先，还是从一个情景展开讨论：
 
 
 
针对一个长度为N的整数数组（假定N=15），其中可能有重复的数字，也可能没有。请用冒泡排序法使其内部元素按从小到大顺序排列。
 
 
根据前面我们对冒泡排序法的讲解，我们可以把这个情景分解为如下步骤：
 
定义并初始化数组
判断某个元素与它后面的那个元素的大小关系，如果顺序反了，就交换它们的位置
（第1次走访数组）对于前N-1个元素的每一个都执行一遍上述操作
 执行完前一操作后，（第2次走访数组）再对数组前N-2个元素的每一个执行一遍第二步的操作
 执行完前一操作后，（第3次走访数组）再对数组前N-3个元素的每一个执行一遍第二步的操作
 ……
 直到第N-2次走访数组，此时只需要对数组的前1个元素执行第二步的操作（对第1个和第2个元素调整顺序）。此时无需再次走访数组，数组已经达到有序状态。
 总结便是这样：
对于第i次走访数组，我们都对数组的前N-i个元素的每一个执行一遍第二步的操作。
 其中i从1一直加到N-2。
当上述操作结束后，数组变得有序。此时只需在屏幕上输出数组
 
定义并初始化数组
 
首先我们先把最简单的工作做了：定义并初始化数组：
 
#include<iostream>
using namespace std;

int main(){
    const int N = 15;
    int a[N]={9,7,15,6,2,18,6,24,-3,12,7,15,1,0,4};
}
 
其中数字是我随便输的，可以发现其中有重复的数字。不过这并不影响我们排序。
 
交换变量的值
 
接下来我们来做最基础的工作：交换两个变量的值。我们一般情况下是需要引入一个新的变量来暂时存储其中一个，不然就很难进行交换。（可以理解为，想要把两个箱子的位置交换，必须先把一个箱子移到别的地方，再把另一个箱子挪到这个箱子位置，最后再把最开始那个箱子挪到正确的位置去。）
 交换的代码可以是这样：
 
int tmp;
tmp=a[j];
a[j]=a[j+1];
a[j+1]=tmp;
 
这样便实现了对数组a下标为j和下标为j+1的元素之间的交换。
 
实现两元素间调整顺序
 
下面我们加入判断：只要数组a下标为j和下标为j+1的元素不满足从小到大的顺序关系，我们就把它们交换顺序。这个用if语句很容易实现：
 
if(a[j]>a[j+1]){
    int tmp;
    tmp=a[j];
    a[j]=a[j+1];
    a[j+1]=tmp;
}
 
第一遍走访数组的情况
 
下面，我们要对数组的前N-1个元素都要执行这个判断（之所以是N-1，是因为第N个元素后面没有元素了，a[j+1]就会下标越界了。无法比较，所以只比较到N-1和N）用一个for循环便能做到：
 
int j;
for(j=0; j<=N-2; j++)
    if(a[j]>a[j+1]){
        int tmp;
        tmp=a[j];
        a[j]=a[j+1];
        a[j+1]=tmp;
    }
 
注意循环的判断条件是N-2！因为我们之前一直用的是“前N-1个元素”，而C++里面下标从0开始，第N-1个元素的下标是N-2！千万不要弄错第几个元素和元素下标之间的区别。
 
这里我用小于等于，是因为j可以取到N-2（此时比较下标为N-2和N-1的元素，也就是第N-1和第N号元素）。写成 j<N-1也是可以的，但这样可能大家就会对N-1的由来觉得理所当然，所以为了强调下标的差别，我用小于等于。
 
第i次走访数组的情况
 
目前第一次走访数组的代码我们就写出来了。下面拓展到第i次走访数组，其实只是修改了for循环的判断条件而已：
 
int j;
for(j=0; j<=N-1-i; j++)
    if(a[j]>a[j+1]){
        int tmp;
        tmp=a[j];
        a[j]=a[j+1];
        a[j+1]=tmp;
    }
 
要注意的是，我们这里定义的i是走访数组的次数。最初的时候，也就是第一次走访数组，i是1而不是0。我们很容易推出循环判断条件应该是 j<=N-1-i（因为i=1时，就是前一步的情况，即N-2）
 
走访N-2次数组
 
最难的地方已经过去了。下面只剩下让i从1到N-2不断循环了：
 
int i;
for(i=1; i<=N-2; i++){
    第i次走访数组，需要对数组下标为0到N-i-1的元素调整顺序 
}
 
把文字替换为前一步得到的代码，就是：
 
int i, j, tmp;
for(i=1; i<=N-2; i++)
    for(j=0; j<=N-1-i; j++)
        if(a[j]>a[j+1]){
            tmp=a[j];
            a[j]=a[j+1];
            a[j+1]=tmp;
        }
 
因为这两个for循环里面实质上都只有一条语句，所以我在这里就省略了大括号，如果觉得看起来不舒服也可以加上。
 
最后是输出
 
长吁一口气吧，前一步的代码执行完毕后，数组就变得有序了！下面我们只需要在屏幕上输出数组就好了：
 
for(i=0; i<N; i++){
    cout<<a[i]<<' ';
}
 
小结
 
整理一下，我们现在都写了些什么：
 
#include<iostream>
using namespace std;

int main(){
    //定义常量与数组 
    const int N = 15;
    int a[N]={9,7,15,6,2,18,6,24,-3,12,7,15,1,0,4};
    
    //执行冒泡排序操作 
    int i, j, tmp;
    //对于第i次走访数组 
    for(i=1; i<=N-2; i++)
        //我们对数组的前N-i个元素的每个元素调整顺序 
        for(j=0; j<=N-1-i; j++)
            //只要下标为j的元素比它后面的大，就需要调整顺序 
            if(a[j]>a[j+1]){
                //我们交换下标为j元素和其后面的元素 
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
    
    //在屏幕上输出数组 
    for(i=0; i<N; i++){
        cout<<a[i]<<' ';
    }
}
 
参见附件知识网络1.4.1，运行一下看看效果吧。
 
其实只是一个二重循环而已，但是
 
内层循环的边界条件却在不断发生变化。
两个for循环的初始化条件和循环条件都和常规for循环不太一样。
两重循环不能像前面几个例子那样分开考虑，它们相互关联。
 
这便是冒泡排序法真正难倒人的地方。
 
为什么我的代码和PPT上的不太一样？
 
我们在这里定义的i和j的意义可能与PPT的不太一样，所以导致两个for循环的边界条件不太一样。同时我们还用的是小于等于而不是小于，这也是导致区别的主要原因。
 看原代码：
 
for(i=1; i<=N-2; i++)
    for(j=0; j<=N-1-i; j++)
        if(a[j]>a[j+1]){
            tmp=a[j];
            a[j]=a[j+1];
            a[j+1]=tmp;
        }
 
注意到第一个for循环里面i<=N-2与i<N-1等价，j<=N-1-i与j<N-i等价，如果这么一换的话，-1就直接没了，for循环会更好看一点，但是此时for循环的条件可能没有前面那个易懂：
 
for(i=1; i<N-1; i++)
    for(j=0; j<N-i; j++)
        if(a[j]>a[j+1]){
            tmp=a[j];
            a[j]=a[j+1];
            a[j+1]=tmp;
        }
 
如果我们比较的不是某元素与其后面的元素顺序，而是比较与其前面的顺序的话，j的意义会发生本质变化。此时我们再稍微调整一下i的大小，此时i也失去了其原本意义，但是会让我们的两个for循环越来越接近我们以前接触的循环：
 
for(i=0; i<N-2; i++)
    for(j=1; j<N-i; j++)
        if(a[j-1]>a[j]){
            tmp=a[j];
            a[j]=a[j-1];
            a[j-1]=tmp;
        }
 
又或是ppt上的那个冒泡排序不是最大的往后走，而是最小的往前走，此时for循环的结构会变得更多（j++会变成j--，还有好多地方都要修改）。
 
介绍了这么多微妙变化的版本，其实只是想说，这些都是正确的。没有一个绝对正确的答案。
 
后话：冒泡排序的可视化
 
这个不是考点。只是这样做，能把冒泡排序的过程更加清晰地展示出来，可能让我们对冒泡排序的理解更加深刻。
 
在每次for循环的时候，可以执行一遍输出，把正在排序的数组展示出来，可以让我们看清楚冒泡排序每次循环都干了些什么：
 
#include<iostream>
using namespace std;

int main(){
    //定义常量与数组 
    const int N = 15;
    int a[N]={9,7,15,6,2,18,6,24,-3,12,7,15,1,0,4};
    
    //排序前进行输出 
    cout<<"排序前："<<endl;
    for(int k=0; k<N; k++){
        cout<<a[k]<<' ';
    }
    cout<<endl;
    cout<<"下面是排序过程："<<endl;
    //执行冒泡排序操作 
    int i, j, tmp;
    //对于第i次走访数组 
    for(i=1; i<=N-2; i++){
        //我们对数组的前N-i个元素的每个元素调整顺序 
        for(j=0; j<=N-1-i; j++){
            //只要下标为j的元素比它后面的大，就需要调整顺序 
            if(a[j]>a[j+1]){
                //我们交换下标为j元素和其后面的元素 
                tmp=a[j];
                a[j]=a[j+1];
                a[j+1]=tmp;
            }
            
        }
        //每次走访数组完毕后进行输出 
        for(int k=0; k<N; k++){
            cout<<a[k]<<' ';
        }
        cout<<endl;
    }
    //排序前进行输出 
    cout<<"排序后："<<endl;
    for(int k=0; k<N; k++){
        cout<<a[k]<<' ';
    }
    cout<<endl;
}
 
这个版本中，在排序前和每次走访完数组（即外层的循环里面，如果在内层循环，则是每次比较元素后都会输出，输出会太多不好看）都会把数组的内容输出的屏幕上。
 参见附件知识网络1.4.2，运行一下看看效果吧。
 
可以发现，冒泡排序的排序过程和我们之前预想的是一样的。
 
后话：别的排序方法呢？
 
非考点。
 除了冒泡排序法外，常用的基础排序法还包括选择排序法、插入排序法、快速排序法等。
 下面简要介绍这些排序的主要思路：
 
选择排序：从数组中找到最大值，将其移到数组末尾。再从剩下的元素里面找到第二大的，移到倒数第二位置。有点像冒泡排序法的原理，但其中部分细节不太一样。
插入排序：对于数组中的每个元素，我们将它和已经排好序的部分逐个比较，看它能插入到这个这个有序的部分的哪里，始终保持这个部分的有序。当最后一个元素被插入时，整个数组也就有序了。
快速排序：因为它比一般的排序算法快而得名。基本原理是，把数组按某个元素为分界，把所有小于这个元素的元素移到它的左边，大于的移到它的右边。然后对这个元素左右两边分别再执行上述操作。
 
如果对其余的排序算法感兴趣的话，可以参考阅读下面的文章：
 http://www.cnblogs.com/eniac12/p/5329396.html
 这里面还有很多动图，可以形象地展示排序的过程。
 （后面有些算法的动图可能会让你赞叹人类智慧的伟大（奸笑））

 
 
冒泡排序的原理有一下几个步骤
 
1 逐一比较数组中相邻的两个元素,如果后面的数字小于前面的数组,就交换前后元素
 
2 经过一轮的比较之后一定有一个最大的排在后面的位置
 
3 每次比较剩下的元素,经过n-1次比较,可以实现排序.
 
 
 
package me;

import java.util.Arrays;

public  class Me {
    public static void main(String[] args) {
      int [] arr = {3,2,5,8,6,4,9}; //用冒泡排序
        for (int i=0;i<arr.length-1;i++){ //遍历数组 第一个元素定义为i
            for (int j=0;j<arr.length-1-i;j++){ //遍历数组定义第二个元素为j,加入i是3那么数组中j就是2
                if (arr[j]>arr[j+1]){ //如果第一个元素大于第二个元素 交换
                    int value = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1]=value;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
    
   
}
 
如果这个交换元素的值不清楚的话可以看下图
 
 
 

/*
  
This file is used for Exp6_1,Bubble sorting
 
Written by Namer_Mega, Thanks for sharing your knowledge.
 
*/
 
 
 #include<stdio.h>
 
 void sorting(int a[],int n)
 {
 int j,i,temp,k;
 for(j = 0;j<n-1;j++)
 for(i = 0;i<n-1-j;i++)
 {
 if(a[i]>a[i+1]) 
 { 
 temp = a[i];
 a[i] = a[i+1];
 a[i+1] = temp;
 } 
 }
 for(k=0;k<n;k++)
 {
 printf("%d ,",a[k]);
 }
 printf("\n");
 }
 
 
 int main(void)
 {
 int a[10]={112,4,5,34,6,76,47,87,345,12};
 sorting(a,10); 
 }