排序（一）–冒泡排序

思路：比较相邻的两个元素的大小

直接上例子，对下列数组进行排序（从小到大）：

10，1，35，61，89，36，55

第一次比较：10 和 1，10大于1。交换位置：1，10，35，61，89，36，55

第二次比较：10 和 35， 35大于10， 不交换位置，保持原样

第三次比较：35 和 61，61大于35，不交换位置，保持原样

第四次比较：61 和 89， 89 大于61，不交换位置，保持原样

第五次比较：89 和 36， 89大于36，交换位置：1，10，35，61，36，89，55

第六次比较：89 和 55， 89大于55，交换位置：1，10，35，61，36，55，89

此时，第一轮比较完成，可以看出比较了6次，而我们一共有7个数，89像水中的泡泡一样，不断往上冒，直到最后，89一定是最大的数，而且放在了最后。

下面进行第二轮，此时89将不考虑在内，我们只排序前面6个数：

第一次比较：1 和 10 ，1小于10，不交换位置。保持原样：1，10，35，61，36，55

第二次比较：10 和 35，10小于35，不交换位置。

第三次比较：35和61，35小于61，不交换位置。

第四次比较：61 和 36，61大于36，交换位置：1，10，35，36，61，55

第五次比较：61 和 55，61 大于55 ，交换位置：1，10，35，36，55，61

此时，第二轮比较完成，可以看出比较了5次，而我们一共有6个数，61最后成为了该序列中最大的数，而且放在了最后。

然后进行第三轮（61不考虑在内）：

第一次比较：1 和10，不交换位置

第二次比较：10 和35，不交换位置

第三次比较：35 和36，不交换位置

第四次比较：36 和 55，不交换位置

此时，第三轮完成，而且已经是一个有序的过程了，但是我们依然要完成后面剩下的三轮排序，每轮剔除一个数。

因此，N个数字要排序完成，总共要进行N-1轮排序，第i轮排序比较的次数为(N-i)次。

下面给出代码实现：

int arry[7]={10，1，35，61，89，36，55}; for(int i=0;i<N;i++)//这里是判断轮数的循环 { for(int j=0;j<N-i-1;j++)//注意这里要减1，因为上一轮已经判断了一个数，所以这里要减去一个数，每轮都减去一个1数，减少不必要的排序。 { if(arry[j]>arry[j+1])//这是从小到大排序，如果要实现从大到小，只需改成<号就可以 { int temp = arry[j]; arry[j] = arry[j+1]; arry[j+1] = temp; } } }

下面给出另外一个代码：

int arry[7]={10，1，35，61，89，36，55}; for(int i=1;i<N;i++)//这里是判断轮数的循环 { for(int j=N-1;j>=i;j--)//这里j是从后往前循环，上面的代码是从前往后 { if(arry[j]>arry[j+1])//这是从小到大排序，如果要实现从大到小，只需改成<号就可以 { swap(arry[j],arry[j+1]);//使用C++自带的函数库交换 } } }

最后进行一下优化

int arry[7]={10，1，35，61，89，36，55}; int flag = true; for(int i=1;i<N && flag;i++) { flag = false; for(int j=N-1;j>=i;j--) { if(arry[j]>arry[j+1]) { swap(arry[j],arry[j+1]); flag = true;//如果有数据交换，则flag变成true，下一轮要进行循环，如果没有交换，说明数据已经是有序的，较少不必要的循环 } } }

最后附上时间复杂度，当序列是完全逆序时，其时间负责度为O(n2).

再给一个动画的链接讲解：

https://www.jianshu.com/p/1458abf81adf